Pathfinding algorithms on grids #
The usual pathfinding algorithms I use — Breadth First Search, Dijsktra's Algorithm, A* — run on graphs. In my previous post I described how grids can be viewed as graphs. Most of the time, pathfinding on grids is fine. However, if you need more performance, grids contain additional structure that standard graph algorithms don't take advantage of. I wrote up some notes about this, either transforming your grid into a smaller graph, or modifying the pathfinding algorithm to harness the structure of grids. It's not something I've had to do in my own projects so if you have additional references or words of advice, I'd love to hear how I can improve that page.
Labels: pathfinding
Graph theory for pathfinding #
While updating my pathfinding pages, I realized that although I cover graph-based pathfinding algorithms, I don't actually explain what graphs are or why we use them. So I wrote a short tutorial on graphs and grids.
Labels: grids , pathfinding