Over the past few years I’ve been writing a new set of pages about pathfinding in games. This page wasn’t originally meant to be externally visible but it is, so I’m leaving it up for anyone who explores my site by editing URLs. Here are the pages and their status:
- A* Introduction including Breadth First Search and Dijkstra’s Algorithm (done) + Implementation supplement (done) and making-of (behind the scenes) and main-loop (unfinished)
- Differential heuristics (on hold) - with this one trick you can make A* significantly faster! Just ten lines of code!
- Clarkson optimization (done, but not promoted) - millisecond pathfinding on an 800x800 grid, live demo in browser
- Distance to any (done, but not promoted or linked)
- Grid algorithm optimizations (done, but not promoted)
- Visibility graphs (on hold) - reducing a grid down to a much smaller pathfinding graph, with demos running on Baldur’s Gate and Dragon Age maps
- Introduction to graphs (done)
- Tower Defense and Breadth First Search (done) + Implementation supplement (done)
- Reprioritization for Dijkstra and A* is not necessary! This is a complex operation with some priority queues, so when I learned that it wasn’t necessary, I was able to make my code simpler.
- All-pairs for finding choke points (done, but not promoted or linked)
This tweet shows the topics I wanted to cover here.