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)
- making-of (done) - behind the scenes look at how the pathfinding pages were originally implemented in 2013, but doesn’t match the current implementation as of 2018
- main-loop (unfinished) - an attempt to reverse the flow, so that instead of the reader providing the input and the page running the algorithm, the page provides the input and the reader runs the algorithm
- Differential heuristics (on hold) - with this one trick you can make A* significantly faster! Just twenty lines of code! this is an idea I like but I haven’t found a good way to explain it - see the demos
- Heuristics (on hold) - I was trying to understand the properties of heuristics that make them good or bad
- Clarkson optimization (done, but not promoted) - millisecond pathfinding on an 800x800 grid, live demo in browser, uses a third party library and doesn’t explain the algorithm
- Distance to any (done) - various things you can do by having more than one start point
- Early exit (done) - various things you can do by having a goal that isn’t a single location
- Grid algorithm optimizations (done, but not promoted)
- Visibility graphs (abandoned) - 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) - “flow fields” are the gradient operator ∇ applied to the “distance field”
- 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) - calculating paths from all points to all other points, then analyzing the map to count how often each tile is used in a path, with interactive demo
- Circular obstacles[1] (done) - you don’t have to store the entire graph in memory; you can generate it dynamically while A* is running
These are other topics I want to cover, but it will take some time to make interactive versions of all of them: