How I Built A* Pathfinding for Enemy AI in a 2D Platformer
In this article we will be seeing about pathfinding and how I implemented A* algorithm in Unity to allow an AI character to navigate through the game world. We will also walk though a small project that demonstrates how the algorithm works in practice.
Note: There are many excellent resources that explore the A* algorithm in much greater depth than this article. My goal here is not to present the definitive implementation, rather than trying to cover every aspect of the algorithm, this article focuses on how I understood the concepts and applied it in my Unity project. The implementation is intentionally kept simple to make the algorithm easier to follow, and there are many ways it could be optimized depending on the project’s requirement.
In simple terms Pathfinding is the process of finding the shortest or most efficient route between two points in a space.
At the core concept pathfinding method searches a Graph or Grid by starting from a given node and exploring neighbour nodes until it reaches the goal node, generally used with the intent of finding the cheapest route with the given enough time, or other methods, would tend the reach the destination sooner.
So Why Use Pathfinding?
We use pathfinding in game development to allow AI controlled characters or object to move intelligently through the game world to reach a target or goal while avoiding any obstacles. Instead of simply making the character/Object to move in straight line or pre programmed path to the goal, which could leads to unexpected patterns or behaviour. A pathfinding algorithm calculates a valid route that the character can follow in the game world. This makes the character movement appear natural and believable, allowing NPC’s to follow after any target, patrol areas, escape danger or navigate complex environments etc.
Pathfinding is not limited, it is also used anywhere a system need to find an efficient route from one location to another. its a simple idea that to compute best path based on factors such as distance, time etc.
Some common real-world applications include:
- GPS and other Navigation systems
- Robotics.
- Autonomous Vehicles.
- Drone Navigation and much more.
Popular pathfinding algorithms include Dijkstra’s Algorithm, A*, Breadth-First Search (BFS) and Depth First Search (DFS). Each algorithm has its unique characteristics, making them suitable for specific scenarios.
A* Pathfinding:
A* algorithm is one of the best and popular technique out there used in pathfinding and graph traversals. It is an best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific node which lets say a starting node of a graph, it aims to find a path by going through the nodes in the graph to the given goal node having the smallest cost lets say like: least distance travelled / shortest time etc.
Imagine an enemy trying to reach the player’s position. Between them is a platform blocking the direct path. Rather than moving straight forward the player and getting stuck, A* searches the surrounding nodes and finds a valid route around the obstacle.
Lets see how A* helped me to achieve the pathfinding in my game:
Creating the Navigation Grid:
The first thing is to divide the scene into grid. Unity’s grid component provides an easy way to organise the game scene into equally sized cells
Generating Nodes:
Once the grid is available, I use the TileMap bounds (AABB — Axis Aligned Bounding Box) to determine which cells contain platforms. For every valid cell, I generate a node that will later be connected to neighbouring nodes.
The path will be discovered by figuring out which neighbouring node the enemy should take to get from its position (point A) to the playersposition (point B). So once the path is created the object moves from node to node until it reaches the goal node.
Before we look into how the search algorithm works, let me show how I was able to place the nodes and made the connect:
- First I have created the node as a gameObject with script attached to it, which contains the gScore, hScore, and fScore (we will discuss about this further in this article), and the connection types to distinguish the connection between the nodes, and a nested class for storing the target node and connection type in a list.
public class Node: MonoBehaviour
{
public float gScore;
public float hScore;
public float FScore()
{
return gScore + hScore;
}
public enum ConnectionType
{
walkable,
jump,
fall
}
public Node cameFrom;
public ConnectionType connectionType;
public class NodeConnection
{
public Node targetNode;
public ConnectionType type;
public NodeConnection(Node node, ConnectionType connectiontype)
{
targetNode = node;
type = connectiontype;
}
}
public List<NodeConnection> connectionsList = new List<NodeConnection>();
}- Then in the Generate Node script which is a component of the TileMap, handles the node placement for each and every cells in the tileMap where the object can move. We loop through all the cells in the tileMap and instantiate the nodes by checking the condition if there is no Tile above the current cell then we place the node there, and add it to a list.
BoundsInt bounds = _platformTileMap.cellBounds;
for (int x = bounds.xMin; x < bounds.xMax; x++)
{
for (int y = bounds.yMin; y < bounds.yMax; y++)
{
Vector3Int currentCellPos = new Vector3Int(x, y, 0);
//We are checking if the cell is present
if(_platformTileMap.HasTile(currentCellPos))
{
Vector3Int aboveCell = new Vector3Int(x, y + 1, 0);
// we are checking is there a cell above the current cell if not we are gonna spawn the node there.
if(!_platformTileMap.HasTile(aboveCell))
{
Vector3 worldPos = _platformTileMap.GetCellCenterWorld(aboveCell);
Node node = PoolManager.SpawnObject(_nodePrefab, worldPos, Quaternion.identity, PoolManager.PoolType.Nodes);
node.name = "WalkableNode " + "_ " + walkableNodeCount.ToString();
walkableNodeCount++;
//Add to the node list
nodeList.Add(node);After that we have to create the connection by determining which nodes should be connected, we need to compare each node with every other node in the graph. we do this using a nested for loop.
private void CreateWalkableConnection()
{
for (int i = 0; i < nodeList.Count; i++)
{
Node nodeA = nodeList[i];
for(int j = i + 1; j < nodeList.Count; j++)
{
if (j == i) continue;
Node nodeB = nodeList[j];
//Get the position of the nodes
Vector3 nodeAPosition = nodeA.transform.position;
Vector3 nodeBPosition = nodeB.transform.position;
//Get the horizontal and vertical distance from both nodes
float horizontalDistance = Mathf.Abs(nodeAPosition.x - nodeBPosition.x);
float verticalDistance = Mathf.Abs(nodeBPosition.y - nodeAPosition.y);
//Now we connect the nodes as walkable by checking the condition as if the distance is lesser thatn 1.0 / 0.1(vertical)
if(horizontalDistance <= 1.0f && verticalDistance < 0.1f)
{
nodeA.connectionsList.Add(new Node.NodeConnection(nodeB, Node.ConnectionType.walkable));
nodeB.connectionsList.Add(new Node.NodeConnection(nodeA, Node.ConnectionType.walkable));
}
}
}You would have noticed that the inner loop starts at i + 1 instead of 0. This is important because it prevents us from comparing the same pair twice. For example: if we have already compared Node 1 with Node 2, there is no need to later compare Node 2 with Node 1. Both comparison represent the same pair of node.
Once we have a pair of nodes (Node A and Node B) we calculate the horizontal and vertical distance between each nodes, if they are close enough to each other we consider them adjacent and create a walkable connection.
Get Vinish Kumar’s stories in your inbox
Join Medium for free to get updates from this writer.
Likewise we will also add other connection such as fall and Jump the same as we did to the walkable connection, but for this i have created separate node list called EdgeNode list to store the edge nodes which is placed at end of the tile row, if there is no cell at each corner then we will place the nodes, the reason we have added edge nodes is that when the NPC’s or object have jump behaviour the node placement might miss-align and cause unwanted behaviour that's why we have added it.
Before moving on with the algorithm, lets look into fScore, gScore and hScore:
- G Score: gScore represents the actual movement cost from the starting node to the current node.
- H Score: hScore (Heuristic score) is an estimate of the remaining cost from the current node to the goal node. So unlike gScore this is not the exact value its a prediction.
- F Score: fScore is the value is A* uses to decide which node to explore next, f = g + h . In the algorithm we calculate the fScore for every neighbouring node and always selects the node with lowest fScore to continue the search.
Now lets look into the A* pathfinding algorithm. This is a simplified implementation of the algorithm which i tailored as per the needs. While this algorithm doesn't include every optimization found in the production implementations.
public List<Node> GeneratePath(Node StartNode, Node GoalNode)
{
if (StartNode == null || GoalNode == null) return new List<Node>();
//Reset all the values so that when the new node search starts all the old value can erased
foreach(var node in AllNodesList)
{
node.cameFrom = null;
node.gScore = float.MaxValue;
node.hScore = 0;
}
if(StartNode == GoalNode)
{
return new List<Node> { StartNode };
}
//Initialize the Start Node
StartNode.gScore = 0;
StartNode.hScore = Vector2.Distance(StartNode.transform.position, GoalNode.transform.position);
//here we create a openSet to store the nodes
List<Node> openSet = new List<Node> { StartNode };
while(openSet.Count > 0)
{
int lowestFScore = default;
for (int i = 1; i < openSet.Count; i++)
{
if (openSet[i].FScore() < openSet[lowestFScore].FScore())
{
lowestFScore = i;
}
}
Node currentNode = openSet[lowestFScore];
openSet.Remove(currentNode);
if(currentNode == GoalNode)
{
List<Node> path = new List<Node>();
Node temp = currentNode;
while(temp != null)
{
path.Add(temp);
if(temp == StartNode)
{
break;
}
temp = temp.cameFrom;
}
path.Reverse();
return path;
}
foreach (Node.NodeConnection connection in currentNode.connectionsList)
{
Node connectedNode = connection.targetNode;
float heldGScore = currentNode.gScore + Vector2.Distance(currentNode.transform.position, connectedNode.transform.position);
if(heldGScore < connectedNode.gScore)
{
connectedNode.cameFrom = currentNode;
connectedNode.gScore = heldGScore;
connectedNode.hScore = Vector2.Distance(connectedNode.transform.position, GoalNode.transform.position);
if(!openSet.Contains(connectedNode))
{
openSet.Add(connectedNode);
}
}
}
}
return null;
}The GeneratePath() method is responsible for finding the shortest path between two nodes. It begins with the starting node and explores the neighbouring nodes and continues searching until reaches the goal node.
if (StartNode == null || GoalNode == null) return new List<Node>();Before starting the search we are verifying that both the start node and goal node exist, if either one is missing then there is no path to calculate, so we return a empty list.
//Reset all the values so that when the new node search starts all the old value can erased
foreach(var node in AllNodesList)
{
node.cameFrom = null;
node.gScore = float.MaxValue;
node.hScore = 0;
}This is the important part because every nodes stores the cost and its parent node (cameFrom) for each search. So we are resetting the costs and parent Node before starting the new search.
you would observed that the GScore is set to float.MaxValue which is nothing but we are making it infinite. At the beginning of the search, we assume every node is infinitely far away until we discover a shorter path to it.
//Initialize the Start Node
StartNode.gScore = 0;
StartNode.hScore = Vector2.Distance(StartNode.transform.position, GoalNode.transform.position);When the search starts we are initializing we set the gScore to 0 as the search starts from the starting node and the cost to reach it is zero. Then calculate the heuristic value which estimates the remaining distance to the goal by getting the distance between two nodes.
//here we create a openSet to store the nodes
List<Node> openSet = new List<Node> { StartNode };The Open Set contains every node that has been discovered but still needs to be explored. Initially it contains only the starting node because that is where the search begins.
while(openSet.Count > 0)
{
}this is the core of this algorithm, the algorithm continues searching as long as there are unexplored nodes remaining in the open set.
if(currentNode == GoalNode)
{
List<Node> path = new List<Node>();
Node temp = currentNode;
while(temp != null)
{
path.Add(temp);
if(temp == StartNode)
{
break;
}
temp = temp.cameFrom;
}
path.Reverse();
return path;
}Once the goal node is selected as the current node, the search is complete. However we still need to reconstruct the path that led to it. During the search every node remembers which node it was reached from using the cameFrom reference. Starting from the goal node, we repeatedly follow these reference backwards until we arrive at starting node.
Since this process builds the path in reverse order(Goal — Start) we reverse the list before returning it so that the final path runs from Start — Goal.
foreach (Node.NodeConnection connection in currentNode.connectionsList)
{
Node connectedNode = connection.targetNode;
float heldGScore = currentNode.gScore + Vector2.Distance(currentNode.transform.position, connectedNode.transform.position);
if(heldGScore < connectedNode.gScore)
{
connectedNode.cameFrom = currentNode;
connectedNode.gScore = heldGScore;
connectedNode.hScore = Vector2.Distance(connectedNode.transform.position, GoalNode.transform.position);
if(!openSet.Contains(connectedNode))
{
openSet.Add(connectedNode);
}
}
}If the current node is not the goal, then we examine each of its connected neighbour nodes. we calculate the cost of travelling from the start node to the neighbour node through the current node. If travelling through the current node produces a lower cost than any previously known route we update the neighbour’s information:
- Store the current node as its parent (cameFrom)
- update its new GScore
- Recalculate its Heuristic(H Score)
- and we add it to the open set if it isn’t already waiting to be explored.
Note: Its important to note that the GeneratePath() isn’t called directly by the player or the pathfinding manager itself. Instead, it is requested by the enemy AI. As long as the enemy remains active and also the player is active in the scene, it continuously generates and updates the path towards the target. The complete source code is available in the accompanying Unity project that i have attached below, where you can trace the execution flow from the enemy script to the pathfinding system.
Recommended Resources:
I recommend this source to get better understand on A* algorithm:
https://wiki.jmonkeyengine.org/docs/3.4/contributions/_attachments/Astar.pdf
If you’d like to gain deeper understanding of A*, graph theory or explore more advanced implementation , I highly recommend the following resource
You can access the project using the link below:
If you’d like to see the pathfinding system in action, you can play the prototype using the link below:
