Creating your first 2D game with A* Algorithm

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 (a heuristic, informally, is like an algorithm, which helps us determine the answer but not in a definite series of steps).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.

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

1. Select the starting point and put it in the open list.
2. Find the F cost to the current node.
3. Mark it in the closed list.
4. For each of the 8 nodes adjacent to the current node, do the following:
   • 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.
5. 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 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()

Arpit Mishra Author 49 Blogs