Third time’s a charm they say, and as I’ve talked about pathfinding twice before (in Don’t follow the shortest path! and Aiding pathfinding with cellular automata) I thought I’d charm everyone with a third pathfinding article. This time I’ll talk about how we can reduce the memory consumption on a commonly used pathfinding algorithm by about a magnitude!
Those of you wacky enough to have taken EE instead of CS, might know breadth-first search applied to pathfinding on a grid as Lee’s algorithm [Lee61]. We also sometimes see this referred to as the wavefront or flood-fill pathfinding algorithm. Odds are you’re quite familiar with it.
An application of Lee’s algorithm is shown below, with the depth of the breadth-first search written into the cells (shown on the left, with start and goal highlighted) along with an optimal path as returned from the algorithm (on the right, with the path in golden yellow):
The optimal path is obtained by starting at the goal cell and finding the neighboring cell with the smallest value, then from that cell we go to its neighboring cell with the smallest value, and so on until we reach the start cell.
For an MxN grid one would think we would need to store an integer per cell, holding log2(M*N) bits, in order to represent the cell state. But one would think wrong! In fact, only two(!) bits per cell are needed, as noted by Akers [Akers67].
Akers first noted that we don’t really need to have labels unique to every cell; we only need labels that are unique between a cell and its preceding and succeeding neighboring cells along any possible path. As such, it would be possible to simply label the cells 0, 1, 2, 0, 1, 2, … along the BFS path. As we also need to represent empty and filled cells we would in this encoding need 5 values or 3 bits to encode all cell values.
From there, Akers observed that we don’t actually need three values, we can instead label the cells 0, 0, 1, 1, 0, 0, 1, 1, … as this encoding (using only two values) still allows us to infer unique labels for three successive cells along a path. Along with the state labels for empty and filled cells, this encoding uses only 2 bits to encode all states!
The grid below shows Akers’ algorithm applied to the same configuration as before:
Here I’ve considered the start node as being labeled 0. In general, we can turn an implementation of Lee’s algorithm into Akers’ algorithm by rather than storing the current search depth D into the grid cell instead storing ((D >> 1) & 1).
Extracting the optimal path once a goal node is reached is done analogous to in Lee’s algorithm, but now we step to the next neighboring cell which has the appropriate value in the reverse of the sequence 0, 0, 1, 1, 0, 0, 1, 1, ….
Traditionally Lee’s algorithm (and Akers’ modification) were used to route paths on printed circuit boards. Today there’s a lot of published algorithms for this routing problem, and anyone pretending to be an AI expert for games should probably be familiar with not just Akers’ algorithm but the ideas behind a few other of these EE path-routing algorithms. A good overview of some is given in Prof. Hai Zhou’s lecture notes. Several relevant papers can also be found at the ACM and IEEE digital libraries.
- [Lee61] Lee, C. Y. “An algorithm for path connections and its applications,” IRE Transactions on Electronic Computers, vol. EC-10, pp. 346-365, September 1961.
- [Akers67] Akers Jr, S. B. “A modification of Lee’s path connection algorithm,” IEEE Transactions on Electronic Computers, vol. EC-16, pp. 97-98, February 1967.