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!

  • \$\begingroup\$ Research articles on A-star pathfinding and Dijkstra's algorithm pathfinding. \$\endgroup\$ Jan 28, 2018 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, 2018 at 15:06


Browse other questions tagged .