An introduction to A* pathfinding (tutorial)
Tags: programming, python, ai, tutorial
Published: 2021-07-26 06:47:09

> This is part 3 of a series on bot programming originally published on the [Coder One blog](https://www.gocoder.one/blog/introduction-to-a-star-pathfinding). 
Part 1: [Getting started with the game environment](https://www.gocoder.one/blog/how-to-build-an-ai-game-bot-bomberman)
Part 2: [Creating our first agent](https://www.gocoder.one/blog/beginners-bot-programming-tutorial-bomberman)

The A* pathfinding (or A* search) algorithm is a popular technique for finding the shortest path between two points in an environment.  

In this tutorial, we'll implement an A* pathfinding algorithm in Python to help our agent navigate to a target destination in the [Dungeons and Data Structures environment](https://dnds.gocoder.one). Make sure you check out [Part 1](https://www.gocoder.one/blog/how-to-build-an-ai-game-bot-bomberman) to get set up (and optionally [Part 2](https://www.gocoder.one/blog/beginners-bot-programming-tutorial-bomberman) to create a simple bot).

![Pathfinding](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ixj9czibbcfphztaxyvc.png)

We'll use the A* pathfinding algorithm to help our knight find the shortest path to a destination.

We won't go deeply into the theory behind A* pathfinding here. Instead, check out these useful resources:

- Get a feel for the intuition behind A* pathfinding: [Introduction to A* Pathfinding](https://www.raywenderlich.com/3016-introduction-to-a-pathfinding) [1]
- The algorithm pseudocode we'll be implementing: [Amit's thoughts on pathfinding](http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html) [2]

## A* pathfinding overview

Provided a starting node, A* pathfinding works by:

1. Searching its neighboring nodes
2. Assigning them a total **cost** (i.e. time taken, tiles moved, etc) based on the cost taken to get there from the starting node ***plus*** the estimated cost of the cheapest path from the neighbor node to the destination

The goal of A* is to minimize:

**f(n) = g(n) + h(n)**

Where:

- *n* is the current node in the path
- *g(n)* is the cost of the path from the starting node to *n*
- *h(n):* a heuristic function that estimates the cost to move from *n* to the target cell

![A* Pathfinding Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uqcak046h1chqgs9ik9m.png)
*Example of f(n), g(n) and h(n) values in our environment.*

> **What's the difference between A\* and Dijkstra's algorithm?**
The A* search algorithm can be considered an application of Dijkstra's algorithm, which adds heuristics to guide its search and achieve better performance. If you set the heuristic function *h(n)* equal to 0, the A* algorithm essentially boils down to Dijkstra's algorithm.

## Getting started

The goal will be to help our agent successfully navigate to a given destination in the environment Dungeons and Data Structures:

![Pathfinding](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jio5wt261y7k8orwsrhy.gif)

If you've been following along with [Part 1](https://www.gocoder.one/blog/how-to-build-an-ai-game-bot-bomberman) and [Part 2](https://www.gocoder.one/blog/beginners-bot-programming-tutorial-bomberman), we'll be restructuring our project to make it a bit more manageable.

To start, create 3 files in your working directory:

- `__init__.py` — to be called by the main environment

```python
from . import my_agent

def agent():
    return my_agent.Agent()
```

- `my_agent.py` — holds our agent's behavior logic

```python
from .helpers import *

class Agent:

    def __init__(self):
        '''
        Place any initialization code for your agent here (if any)
        '''
        self.pending_actions = []

    def next_move(self, game_state, player_state):
        '''
        This method is called each time your Agent is required to choose an action
        '''
				
        pass
```

- `helpers.py` — holds all our helper functions and classes (empty file for now)

## Helper functions

We'll define some helper functions that will be useful for our A* pathfinding algorithm later. Add these to your `helpers.py` file.

> **Note:**  For consistency in the following sections, we'll refer to **tiles** as an (x,y) location of any tile on the map, and **nodes** as specific instances of the Node class object (which we'll cover later on). A **node** will contain a `location` property equivalent to a tile.

### `get_free_neighbors()`

Given a tile, this will be used to get a list of surrounding tiles to search next.

```python
# given our current location, return only surrounding tiles that are free
def get_free_neighbors(game_state, location):

    x, y = location
    neighbors = [{(x-1, y): 'l'}, {(x+1, y): 'r'}, {(x, y-1): 'd'}, {(x, y+1): 'u'}]
    free_neighbors = []

    for neighbor in neighbors:
        for tile, direction in neighbor.items():
            if game_state.is_in_bounds(tile):
                if game_state.is_occupied(tile):
                    # check if this tile contains treasure or ammo
                    if game_state.entity_at(tile) == 't' or game_state.entity_at(tile) == 'a':
                        free_neighbors.append({tile:direction})
                else:
                    free_neighbors.append({tile:direction})

    return free_neighbors
```

### `get_treasure()`

We'll make our target destination the location of any treasure that spawns. (Alternatively, switch out `treasure` for `ammo` to make the agent pick up ammo around the map instead).

```python
# finds treasure, if any
def get_treasure(game_state):

    treasure = game_state.treasure

    if treasure:
        return treasure[0] # return first treasure on the list
```

### `manhattan_distance()`

We mentioned earlier that the A* pathfinding algorithm is guided by a **heuristic function** $h(n)$. The heuristic function we'll use is the **Manhattan Distance**:

![Manhattan Distance](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vb3oy9gz5e7gzjmpyzj3.png)

[Source](https://iq.opengenus.org/euclidean-vs-manhattan-vs-chebyshev-distance/)

This Manhattan Distance is an **approximation** of the distance between our current node and the destination since it will not account for any obstacles. While not perfect, it will work for our purposes.

![Manhattan Distance](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/00hodxdmxg2af8ney5pe.png)

Manhattan Distance does not account for obstacles in our path

```python
def manhattan_distance(start, end):

    distance = abs(start[0] - end[0]) + abs(start[1] - end[1])

    return distance
```

## The A* Algorithm

Here is the pseudocode we will be implementing from [[2]](http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html):

```markup
OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers
```

Here is our implementation ([link to full code](https://gist.github.com/joooyzee/7c681f9c5711d3e9ea556ac7f55bebea)):

```python
########################
###    Pathfinder    ###
########################

class Node:

    def __init__(self, parent=None, location=None, action=None):
        self.parent = parent
        self.location = location
        self.action = action

        self.h = 0
        self.g = 0
        self.f = 0

def get_path(node):
    path = []

    while node.parent:
        path.append(node)
        node = node.parent

    return path

def get_path_actions(path):

    actions = []

    for node in path:
        actions.append(node.action)

    return actions

def astar(game_state, start, target):

    print("----A* STAR----")
    path = []

    # add starting node to open list
    open_list = [Node(None, start, None)]
    closed_list = []

    # exit the loop early if no path can be found
    # (the target is likely blocked off)
    max_loops = 1000
    counter = 0

    # while lowest rank in OPEN is not the GOAL:
    while len(open_list) > 0 and counter <= max_loops:

        # find the node with the lowest rank
        curr_node = open_list[0]
        curr_index = 0

        for index, node in enumerate(open_list):
            if node.f < curr_node.f:
                curr_node = node
                curr_index = index

        # check if this node is the goal
        if curr_node.location == target:
            print(f"~~~~~~~FOUND TARGET~~~~~~~")
            path = get_path(curr_node)
            return path

        # current = remove lowest rank item from OPEN
        # add current to CLOSED
        del open_list[curr_index]
        closed_list.append(curr_node)

        # get neighbors of current
        neighbors = get_free_neighbors(game_state, curr_node.location)
        neighbor_nodes = []
        for neighbor in neighbors:
            for location, action in neighbor.items():
                neighbor_nodes.append(Node(None, location, action))

        #   for neighbors of current:
        for neighbor in neighbor_nodes:
            
            # used for loop behavior
            in_closed = False
            in_open = False

            # cost = g(current) + movementcost(current, neighbor)
            cost = curr_node.g + 1

            # if neighbor in OPEN and cost less than g(neighbor):
            #   remove neighbor from OPEN, because new path is better
            for index, node in enumerate(open_list):
                if neighbor.location == node.location and cost < neighbor.g:
                    del open_list[index]
                    in_open = True

            # if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
            #   remove neighbor from CLOSED
            for index, node in enumerate(closed_list):
                if neighbor.location == node.location and cost < neighbor.g: 
                    del closed_list[index]
                    in_closed = True

            # if neighbor not in OPEN and neighbor not in CLOSED:
            #   set g(neighbor) to cost
            #   add neighbor to OPEN
            #   set priority queue rank to g(neighbor) + h(neighbor)
            #   set neighbor's parent to current
            if not in_open and not in_closed:
                neighbor.g = cost
                open_list.append(neighbor)
                neighbor.h = manhattan_distance(neighbor.location, target)
                neighbor.f = neighbor.g + neighbor.h
                neighbor.parent = curr_node

        counter += 1

    print(f"---NO PATH FOUND---")
```

Add this to `helpers.py`.

Note that we've added `get_path_actions()`. This will return the actions our agent will need to take in order to get to the destination (e.g. `['u', 'l', ...]`)

## Adding pathfinding to our agent

To check that everything is working, update the `next_move()` method in your `my_agent.py` file:

```python
def next_move(self, game_state, player_state):
    
    print(f"tick: {game_state.tick_number}")

    # treasure spawns randomly
    treasure = get_treasure(game_state)

    if len(self.pending_actions) > 0:
        action = self.pending_actions.pop()
    elif treasure:
        path = astar(game_state, player_state.location, treasure)

        if path:
            actions = get_path_actions(path)
            print(f"--ACTIONS: {actions}")

            for action in actions:
                self.pending_actions.append(action)

            action = self.pending_actions.pop()
        else:
            action = ''
    else:
        action = ''

    return action
```

[Link to full code](https://gist.github.com/joooyzee/b053ab09eb908996633c269c6492cffd)

In your terminal, run:

```bash
coderone-dungeon my_agent --interactive
```

(The `--interactive` flag will allow you to play as the Knight)

If you've set everything up successfully, you should see your agent picking up treasure around the map (treasure spawns randomly).

```bash
----A* STAR----
~~~~~~~FOUND TARGET~~~~~~~
--ACTIONS: ['d', 'd', 'd', 'r', 'r', 'd', 'r', 'r', 'r']
```

**Note:** we built our path from the destination node backward so this list of actions is also reversed. This is fine since we use `pop()` which takes actions from the end of the list.