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 for some ideas.
Problem: lots of game maps are expressed as grids, including the Bioware maps available here. A* pathfinding on grids can be wasteful, especially if there are are uniform movement costs. I recommend here 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.
TODO: There’s another optimization I haven’t yet implemented for maps with diagonal walls (the AR______ maps in the dropdown). The diagonal walls could be smoothed out so that every step doesn’t produce a vertex.
TODO: There’s also another geometric optimization that lets us skip many of the edges during pathfinding. I think but I am not sure that if you’ve just reached a corner with the wall on the right and the open area on the left, the next edge should be to the right and we can prune the edges to the left. (and vice versa with left/right switched.) I don’t know if this is a big win. I need to investigate this, then write it up.
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