I am following the pseudocode on Wikipedia to implement A* algorithm with priority queue to find the shortest path from one source to reach another destination in an infinite large grid. The problem came out when the target is unreachable, e.g., surrounded by walls (no infinite long walls), the algorithm won't stop, so it falls into an infinite loop. My intuitive thought for the solution is to do some preprocessing work, such as adding boundaries based on source and destination, or check whether the destination is surrounded (this won't be easy), before searching. Any suggestions for unreachable early stop? Thanks.
As long as you don't have any infinite walls, you can run A* from the source to the destination, and at the same time run A* from the destination to the source.
If the destination is surrounded by walls, then eventually the destination->source A* will run out of options.
If the source is surrounded by walls, then eventually the source->destination A* will run out of options.
Otherwise they will meet at some point. Whenever that happens you can use the path length from one as a perfect heuristic for the other.