0

I am given a map that looks like so:

pathfinding map

Every node is connected with its horizontal and vertical (not diagonal) neighbors and all connections have the same cost.

I want to find the best path, from one location to a set of end locations (the one which can be reached quickest). Also note that every node has the ability to be blocked and and thus not be used as a node in the path.

What would be the most efficient algorithm to solve this problem with?

I have thought of maybe A* but find it difficult to apply the multiple endpoint rule.

Jason Aller
  • 3,541
  • 28
  • 38
  • 38
Mark Jacobsen
  • 341
  • 1
  • 4
  • 14
  • 2
    This SO question might help you, very high quality answer: https://stackoverflow.com/questions/9511118/is-a-the-best-pathfinding-algorithm – Aaron Jan 18 '20 at 12:07
  • Since you have an undirected, equal weights graph, a simple Bread-First Search algorithm will do the job. Alternatively, you can use Dijkstra's algorithm. – Ajay Dabas Jan 18 '20 at 12:08
  • I think this is off topic for Stack Overflow. – AMC Jan 18 '20 at 18:16
  • 1
    For grids, check out things like Jump Point Search and RSR. Also A* works fine with multiple endpoints, just take the minimum of all heuristics. – BlueRaja - Danny Pflughoeft Jan 19 '20 at 19:41

0 Answers0