0
\$\begingroup\$

This question already has an answer here:

I've got pathfinding working on a simple 2D grid map. NPCs can now move around the board and avoid areas they cannot travel. This works well, and is carried out by a single sweep of the board to calculate the path.

If there is no path to the destination, I want the entities to move as close as possible. I have also accomplished this, and have been able to reuse my pathfinding code for this purpose. Essentially, if the initial sweep fails to find a path, the reverse sweep is carried out, which essentially identifies every area which is reachable by the entity. The distance from each cell to the intended destination is already calculated by the pathfinding algorithm. So then I just sort the array of accessible cells by their distance from the destination, and the first one is the closest to the destination. Then I use the pathfinder function again to calculate a path to that closest point.

This does work flawlessly, but it seems inefficient. The process of a failed path find in summary is:

  1. Sweep the board for a path to the destination (which fails)
  2. Sweep the board a second time to find all cells accessible by the entity
  3. Sweep the board a third time to calculate the path from the entity to the cell which is closest to the destination

I suspect the answer is that this is the only way to accomplish what I want; I need to calculate all three pieces of information ((1) whether a path exists, (2) which cell is closes, and (3) how to get to the closest cell), but I'm far from an expert on these algorithms so if there is a better way I would love to know!

\$\endgroup\$

marked as duplicate by congusbongus, DMGregory Jan 31 '18 at 23:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Research articles on A-star pathfinding and Dijkstra's algorithm pathfinding. \$\endgroup\$ – Pieter Geerkens Jan 28 '18 at 23:49
  • \$\begingroup\$ Thank you @Pieter Geerkens. I’ve had a cursory look, and for the case at hand I think those algorithms might be overkill. In reality, this case concerns a very small map with entities travelling between defined points. In the end I devised a solution which I will post as a separate answer. \$\endgroup\$ – mashers Jan 29 '18 at 15:06