Detecting when pathfinding has failed

Question

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.

Answer 1

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.