Older article from Voxel Entertainment; originally written by Jeremy Bridon.

A* and D* are well known path-planning algorithms. Path planning is the process of finding the “best” path from one location to a target location. “Best” is defined by the programmer, usually as either the shortest path or the cheapest path or some other variable. Path planning is critical to any sort of unit movement for any real-time strategy game: units following a straight line might collide into different objects, thus a complex path may be needed. Other approaches exist, such as flocking algorithms, that treat each unit as a particle and simulate pseudo-natural group movement behaviors. The later type of algorithm is more heuristic, are do not necessarily return you a correct path.

I originally learned about A* and D* through my own robotics research applications. A* is a simple breadth-first search algorithm, while D* is a dynamic programming algorithm. I was involved with an international robotics competition to have a robot drive through unknown terrain from a starting location to a series of way-points. The search space is not only huge (hundreds of square meters the robot has to drive around) but the arena was completely unknown at run-time. The robot fills in its “known world” over time, as it discovers obstacles, while driving to a goal.

During each “known world” update (we queued up sensor readings into burst-writes for performance), we actually only update the node/edge values within our D* map. For added performance (this code was never deployed, but was developed and simulated) we removed nodes that were surrounded by obstacles as well as only added new nodes if the robot really thought there was an obstacle. From there, the algorithm didn’t need to run through all possible paths like A* does (hence the dynamic programming aspect), but only updates the paths associated with the node/edges that have been changed.

This is a very subtle difference, and frankly the performance gain from our own D* implementation wasn’t huge, but when we ran simulations of worlds that had overly complex obstacles (fences, clustered poles, etc..), D* outperformed by far! Simply: A* is great for well-defined static worlds, D* is great for dynamic changing worlds. That’s it! I think A* seems to best fit your needs since maps are very well defined; any needed path planning data could just be pre-calculated.

V*, a new path planning approach faster than D*, is being developed at Penn State. This approach uses language theory mechanics and has a theoretical lower constant than A* and D*, which are all bounded by O(n^2). Who knows if maybe in the future we find a linear or constant-time search algorithm?