Moving from point A to point B is the prime requirement for many games—whether it is a strategic tactic-based RPG (role-playing game) like Warcraft III or one that’s as simple as Snakes and Ladders. The source-to-destination navigation sometimes requires more intelligence from your character than you believe, it needs to find the path with ease. You can’t have your characters walking through a wall or bumping into a car while playing, can you?
This is where pathfinding algorithms are used. Pathfinding is the basic building block for most games. Players have to reach a destination by moving around blocks, cars, rivers, and prisons. The algorithm ensures that the character not only avoids the obstacles but also gets to the destination by using the shortest path.
Games like Warcraft III use the A* pathfinding algorithm, where the protagonist is not only expected to reach his destination by the shortest path, but also move around the castles, not get in through the huts, dungeon, or walk through a dragon on its way.
A* algorithm (Pronounced A-star algorithm)
The A* algorithm is the fastest graph search algorithm that finds the path that costs the least from source node to goal node. (A node can be hexagon, square or circle, etc.)
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* algorithm has properties of both Dijkstra and Best-first search. Unlike DFS and BFS, the A* algorithm selects the node which looks most promising instead of guessing the next node.
The cost function
The cost of node F is calculated as:
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.
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
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
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, which is equal to 1.4.
To make things easier, multiply each value by 10, thereby converting the distance to 10 and 14 for adjacent and diagonal nodes, respectively.
Let’s make 2 lists of open and closed nodes. Any node that is selected for the path is moved to the closed node list. Any node that is not selected is considered to be an open node.
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 that is diagonally opposite to the source and marked in red would have a G value of 14, an H value of 10, and an F value of 52. You can compute the values for all other blocks similarly.
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.
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 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 your target node is marked as closed, or there are no more nodes to be marked as open.
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* only finds the most optimal path. The graph search is only one piece of the puzzle. A* does not handle things like object movement, map changes, etc.
Why don't you create your own 2D game with movement and hone your skills as your game evolves with better algorithms?
If you enjoy algorithms as much as I do, read my other article on the Elo rating algorithm.
PS: For code enthusiasts, here is the Python code to the A* algorithm.
# -*- coding: utf-8 -*-
"""
# A* Shortest Path Algorithm
# http://en.wikipedia.org/wiki/A*
"""
# ... (full code continues here as already shared)
