Would it be acceptable to place bounds around my pathfinding area?

Question

I'm currently using the A* pathfinding algorithm to calculate a path on an infinite grid (using an UnboundedGrid in Gridworld, the AP CS case study, if that helps anyone). Everything works wonderfully, except for cases where no valid path exists because the end node is completely surrounded by walls. As expected, the algorithm continues searching infinitely, never finding the end node.

A possible solution to this would be to place invisible (as in, the user doesn't see them but the algorithm does) walls around the entire pathfinding area, making sure the start node, end node, and all the wall nodes are within these walls, with 2-3 spaces padding or so. Something like:

_________________________________
|                               |
|              S  |             |
|            _____|   _____     |
|                     | E |     |
|                     |___|     |
|_______________________________|

...the idea being that eventually all the nodes will be added to the closedlist, the openlist will become empty, and at that point I'll know that no valid path exists.

Does this seem like a reasonable solution to the problem? Are there any ways in which this could potentially go wrong? I understand that another solution is to simultaneously pathfind backwards from the end, but this seems like it could be potentially expensive, particularly in cases where the end node isn't so tightly enclosed.

Answer 1

Don't you know exactly where is the end node? If you do, just check if it's surrounded before doing your algorithm.

Answer 2

See also my comment on your question. After typing I came up with what might be a nice solution. This is for a case where you do not know your end node and can do nothing with your end-node's position as suggested above.

You could also something along the lines of: "I have found a closed box in my field and no path after x time so with y% propability I can say there is no path, and update the y% to increase over time, but never reaching 100%.

Might be a nice solution which is in the middle of bounding the search area and doing nothing.

Answer 3

I had a similar problem and here's what I did:

1. Run algorithm for n iterations, starting at A searching for B.
2. Run algorithm for n iterations, starting at B searching for A.

If either run determines that one or the other is in a completely isolated area (no more open nodes), the search fails. Otherwise the search is made as normal.

The trick here is, of course, to come up with a good value for n. I did multiple passes with increasing n and cached the results (my graph didnt change alot).

Answer 4

You're using A* so you should be able to weight the terrain nodes with a cost. Put an insanely high cost onto the wall nodes. It must be greater than the total cost of any possible path. If the end cost of the path is greater than that boundary cost, then you had to pass a wall to find a path, so it's invalid. The A* algorithm routes around high cost nodes, so it won't route through a wall unless it has to.