A* Pathfinding Tutorial : Part 1

Welcome to part one of my two part series on path finding!

In this first part we will be looking at the amazing A* (A-Star) pathfinding algorithm which is probably one of the most precise and performance friendly pathfinding algorithm out there at the moment.

In part two I am going to show you that although A* is great, that it isn’t always the best algorithm for the job. I will be showing you how we can add pathfinding to the tower defence game made in the previous series using a Breadth First algorithm.

The first thing we are going to do talk about before we get onto the algorithm itself is the world in which the pathfinding will take place.

Imagine we have a very simple level like this and we want to get from the red flag to the yellow flag.

The first thing that we will need to do to find a path is split the level up into a grid.

This allows us to simplify the level down to a series of squares, some that can be walked across, and some that are blocked. Each of these squares (or nodes) represent a tile that our path might pass over. We call the squares around a node the nodes neighbours.

So, lets implement what we have just talked about in code. I have made a project that I will be using as the starting code for this tutorial; all it does is create a level and draw it to the screen.

It can be downloaded here.

Once you have opened up the project you will need to find and open Pathfinder.cs and you should see two empty classes ready for us to get started with! The SearchNode class will represent one of our pathfinding nodes.

So lets start by padding it out with some useful fields :

/// <summary>

/// Reresents one node in the search space

/// </summary>

private class SearchNode

{

/// <summary>

/// Location on the map

/// </summary>

public Point Position;

/// <summary>

/// If true, this tile can be walked on.

/// </summary>

public bool Walkable;



/// <summary>

/// This contains references to the for nodes surrounding 

/// this tile (Up, Down, Left, Right).

/// </summary>

public SearchNode[] Neighbors;

}

There is nothing too scary there, the first field is to keep track of where the node is on our map. The second field defines if the node can be walked on or not! The last field will keep track of the other nodes that surround this node.

Now that we have our node defined we will concentrate on the Pathfinder class! This is where all of the magic will happen. Add the following fields and the constructor to the top of the Pathfinder class :

// Stores an array of the walkable search nodes.

private SearchNode[,] searchNodes;



// The width of the map.

private int levelWidth;

// The height of the map.

private int levelHeight;



/// <summary>

/// Constructor.

/// </summary>

public Pathfinder(Map map)

{

levelWidth = map.Width;

levelHeight = map.Height;

}

The first node is a 2D array that will keep track of our search nodes, it is in the same format as the layout array in our map class. This is because one tile from our map class will be represented by one of our search nodes!

The other two fields just help us keep track of how big the level is. Next we are going to add a new method to the class, this will be the method responsible for splitting our level up into a grid. Add this method just underneath the constructor :

// <summary>

/// Splits our level up into a grid of nodes.

/// </summary>

private void InitializeSearchNodes(Map map)

{



}

Before we start padding out this method, we need to make sure that it is called in the Pathfinder’s constructor, so add this line at the bottom of the Constructor :

InitializeSearchNodes(map);

Ok we are now ready to start padding at the InitializeSearchNodes method. Let’s start by adding the following code to the InitializeSearchNodes method :

searchNodes = new SearchNode[levelWidth, levelHeight];



//For each of the tiles in our map, we

// will create a search node for it.

for (int x = 0; x < levelWidth; x++)

{

for (int y = 0; y < levelHeight; y++)

{

    //Create a search node to represent this tile.

    SearchNode node = new SearchNode();



    node.Position = new Point(x, y);



    // Our enemies can only walk on grass tiles.

    node.Walkable = map.GetIndex(x, y) == 0;



    // We only want to store nodes

    // that can be walked on.

    if (node.Walkable == true)

    {

        node.Neighbors = new SearchNode[4];

        searchNodes[x, y] = node;

    }

}

}

We start off by initializing the grid of nodes that we defined earlier. Next, for every tile on the map, we create a new search node to represent it. Note that we don’t set up the references to the neighbour nodes just yet, first we need to create all of the nodes before we can start referencing them!

Next just below that code add the following :

// Now for each of the search nodes, we will

// connect it to each of its neighbours.

for (int x = 0; x < levelWidth; x++)

{

for (int y = 0; y < levelHeight; y++)

{

    SearchNode node = searchNodes[x, y];



    // We only want to look at the nodes that 

    // our enemies can walk on.

    if (node == null || node.Walkable == false)

    {

        continue;

    }



    // An array of all of the possible neighbors this 

    // node could have. (We will ignore diagonals for now.)

    Point[] neighbors = new Point[]

    {

        new Point (x, y - 1), // The node above the current node

        new Point (x, y + 1), // The node below the current node.

        new Point (x - 1, y), // The node left of the current node.

        new Point (x + 1, y), // The node right of the current node

    };



    // We loop through each of the possible neighbors

    for (int i = 0; i < neighbors.Length; i++)

    {

        Point position = neighbors[i];



        // We need to make sure this neighbour is part of the level.

        if (position.X < 0 || position.X > levelWidth - 1 ||

            position.Y < 0 || position.Y > levelHeight - 1)

        {

            continue;

        }



        SearchNode neighbor = searchNodes[position.X, position.Y];



        // We will only bother keeping a reference 

        // to the nodes that can be walked on.

        if (neighbor == null || neighbor.Walkable == false)

        {

            continue;

        }



        // Store a reference to the neighbor.

        node.Neighbors[i] = neighbor;

    }

}

}

I know the length of this snippet may be quite daunting, but the code code is actually pretty simple! We loop through all of our search nodes, and if the node can be walked on, we look at all of the possible neighbours for that node. If the neighbour is part of the level and can be walked on, we keep a reference to it. It’s as simple as that!

And that is all we will be doing on the pathfinder in this tutorial. The last thing we are going to do is create an instance of the pathfinder in the game class, so go to Game1.cs and at the top add the following field :

Pathfinder pathfinder;

Next go to the Initialize method and add the following :

pathfinder = new Pathfinder(map);

And we are finished for this part of the tutorial, I know it doesn’t seem like we have done much, but we have just laid down the foundations for our pathfinder!

Next time we will actually look at the algorithm in more depth before we get to work implementing it in code.