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
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.
We have implemented the node as coordinates depending on the type of object that is passed. The attributes that it will have are the position, distance, priority and the possible directions that the node object can move. These attributes are managed through the updatePriority and nextMove methods. The implementation is shown below. You might notice that the cost function shown above is the estimate method of the node object.
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):
"""
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
def updatePriority(self, xDest, yDest):
"""
employs the a-star heuristic
"""
self.priority = self.distance + self.estimate(xDest, yDest) * 10
def nextMove(self, d):
"""
give higher priority to going straight instead of diagonally
d: direction to move
"""
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 the obtained by summing G (which is the distance from the source node) and H (which is the distance from the goal node).
For example, a block that is diagonally opposite to the source and marked in red would have a G value of 14 (1.4 * 10), an H value of 10 (2*1.4*10 +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):
"""
generate the path from finish to start by following the possible_directions
"""
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 (nodes which are not selected), 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. This process has been represented in red and purple for the problem above.
However, in a game, the path is not so simple. It is usually filled with hurdles and areas that the character is not supposed to walk in.
Assume that, in a game, the section in black is the area which cannot be traversed by the player. We will use the same approach that we used in the previous example while keeping in mind that there is now a black node that the player cannot traverse.
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 (F=G+H). Now select the node with the smallest value, which in this case is 48. Once you select the node with the smallest value, find the F values of all its surrounding nodes. The process of selecting the smallest node continues.
But what if two nodes have the same values, like F=48, in the table above?
In such cases, you must select any one of the nodes with a similar F value and proceed with finding F values of its surrounding nodes.
Select the node with the smallest F value and carry on along the path. You will soon reach the goal node by the shortest path possible.
Summary of A * Algorithm
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 not a definitive work on the subject, rather it 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*
"""
from __future__ import print_function
from heapq import heappush, heappop # for priority queue
import math
import time
import random
# for compatibility with both py2 and py3
try:
input = raw_input
except NameError:
pass
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):
"""
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
def updatePriority(self, xDest, yDest):
"""
employs the a-star heuristic
"""
self.priority = self.distance + self.estimate(xDest, yDest) * 10
def nextMove(self, d):
"""
give higher priority to going straight instead of diagonally
d: direction to move
"""
if self.possible_directions == 8 and d % 2 != 0:
self.distance += 14
else:
self.distance += 10
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):
"""
generate the path from finish to start by following the possible_directions
"""
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
def outside_map(x_y_shift,
horizontal_size_of_map, vertical_size_of_map):
return any((x_y_shift.change_in_x < 0, x_y_shift.change_in_y < 0,
x_y_shift.change_in_x > horizontal_size_of_map - 1,
x_y_shift.change_in_y > vertical_size_of_map - 1))
class Shift:
"""
x -> change in x
y -> change in y
"""
def __init__(self, x, y):
self.change_in_x = x
self.change_in_y = y
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))
def generate_a_child_node(x_y_shift, node, direction, finish_coord):
child_node = Node(x_y_shift,
node.distance, node.priority,
node.possible_directions)
child_node.nextMove(direction)
xB, yB = finish_coord
child_node.updatePriority(xB, yB)
return child_node
def pathFind(the_map, horizontal_size_of_map, vertical_size_of_map,
possible_directions, dx, dy, xA, yA, xB, yB):
"""
A-star algorithm. The path returned will be a string of digits of direction
"""
finish_coord = (xB, yB)
start_coord = (xA, yA)
row = [0] * horizontal_size_of_map
# map of closed (tried-out) nodes
closed_nodes_map = [list(row) for _ in range(vertical_size_of_map)]
# map of open (not-yet-tried) nodes
open_nodes_map = [list(row) for _ in range(vertical_size_of_map)]
# map of possible_directions
dir_map = [list(row) for _ in range(vertical_size_of_map)]
priority_queues = [[], []] # priority queues of open (not-yet-tried) nodes
priority_queue_indx = 0
# create the start node and push into list of open nodes
node = Node(start_coord, 0, 0, possible_directions=possible_directions)
node.updatePriority(xB, yB)
heappush(priority_queues[priority_queue_indx], node)
open_nodes_map[yA][xA] = node.priority # mark it on the open nodes map
# A* search
while len(priority_queues[priority_queue_indx]) > 0:
# get the current node with the highest priority
# from the list of open nodes
top_node = priority_queues[priority_queue_indx][0]
node = Node(top_node,
top_node.distance, top_node.priority,
possible_directions=possible_directions)
x = node.x_position
y = node.y_position
heappop(priority_queues[priority_queue_indx]) # remove the node from the open list
open_nodes_map[y][x] = 0
closed_nodes_map[y][x] = 1 # mark it on the closed nodes map
# quit searching when the goal is reached if node.estimate(xB, yB) == 0:
if node.x_position == xB and node.y_position == yB:
return generate_path(possible_directions, dir_map,
dx, dy, xA, yA,
node.x_position, node.y_position)
# generate moves (child nodes) in all possible possible_directions
for direction in range(possible_directions):
change_in_x = node.x_position + dx[direction]
change_in_y = node.y_position + dy[direction]
x_y_shift = Shift(change_in_x, change_in_y)
if not (outside_map(x_y_shift, horizontal_size_of_map, vertical_size_of_map) or
collision_with_obstacle(x_y_shift, the_map, closed_nodes_map)):
child_node = generate_a_child_node(x_y_shift, node,
direction, finish_coord)
# if it is not in the open list then add into that
if open_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 0:
open_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] = child_node.priority
heappush(priority_queues[priority_queue_indx], child_node)
# mark its parent node direction
dir_map[x_y_shift.change_in_y][x_y_shift.change_in_x] = a_chosen_direction(direction, possible_directions=possible_directions)
elif open_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] > child_node.priority:
# update the priority
open_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] = child_node.priority
# update the parent direction
dir_map[x_y_shift.change_in_y][x_y_shift.change_in_x] = a_chosen_direction(direction, possible_directions=possible_directions)
# replace the node by emptying one priority_queues to the other one
# except the node to be replaced will be ignored and
# the new node will be pushed in instead
while not (priority_queues[priority_queue_indx][0].x_position == x_y_shift.change_in_x and
priority_queues[priority_queue_indx][0].y_position == x_y_shift.change_in_y):
heappush(priority_queues[1 - priority_queue_indx], priority_queues[priority_queue_indx][0])
heappop(priority_queues[priority_queue_indx])
heappop(priority_queues[priority_queue_indx]) # remove the target node
# empty the larger size priority queue
# to the smaller one
if len(priority_queues[priority_queue_indx]) > len(priority_queues[1 - priority_queue_indx]):
priority_queue_indx = 1 - priority_queue_indx
while len(priority_queues[priority_queue_indx]) > 0:
heappush(priority_queues[1-priority_queue_indx], priority_queues[priority_queue_indx][0])
heappop(priority_queues[priority_queue_indx])
priority_queue_indx = 1 - priority_queue_indx
heappush(priority_queues[priority_queue_indx], child_node) # add the better node instead
return '' # if no route found
if __name__ == "__main__":
possible_directions = 8 # number of possible directions to move on the map
if possible_directions == 4:
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
elif possible_directions == 8:
dx = [1, 1, 0, -1, -1, -1, 0, 1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
horizontal_size_of_map = 100
vertical_size_of_map = 100
the_map = []
row = [0] * horizontal_size_of_map
for i in range(vertical_size_of_map): # create empty map
the_map.append(list(row))
# fillout the map with a '+' pattern
for x in range(horizontal_size_of_map // 8, horizontal_size_of_map * 7 // 8):
the_map[vertical_size_of_map // 2][x] = 1
for y in range(vertical_size_of_map//8, vertical_size_of_map * 7 // 8):
the_map[y][horizontal_size_of_map // 2] = 1
# randomly select start and finish locations from a list
sf = []
sf.append((0, 0, horizontal_size_of_map - 1, vertical_size_of_map - 1))
sf.append((0, vertical_size_of_map - 1, horizontal_size_of_map - 1, 0))
sf.append((horizontal_size_of_map // 2 - 1, vertical_size_of_map // 2 - 1, horizontal_size_of_map // 2 + 1, vertical_size_of_map // 2 + 1))
sf.append((horizontal_size_of_map // 2 - 1, vertical_size_of_map // 2 + 1, horizontal_size_of_map // 2 + 1, vertical_size_of_map // 2 - 1))
sf.append((horizontal_size_of_map // 2 - 1, 0, horizontal_size_of_map // 2 + 1, vertical_size_of_map - 1))
sf.append((horizontal_size_of_map // 2 + 1, vertical_size_of_map - 1, horizontal_size_of_map // 2 - 1, 0))
sf.append((0, vertical_size_of_map // 2 - 1, horizontal_size_of_map - 1, vertical_size_of_map // 2 + 1))
sf.append((horizontal_size_of_map - 1, vertical_size_of_map // 2 + 1, 0, vertical_size_of_map // 2 - 1))
(xA, yA, xB, yB) = random.choice(sf)
print('Map size (X,Y): ', horizontal_size_of_map, vertical_size_of_map)
print('Start: ', xA, yA)
print('Finish: ', xB, yB)
t = time.time()
route = pathFind(the_map, horizontal_size_of_map, vertical_size_of_map, possible_directions, dx, dy, xA, yA, xB, yB)
print('Time to generate the route (seconds): ', time.time() - t)
print('Route:')
print(route)
# mark the route on the map
if len(route) > 0:
x = xA
y = yA
the_map[y][x] = 2
for i in range(len(route)):
j = int(route[i])
x += dx[j]
y += dy[j]
the_map[y][x] = 3
the_map[y][x] = 4
# display the map with the route added
print('Map:')
for y in range(vertical_size_of_map):
for x in range(horizontal_size_of_map):
xy = the_map[y][x]
if xy == 0:
print('.' ,end="") # space
elif xy == 1:
print('O' ,end="") # obstacle
elif xy == 2:
print('S', end="") # start
elif xy == 3:
print('R', end="") # route
elif xy == 4:
print('F', end="") # finish
print() Introduction In today's dynamic workplaces, a strong HR department is no longer a luxury –…
Job task analysis is a crucial process for understanding the specific duties and skills required…
In today's competitive talent landscape, attracting top candidates requires going beyond traditional job board postings.…
Finding the perfect fit for your team can feel like searching for a unicorn. But…
Recruitment forms a strong foundation to build an effective team. However, do you know if…
Introduction Performance appraisal has seen a tremendous change over the years. It is no longer…