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