Timeline for How does A* pathfinding work?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18, 2011 at 15:09 | comment | added | amitp | To add to Joe's explanation: A* will find the path to all points too, if you let it, but in games we usually want to stop early. A* works like Dijsktra's algorithm, except the heuristic helps reorder the nodes to explore the most promising paths first. That way you usually can stop even earlier than with Dijkstra's algorithm. For example, if you want to find a path from the center of the map to the east side, Dijkstra's algorithm will explore equally in all directions, and stop when it finds the east side. A* will spend more time going east than west, and get there sooner. | |
| Apr 16, 2011 at 18:53 | comment | added | user744 | This is not really an accurate description of the difference between A* and Dijkstra. It's true that Dijkstra solves single-source to all points, but when used in games it's usually cut off as soon as you find a path to the goal. The real difference between the two is that A* is informed by heuristic and can find that goal with fewer branches. | |
| Jul 14, 2010 at 20:44 | history | answered | Karantza | CC BY-SA 2.5 |