Detecting when pathfinding has failed

I have successfully implemented a simple pathfinding routine as described in this Wikipedia article:

https://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm

I used the "sample algorithm", which starts at the endpoint, words across the grid by hopping to adjacent cells, counting the hops as it goes, and then using the number of hops to track the path back from the start to the end point. It works well, and is fairly fast.

The only problem I have is that the loop for calculating the path never breaks if there is no route to the destination (i.e. if the path is blocked).

I have considered limiting the number of rounds for the calculation; the maximum possible steps on the board will be (rows*columns)-1, so in a 10*10 grid, if a path hasn't been found within 99 rounds, there is no path. However, this could be very wasteful, for example if the start point is within a very confined space with only a few possible moves around it.

I'm writing in Cocoa + Objective-C, but I wouldn't have thought that makes a difference, as this seems to be a logical issue rather than one regarding the framework I'm developing in.

• Wow, that section is an absurdly bad description of one of the most well-known algorithms in programming, breadth-first search. They didn't even mention it by name! – BlueRaja - Danny Pflughoeft Jan 28 '18 at 16:11
• @BlueRaja-DannyPflughoeft - I'm an experienced programmer, but found that article very difficult to understand. I had to draw it out on paper and work through the example to get my head around it before translating the process to an in-code version! – mashers Jan 28 '18 at 18:12

And, as is often the case, having typed the problem out and thought for a few seconds, the solution has occurred to me.

The sample pathfinding algorithm ignores un-occupiable positions on the grid, and makes its way across the occupiable positions. It essentially "fills up" the traversable parts of the grid, recording as it goes how many hops away from the destination each cell is.

Once the traversable area has been mapped, no more steps will be possible. When no more steps can be taken, if the destination hasn't been reached, then it is unreachable.

In programming terms, this meant the following. My method for traversing the map was a function which takes as its only parameter an array of grid positions. The first time the function is called, the array contains only one item - the starting position. Each time the function runs through, it looks at all of the positions currently in the array, and for each of them, examines the adjacent cells. Any traversable cells which haven't already been crossed are added to the array, and then the (now larger) array is fed back into the function. The function only returns when one of the found cells is the destination.

I modified this by storing the current number of steps in the array at the beginning of the function. Then, at the end of the function, I compared the number of items now in the array to the number recorded at the beginning.

If the number of steps in the array is the same as before, then no more steps were taken, and the destination must be unreachable.

• As a point of interest on the topic, pathfinding algorithms often will perform a bi-directional search; you search both from the start to the destination, and simultaneously also from the destination to the start. (Typically by alternating sides after each step in the search process) The path is complete once you find a point which has been considered by both the "from start" and "from destination" paths. Searching from both ends means you detect "start/end is in a locked room" failure states a lot faster. – Trevor Powell Jan 29 '18 at 1:14
• (because once the small number of spaces on the interior of the locked room are fully searched, you know there's no path and can stop; you don't have to search the entire world map, as a single-direction search from the outside of the locked room must do) – Trevor Powell Jan 29 '18 at 1:18
• @TrevorPowell To add to this, imagining the search as growing circles shows that searching from the start and end covers less ground than start or end. Start or end, search ends when it reaches the other (distance d): a=πd². Start and end, search ends halfway between: a=2π(d/2)² (two circles with half radius (1/4 area) -> halved search space) – phflack Jan 29 '18 at 18:10