Pathfinding Beyond Maps: Lessons from Gaming AI for Hyperloop Design

While we may be using A* to design an optimal Hyperloop route, A* search algorithms can be used for so much more. While brainstorming what day-to-day things I interact with that use A*, I thought about video games. I thought about how non player characters (NPCs) often have to move from one point to another, and was intrigued by how this was done.

That is when I came across A*-based Pathfinding in Modern Computer Games by Xiao Cui and Hao Shi. The paper mentions how with the rising popularity of video games, it’s become important to optimize how NPCs path find. This optimization is done by optimizing the implementation of the A* search algorithm in different ways, and the paper goes over 4 popular optimizations.

The first popular optimization is optimizing the search space. Every game environment has an underlying data structure for the AI characters to use, and by optimizing the underlying data structure you can optimize the A* algorithm that is done (because the A* algorithm has less work to do). We can implement this optimization when designing our A* algorithm, by thinking about what data structure would be most optimal for us to represent the different roads, rivers, environmentally protected areas, etc.

The second popular optimization is Hierarchal Pathfinding A* (HPA*). This involves breaking up a search space into multiple levels, the paper brings up a great real-world example, considering the path between Los Angeles and Toronto. Finding the most optimal path of all roads between the two cities would be way too expensive. Instead, you can abstract the map to the city level. Find the most optimal route of cities, and then within the cities find the most optimal map of roads. You could even apply another layer of abstraction by finding the most optimal route of neighborhoods within cities. We could implement this optimization when designing our A* algorithm, as we are dealing with real-world maps and cities as well.

The third popular optimization is Navigation Mesh (NavMesh). NavMesh is used for AI path finding in 3D worlds. “A NavMesh is a set of convex polygons that describe the ‘walkable’ surface of a 3D environment.” Think of it like a floor plan that shows where the AI can actually move, with polygons separating the different obstructions. An AI starts in a polygon that isn’t the same as the polygon that the destination is in, and keeps moving in polygons towards the polygon that the goal is in. Once in the destination polygon, the AI can move in a straight line to the goal. We could use a similar idea when considering our environmentally protected areas (which for us are “not-walkable”, because under no conditions is the route allowed to go through that), but we won’t be separating our map into polygons so NavMesh isn’t applicable for us.

The final optimization is memory optimization. A* requires a large amount of memory to operate, so it is vital to optimize the amount of memory required. One very helpful aspect of this that I believe we should implement in our algorithm is something also found in Iterative Deepening A* (IDA*). The idea behind it is to create a threshold equal to the heuristic at the start node. Then, the neighboring nodes are expanded until either a solution is found that scores below the threshold, or no solution is found. If no solution is found, then the threshold is incremented. This is done until you find a solution. We should implement this, as our heuristic takes up more than just the euclidean distance so we need another way to limit which nodes are visited.

The paper then goes on to list how A* pathfinding has been used in many popular games, such as Age of Empires, Civilization V, but is more optimal in FPS (first person shooter) games such as Counter-Strike which have less units moving around. Our A* algorithm won’t be taking multiple units into account, so there won’t be any dynamic change in the paths. By taking into account the four popular optimizations the paper talks about, we can heavily improve our A* algorithm’s complexity and memory usage.