How to quickly check if there is any path between grid points?
I use the A-star algorithm in my game, and if there is no path, it starts checking too many nodes (the grid is quite large), so as I see I need to check if any path exists in the first place. To not find the actual path, just check if it exists or not. The only algorithm I can think of is to recursively populate the bool matrix. There must be a better way, right?
Optional question: if the path to the target cell does not exist, how do I find an accessible cell (the path exists) and is as close as possible to the original target?
source to share
A * does exactly what ... so there is no significantly better way (links to articles can be found at http://en.wikipedia.org/wiki/Shortest_path_problem )
If you can preprocess, you can color all the dots so that the pairs that can be achieved are colored the same. The later you get 2 points if the color is different from that there is no path.
To find the closing point, you can measure the radius of points with the same color and then start looking for a path that approaches that radius.
source to share