Pathfinding is the load-bearing subsystem behind almost every moving character in a 2D game — the ghosts in Pac-Man, units in an RTS, or an NPC weaving around obstacles. When you are creating your first 2D game, the A* algorithm is the standard tool for finding the shortest route from source to destination without walking through walls.
A* ensures a character avoids obstacles like blocks, cars, rivers, and walls while reaching the destination along the shortest available path.
RTS games like Warcraft III commonly rely on A* variants for unit movement, where each unit must not only reach its destination by the shortest path but also route around castles, huts, dungeons, and enemies.
A* algorithm (pronounced A-star)
The A* algorithm is one of the most widely used optimal pathfinding algorithms, balancing search speed with a guarantee of finding the least-cost path from the source node to the goal node — provided the heuristic is admissible. An admissible heuristic is one that never overestimates the true cost of reaching the goal from a given node — this is the property that lets A* guarantee an optimal path. A* was first published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute. (A node can be hexagon, square or circle, etc.) See Amit Patel's introduction to A* for an interactive walkthrough.
In the gaming world, a node graph is a map of your gaming world, and the path that costs the least is the shortest path; A* traverses a node graph and finds the path that costs the least.
A* combines the guaranteed optimality of Dijkstra's algorithm with the heuristic-guided efficiency of Greedy Best-First Search. Unlike uninformed searches such as DFS and BFS, A* uses a heuristic to pick the most promising next node. Unlike Greedy Best-First Search — which is fast but not guaranteed to find the shortest path — A* also accounts for the actual cost of the path traveled so far, which is what keeps its result optimal.
The cost function
The A* cost function F = G + H combines the actual travel cost (G) from the start with the estimated remaining cost (H) to the goal.
F = G + H
- G is the cost that is required to reach a particular node from the source node.
- H often termed the Heuristic Value. It is the estimated cost from one square on the grid to the other square, which is the goal on the grid. H being heuristic, can never be perfect and is usually based on assumptions.
Here we implemented the Euclidean distance for the cost function. The Manhattan and the Chebyshev functions are also shown in case required.
The following Python implementation shows the heuristic function; Euclidean is used here, with Manhattan and Chebyshev shown as comments.
def estimate(self, xDest, yDest):
"""
Estimation function for the remaining distance to the goal.
"""
dx = xDest - self.x_position
dy = yDest - self.y_position
# Euclidian Distance
d = math.sqrt(dx ** 2 + dy ** 2)
# Manhattan distance: d = abs(xd) + abs(yd)
# Chebyshev distance: d = max(abs(xd), abs(yd))
return d
A quick opinion: for most tile-based 2D games where diagonal movement is disabled, Manhattan distance is a better default heuristic than Euclidean — it matches the movement model exactly, which keeps the heuristic tight and admissible.
Let's look at the following example:
Assume that the graph or table above is a game grid where our protagonist needs to move from the source node of the grid to the goal node.
class Node:
"""
for handling the individual nodes or spaces in the given map
"""
def __init__(self, coordinates, distance, priority, possible_directions):
if isinstance(coordinates, Shift):
self.x_position = coordinates.change_in_x
self.y_position = coordinates.change_in_y
elif isinstance(coordinates, Node):
self.x_position = coordinates.x_position
self.y_position = coordinates.y_position
else:
self.x_position = coordinates[0]
self.y_position = coordinates[1]
self.distance = distance
self.priority = priority
self.possible_directions = possible_directions
def __lt__(self, other):
"""
comparison method for priority queue
"""
return self.priority < other.priority
def estimate(self, xDest, yDest):
dx = xDest - self.x_position
dy = yDest - self.y_position
d = math.sqrt(dx ** 2 + dy ** 2)
return d
def updatePriority(self, xDest, yDest):
self.priority = self.distance + self.estimate(xDest, yDest) * 10
def nextMove(self, d):
if self.possible_directions == 8 and d % 2 != 0:
self.distance += 14
else:
self.distance += 10
How A* traverses a grid
A* traverses a grid by repeatedly picking the open-list node with the lowest F cost, moving it to the closed list, and expanding its neighbors — continuing until the goal node is selected for expansion.
Calculating F, G, and H on a real grid
Let's consider that every block to the left, right, top, and bottom of the selected (parent) node is at a distance of 1 unit. That means that each block is at a diagonal distance of √2 ≈ 1.4142.
To make things easier, multiply each value by 10, giving costs of 10 for adjacent nodes and approximately 14 for diagonal nodes (since 10 × √2 ≈ 14.14, rounded to 14).
Let's make 2 lists of open and closed nodes. When a node is selected for expansion (popped from the open list because it has the lowest F value), it is moved to the closed list. The open list contains all nodes that have been generated as neighbors but not yet expanded — many of these will never end up on the final path.
Assume that our protagonist is at the location source. Every block surrounding the location source has a certain F cost, which is obtained by summing G and H.
For example, a block diagonally opposite to the source and marked in red has a G value of 14 (the diagonal step cost). If the goal is roughly 3.8 units away in a straight line, the scaled H value is about 38, giving F = G + H = 14 + 38 = 52. You can compute the values for all other blocks the same way.
After we have the cost of all the blocks, select the block which has the lowest cost. In this case, F=52 and mark it as closed.
def a_chosen_direction(x, possible_directions):
return (x + possible_directions // 2) % possible_directions
def generate_path(possible_directions, dir_map, dx, dy, xA, yA, x, y):
path = ""
while not (x == xA and y == yA):
j = dir_map[y][x]
c = str(a_chosen_direction(j, possible_directions))
path = c + path
x += dx[j]
y += dy[j]
return path
Repeat the entire process with all the open nodes and select the block with the lowest F value as you head towards your goal.
Once you reach the goal, the path traversed is the lowest possible path for a given matrix.
Handling obstacles in the closed list
Assume that, in a game, the section in black is the area which cannot be traversed by the player.
def collision_with_obstacle(x_y_shift, the_map, closed_nodes_map):
return any((
the_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 1,
closed_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 1
))
Select the Source node and calculate the F cost of all its surrounding nodes. Now select the node with the smallest value, which in this case is 48. Then repeat the process.
What if two nodes have the same values, like F=48? In such cases, select any one of them and proceed.
Summary of the A* algorithm
- Select the starting point and put it in the open list.
- Find the F cost to the current node.
- Mark it in the closed list.
For each of the 8 nodes adjacent to the current node:
If the node is in the closed list or cannot be walked through, then ignore it.
- If it is not open, then put it on the open list and find the G, H, and F values for it.
- If it is in the open list, then check if the path has a better cost and make it the parent node.
- Stop when the target node is selected for expansion from the open list (the returned path is optimal provided the heuristic is admissible), or when the open list is empty (no path exists).
At this point, you should have a decent conceptual understanding of how the A* pathfinding algorithm can be adapted to a platform. This article is a beginner's guide of sorts.
Remember that A* finds the optimal path only when the heuristic is admissible (never overestimates the true remaining cost). The graph search is only one piece of the puzzle. A* does not handle things like object movement, map changes, etc. The Node, estimation, and path-generation snippets above together form a working reference implementation you can drop into a Python project.
A good next step: take the reference implementation above and swap the Euclidean heuristic for Manhattan distance on a 20×20 grid, then compare how the resulting paths differ. If you're curious about how AI-driven agents choose moves in games, see game playing programs for a broader look, or explore how BFS underpins GPS navigation for another practical pathfinding example.
For more on foundational algorithms, see the top algorithms and data structures every programmer should know.
Frequently asked questions
What is the A* algorithm used for in 2D games?
Beyond navigating a single character to a target, A* is used in 2D games for AI patrol routes, enemy pursuit with dynamic obstacles, waypoint planning for NPC dialogue triggers, and precomputed navigation meshes on tile grids. In practice, developers often layer A* with steering behaviors so movement looks natural rather than snapping tile-to-tile.
Is A* the best pathfinding algorithm for a 2D game?
Not always. A keeps every candidate node in memory via its open and closed lists, so on very large maps the memory overhead becomes a real cost. When many agents need to move toward the same target — for example, an RTS with hundreds of units — flow fields compute a single vector field once and let every unit follow it, which typically outperforms running A per unit. Reach for A* when you have one agent, a moderate map, and an admissible heuristic; reach for alternatives when either of those breaks.
What programming language should I use to build a 2D game?
Any language with a game framework works, but the right pick depends on scope. For prototypes and learning, Python with Pygame is the fastest to set up. For shipped 2D games, C# with Unity is the mainstream production choice, and GDScript with Godot is a strong open-source alternative. Godot uses GDScript, a Python-like scripting language built specifically for the engine, and also supports C# for developers who prefer a more mainstream production language. The A* implementation shown here can be ported to any of them with minor syntax changes.
What is the best software for creating 2D games?
For beginners, Unity and Godot are the two most popular 2D game engines — Unity has the larger asset store and job market, while Godot is free, open-source, and lighter for small projects. GameMaker is another strong choice for pixel-art 2D games, and Pygame remains the fastest way to prototype pathfinding logic like the A* implementation shown above.
