Warning: INCOMPLETE PAGE ; I lost interest in this and never finished. I realized that for my own game projects, I’m not going to need this. I suggest looking instead at the academic literature; see this paper[1] for some ideas. Also look at this slide deck[2].
Problem: lots of game maps are expressed as grids, including the Bioware maps available here[3]. A* pathfinding on grids can be wasteful, especially if there are are uniform movement costs. I recommend here[4] that people consider visibility graphs or navigation meshes to construct pathfinding graphs for A*. JPS+ is one algorithm that constructs something like a pathfinding graph, but doesn’t use regular A*. On this page we’re going to explore how pathfinding graphs can be used with standard A*.
The simplest thing we can do with a grid map is to make each of the locations into an A* pathfinding node, with approximately 4 times that many edges:
However, A* will run much faster if we use only these key locations connected to each other. There are possible edges, but only edges that don’t pass through walls:
A further optimization is to include only the edges that might ever be used in the shortest path. The edges we removed aren’t needed because they’re a longer version of a nearby edge.
The diagonal walls (numbered maps) produce too many exterior corners. TODO: smoothed out these walls so that every step doesn’t produce a vertex, or use a different algorithm for maps with lots of diagonal walls.
TODO: There’s also another geometric optimization that lets us skip many of the edges during pathfinding. If you’ve reached a corner and the obstacle is on the right, then we only have to consider the edges that bend right from this corner. This reduces the number of edges we have to consider. See the “culling cusped edges” section of this page[5] for the intuition, or see Chapter 3.10 of Game Programming Gems 2 for a generalization for any polygons. I haven’t yet written up the version for grids and corners.
TL;DR: we can reduce the graph nodes down to ; we can reduce the approx graph edges down to . With a much smaller pathfinding graph, A* should run much faster.
TODO: run some benchmarks