A* Pathfinding

The Modern Pathfinder

Pathfinding is used extensively in the implementation of artificial intelligence. There are numerous ways to find the optimal path between two points, but the most commonly used are based on the A* algorithm. The methodology is incredibly similar across all heuristics, but the discovery of the shortest path can be widely different.

A* is not the only pathfinding system; Dijkstra in 1959 developed the algorithm which served as the basis for A*. The 1950s were ripe with various algorithms, and indeed, many of the variations between them were subtle. By the end of the decade, Dijkstra beat out algorithms like the Bellman-Ford method and one written only a year earlier by Dantzig. Not until recently was Dijkstra substituted by A*, which uses a more cost-effective heuristic.

How Grid-based A* Works

The built-in pathfinding tools in most modern engines use A* to work, but more optimal solutions have been made to be better suited for a 3d environment. Those variants involve NavMeshes, which slice a “walkable” area into a series of convex polygons, allowing for the AI to move around freely within them. This method chooses which polygonal slices are included in the optimal path, and uses their points to deliver complex, accurate, and dynamic movement. Whether the environment is large or small, this method is both highly effective and scalable. However, grid-based pathfinding is still an incredibly effective tool, and is a lot faster to implement, especially with less complicated projects. This is a higher-level look of pathfinding, so I will not go into the actual implementation of it, aside from showing the pseudocode I implemented in my own version.

Pseudocode for the A* and Dijkstra algorithms. Both are very similar.

Obstacles and environmental pieces are placed on a grid. The goal of the algorithm is to find the best way around these obstacles, which uses the grid as a way of organizing the optimal path called a node. A common grid sizes for 2D games is 32x32, this is important for pathfinding as it dictates the dimensions of that node. The node size can be smaller than 32 but should be divisible by that number, like 2, 4, 8, or 16. This is referenced as a ‘step’. The smaller the step, the more precise the pathfinding is, but requires more calculations.

This can be optimized in many ways:
• A common, but powerful optimization tool is that the AI calculates the distance between the player and itself before initiating the algorithm
• If the player is in range, a vector between the AI and the player is calculated based on the direction the AI is facing, and if that line is interfered by a barrier, assuming that the player is behind a wall, then the AI will not chase the player

The algorithm works by checking the nodes surrounding the AI. To determine which node is the optimal one, it calculates the Scost, which is the node’s distance from the starting AI, and the Ecost, the distance from the destination. Each node is weighted based on the sum of the Scost and Ecost. The expanded nodes, colored orange, are the expanded nodes that were weighted by the algorithm. The node with the lowest weight is chosen as the most promising. The A* heuristic only looks at promising nodes, dramatically decreasing the number of nodes it tests, making the process faster. Based on the promising node with the lowest weight, the process repeats around that node until the destination is reached or returns null, meaning the destination is not reachable. Additionally, if a node is occupied by an obstacle, it ignores it. Of course, promising nodes can change based on the obstacles it discovers, as it determines the fastest path based on what it already knows.

The algorithm returns a 2-dimensional array of x and y coordinates of all the promising nodes leading the AI to the destination.

{{ 120,184 }, { 136,200 }, { 152,200 }, { 168,200 }, { 184,200 }, { 200,200 }, { 216,200 }, { 232,200 }, { 248,216 }, { 264,232 }, { 280,248 }, { 296,264 }, { 312,264 }, { 328,248 }, { 344,232 }, { 360,216 }, { 360,200 }}

To retrieve the x coordinates from the first node, you would call the first position from the array (0), and the first position within that array (0,0). The same would go for retrieving the y coordinate, but retrieving the second position (0,1). In an inelegant form that would be read as x equaling enemy_path[0,0] and y equaling enemy_path[0,1].

As the AI moves towards that first node or the destination moves, as in the player moves, the coordinate position of the first node will update, changing the trajectory of the AI. For smoother movement, programmers use linear interpolation, which in this case creates a closer coordinate between the AI and the first node, making the movement smoother. How that coordinate is divided up is visually interpreted as speed.

Why Not Dijkstra?

Why did we move away from Dijkstra? Dijkstra’s heuristic does not sort the nodes as efficiently due to it weighing only the Scost rather than the sum of Scost and Ecost. This difference is detrimental to the optimized focused industry of video games, as Dijkstra’s method dramatically increases the number of calculated nodes, taking both more time and valuable computational resources to achieve the same result as A*.

Why build your own?

Whether its NavMesh or grid-based pathfinding, writing your own gives you far more control over how your AI functions. The reason some of my projects implemented custom pathfinding was because the built-in tools both had performance problems and could not support the AI my team developed. This is, of course, a case-by-case basis, and most people will be perfectly fine using the robust systems already in place. Regardless, it’s always good to know what logic is going on under the hood.