Sebastian Lague A* Tutorial Series - Algorithm Implementation - Pt. 03

November 20, 2019

A* Tutorial Series

Pt. 03 - Algorithm Implementation

A* Pathfinding (E03: algorithm implementation)

Link - Tutorial

By: Sebastian Lague

Intro:

Since these sections are very coding intensive, I just setup a breakdown into the different classes that are worked on. I try to discuss anything done within the class in that class's section here. As should be expected, they do not continuosly do a single section and move to the next, they jump back and forth so that the references and fields make more sense for why they exist, so I try to mention that if needed.

Pathfinding

This class begins to implement the psuedo code logic for the actual A* algorithm. It starts with a method, FindPath, that takes in two Vector3 values, one for the starting position and one for the target position. It then uses our NodeFromWorldPoint method in AGrid to determine which nodes those positions are associated with so we can do all the work with our node system.

It then creates a List of nodes for the openSet and a HashSet of nodes for the closed set, as seen in the psuedo code. It is around here that they begin to update the Node class since it will need to hold more information.

The next part is the meat of the algorithm, where it searches through the entire openSet to determine which node to explore further (by using the logic of finding the one with the lowest fCost, and in the case of ties, that with the lowest hCost). Once found, it removes this node from the openSet and adds it to the closedSet. It is mentioned that this is very unoptimized, but it is one of the simplest ways of setting it up initially (they return to this for optimization in future tutorials).

Continuing to follow the psuedo code, they go through the list of neighbors for the currentNode and check to see if any are walkable and not already in the closedSet to determine which to further explore.

Here they create the distance calculating method that will serve as the foundation for finding the gCost and hCost. This method, named GetDistance, takes two nodes and returns the total distance between them in terms of the grid system. Just to reiterate, it returns an approximated and scaled integer distance value between two nodes. Orthogonal moves have a normalized distance of 1, where diagonal moves are then relatively the sqrt(2), which is approximately 1.4. These values are then multiplied by 10 to give their respective values of 10 and 14 for ease of use and readability.

If it is determined that the neighbor node should be evaluated, it calculates the gCost of that neighbor from the current node by adding the distance to the neighbor from the currentNode to the currentNode gCost. It then checks if this is lower than the neighbor node's current gCost (so they found a cheaper route to the same node) or if neighbor is not in the openSet (which means it has never been evaluated, so has no gCost to compare). If these criteria are met, it sets the gCost of the neighbor to this determined value, and calculates the hCost using the new GetDistance method created between the neighbor node and the targetNode.

It finally sets that neighbor node's parent as the currentNode, and checks if the neighbor was already in the openSet. If not, it adds this node to the openSet.

The RetracePath method was created, which determines the path of nodes to follow once the target has finally been reached. Starting with the endNode (target position), it cycles through each node's parent by continually changing the checked node to the current node's parent until it gets back to the startNode, and adds them to a list named path. Finally, it reverses the list so they are in the proper order matching the actual object's traversal path (since doing it this way effectively gives you the list of nodes backwards, starting with the end).

Node

They add the gCost, hCost, and fCost as public ints here finally. The fCost is actually just a getter function that returns gCost + hCost. This is a nice setup that provides some extra encapsulation as fCost will never be anything else so it may as well only return that sum whenever it is called.

Later they also add ints gridX and gridY, which are references to their indices in the overall grid array. This helps locate them, as well as their neighbors, more easily in later code.

A field is created of the type Node named parent to hold a reference to a parent node. This serves as the link between nodes to give a path to follow once the final destination has been reached. As the lowest fCost nodes are found, they will create a chain of parent nodes which can be followed. This is done with the RetracePath method in Pathfinding.

AGrid

They added the GetNeighbors method here. It takes in a node, then returns a list of nodes that are its neighbors. It effectively checks the 8 potential areas around the node with simple for loops spanning -/+ 1 in the x and y axes relative to the given node. It skips the node itself by ignoring the check when x and y are both 0. It also makes sure any potential locations to check exist within the grid borders (so it does not look for nodes outside of the grid for nodes on the edges for example).