Sunday 26 June 2011

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.

example2

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

example3

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.

31 comments:

  1. Great tutorial! Hope to see your next tutorial soon!

    ReplyDelete
  2. Hi, loved your tutorial! If I can help you with ANYthing, you just have to say it. I can program Xna pretty good. Of course not as good as you, but I have a fairly understanding of Xna. I've made a pacman clone, a side-scrolling adventure like game and I've done a bit in 3d. So if you need any help, than I would love to help you to speed up your posts.

    Martijn

    ReplyDelete
  3. I am glad you liked it! Thanks for the kind offer Martijn but I don't really need any help at the moment, but thank you anyway!!

    ReplyDelete
  4. ok no problem. If you ever do need help I would love to help you.

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Had a long post inquiring about how the searchNodes array stores data, but figured it out after reading the WIKI on Breadth-First.
    So, if I get this right, the searchNode array will drill down from each node into all the neighboring nodes to get a path to all possible locations from the current location?
    I'm assuming we'll check to see which node has the shortest set of neighbor 'hops' to find the shortest path?
    Can't wait for more!

    ReplyDelete
  7. How do we pause it! I have been wondering for so long on how to make it pause, all i want is to set the enemy speed to 0, but whatever I do it doesn't work!

    ReplyDelete
  8. You could do something like this in Game1.cs :

    http://pastebin.com/pDL2yJpz

    ReplyDelete
  9. One more (hopefully my last) question: How do we make it so the tower doesnt turn when it shoots. I want the bullet to go to the enemy, but I can't get it to turn.

    ReplyDelete
  10. when will get part 2?! This tutorial has been very helpful

    ReplyDelete
  11. Are you making a part 2?

    ReplyDelete
  12. waiting too...

    ReplyDelete
  13. Sorry about the wait guys I am still writing Part 2, I recently got a new job which is taking up a lot of my time but the tutorial is nearly finished, I just need to add some extra details to it!

    ReplyDelete
  14. in wich xna is this tutorial made?

    ReplyDelete
  15. xna 4.0 (c#). Were you asking for that, or do you mean something else?

    ReplyDelete
  16. Still waiting :'(

    ReplyDelete
  17. If you need any help at this moment, you know you just have to snap your fingers (I've got holiday and nothing to do ;-).

    Martijn

    ReplyDelete
  18. Have you got an email I can contact you on? It would be really helpful if you could read through what I have so far and tell me if anything isn't clear enough or something is missing etc.

    ReplyDelete
  19. very helpful tutorial.
    hope to see part 2 soon

    ReplyDelete
  20. "if (neighbor == null || neighbor.Walkable == false)"

    Perator "||" cannot be applied to operands of type '' and 'bool'.

    ReplyDelete
  21. You said that "we will ignore diagonals for now"... but part 2 and 3 don't seem to go back to it. I've tried just adding their coordinates to the list of neighbours, but it doesn't work. How do we stop the pests from walking through walls? ^_^

    ReplyDelete
  22. When you are initializing the search nodes you would have to add in some extra checks for diagonal tiles.

    For example to check if the top right neighbour can be walked to you would need to something like:

    if (topRightNode.Walkable == false ||
    topNode.Walkable == false ||
    rightNode.Walkable == false)
    {
    // Can't get to top right tile!
    }

    ReplyDelete
  23. i'm trying to make a game with monsters can i use this algorithm or will I change something ???

    ReplyDelete
    Replies
    1. Thats a very bad way of putting it.. If you use a grid you will not have to change anything. You just gotta tell each and every monster where it can or cannot walk. The core of this will not change, all it depends on is you calling the right references.

      Delete
  24. Good Job. One of the best A* tut Ive seen well done.

    ReplyDelete
  25. Good day!

    My friends and I are competing in the 2013 Imagine Cup, Games Category.
    We humbly request your permission to let us your A*Pathfinder class in our entry.
    In line with this, we ask for your email that we may ask for your permission in a more formal way.

    Thank you for your consideration.

    ReplyDelete
  26. Hey,

    You of course of have my permission, if you wish to contact me further my public email is zulbaric11@yahoo.co.uk. Good look with your entry!

    ReplyDelete
    Replies
    1. thank you very much! (^_^)
      an email has been sent to you.

      Delete