Dot Net Perls

Problem

Use A-Star Pathfinding to allow monsters to maneuver walls and obstacles. In some old Nintendo games, monsters would walk predetermined paths or randomly meander, but that's dumb. To fix this, we need an algorithm that always finds the shortest path between two points, even when there are obstacles in between.

C# Solution

Here we go through the steps you need to take to implement the A-Star Pathfinding algorithm. This algorithm allows you to find the shortest path from one point to another, navigating along walls and barriers. This algorithm is how you can have a monster walk between obstacles to your character, the hero.

What are the steps?

I will break the algorithm we are going to write into these steps. Let's assume we have a program with an interface, and a 2-dimensional grid of squares for our field. We will use a 15 x 15 square grid here. What follows is how the monster will find the hero.

1. Start at the hero
   Beginning at the hero's location, place numbers that indicate the number of steps each square is.
2. Lowest number
   Using the lowest number each time, fill up the board with these numbers. As you get further from the hero, the numbers get higher.
3. When all squares have numbers
   When all the squares are numbered, the hero will be surrounded by 1's, and the monster will be surrounded with much higher numbers.
4. Path is found
   This is why it is called pathfinding. The monster's best path will be found by following the lowest number it finds on each step.

Player positions. Look at the screenshot at the top, and you can see two orange squares. The two orange squares are the monster and the hero. They are both the same color because the way the algorithm works, there is no difference. The blue line is the best path, as found by the A* Pathfinding algorithm.

What data do we store?

We need some objects at the class level to store our data. I show what we do with these later on. Let's just look at the class-level member variables now.

// Movements is an array of various directions.
Point[] _movements;

// Squares is an array of square objects.
CompleteSquare[,] _squares = new CompleteSquare[15, 15];

How do we move through the squares?

Let's start by defining a movement array of Point objects. Think of the movements a monster can take as a grid of 9 squares--one in every direction. We can define these squares by their coordinates. When we go to use this array, we add it to the regular coordinates to find the new square.

void InitMovements(int movementCount)
{
    // Use 4 or 8 directions, depending on the setup. We use collection
    // initializer syntax here to create the arrays.
    if (movementCount == 4)
    {
        _movements = new Point[]
        {
            new Point(0, -1),
            new Point(1, 0),
            new Point(0, 1),
            new Point(-1, 0)
        };
    }
    else
    {
        _movements = new Point[]
        {
            new Point(-1, -1),
            new Point(0, -1),
            new Point(1, -1),
            new Point(1, 0),
            new Point(1, 1),
            new Point(0, 1),
            new Point(-1, 1),
            new Point(-1, 0)
        };
    }
}

How can we test for valid points?

We only have a 15 x 15 square grid, and we can't allow anything to move off of the board. That would cause our program to crash or throw an exception. Let's setup a nice validation function. The function is static because it doesn't save state and doesn't need access to any other class members.

static private bool ValidCoordinates(int x, int y)
{
    // Our coordinates are constrained between 0 and 14.
    if (x < 0)
    {
        return false;
    }
    if (y < 0)
    {
        return false;
    }
    if (x > 14)
    {
        return false;
    }
    if (y > 14)
    {
        return false;
    }
    return true;
}

What data do we store for each square?

We need a data structure to store the board square data. Each square can have a hero, a monster, a wall, or be empty. Let's put that information in the form on an enum type. The following snippet shows the various enum values squares can contain.

enum SquareContent
{
    Empty,
    Monster,
    Hero,
    Wall
};

Now, we will use that enum to define various parts on the board squares. Hold on, because I will show you how we read in the maps from files on the disk. The next code I am showing is the data structure that we store each square. Right after this code, I will show a table that describes some parts of what it does.

class CompleteSquare
{
    SquareContent _contentCode = SquareContent.Empty;
    public SquareContent ContentCode
    {
        get { return _contentCode; }
        set { _contentCode = value; }
    }

    int _distanceSteps = 100;
    public int DistanceSteps
    {
        get { return _distanceSteps; }
        set { _distanceSteps = value; }
    }

    bool _isPath = false;
    public bool IsPath
    {
        get { return _isPath; }
        set { _isPath = value; }
    }

    public void FromChar(char charIn)
    {
        // Use a switch statement to parse characters.
        switch (charIn)
        {
            case 'W':
                _contentCode = SquareContent.Wall;
                break;
            case 'H':
                _contentCode = SquareContent.Hero;
                break;
            case 'M':
                _contentCode = SquareContent.Monster;
                break;
            case ' ':
            default:
                _contentCode = SquareContent.Empty;
                break;
        }
    }
}

What file format do we use?

It is by far easier to use a text file to store the map information. Look at FromChar above, and you will see that W stands for Wall, and H for Hero, and M for monster, and a space for empty. Those are the characters in our files. The following text is used to build the display shown near the start of this article.

              M
   WWWWWWWWWWWW
               
               
WWWWWWWWWWW
               
               
               
       WWWWWWWW
               
WWWWWWWWWWWW   
               
H              
               
WWWWWWWW       

If you look closely at all the Ws, which stand for walls, you can see the resemblance to the graphic. (The Ws may also stand for bushes, as I mentioned at the start.) Next, let's examine the short code that reads in the file itself. You may want to take a peek at my article about using statements.

private void ReadMap(string fileName)
{
    // Read in a map file.
    using (StreamReader reader = new StreamReader(fileName))
    {
        int lineNum = 0;
        string line;
        while ((line = reader.ReadLine()) != null)
        {
            // Get the char array.
            char[] parts = line.ToCharArray();
            for (int i = 0; i < parts.Length; i++)
            {
                _squares[i, lineNum].FromChar(parts[i]);
            }
            lineNum++;
        }
    }
}

You can see that the file is read in line-by-line. Then, the squares array is set from each char. Where is that array, though? Look up at the first code sample--it is declared there. It is a 15 x 15 array of the CompleteSquare object. That is shown in an example earlier too.

Can we use different maps?

It is time for another screenshot, one that shows a different map being used. If you look closely, you will see a black rectangle. That is where the mouse pointer should be. At that point, 15 is the distance according to the algorithm I am describing. The monster would need to walk 15 steps to get to the black rectangle square.

How do we find the path?

First, I will refer you to another page on this site to see how I use enumerators to iterate through the 2D arrays that represent the board. Please look at my article regarding 2D arrays and enumerators for information about that. I will do my best to explain things later on, too.

Now, let's look at the really important part of the algorithm. It implements the A* Pathfinding algorithm in C#, and I have tried to add comments to it. The first part, where I get a point called starting point, uses a simple function that locates the hero on the board (not shown). Next, we set the hero's distance at 0. The algorithm will set all the surrounding squares as 1.

void Pathfind()
{
    // Find path from hero to monster. First, get coordinates of hero.
    Point startingPoint = FindCode(SquareContent.Hero);
    int heroX = startingPoint.X;
    int heroY = startingPoint.Y;
    if (heroX == -1 || heroY == -1)
    {
        return;
    }
    // Hero starts at distance of 0.
    _squares[heroX, heroY].DistanceSteps = 0;

    while (true)
    {
        bool madeProgress = false;

        // Look at each square on the board.
        foreach (Point mainPoint in Squares())
        {
            int x = mainPoint.X;
            int y = mainPoint.Y;

            // If the square is open, look through valid moves given
            // the coordinates of that square.
            if (SquareOpen(x, y))
            {
                int passHere = _squares[x, y].DistanceSteps;

                foreach (Point movePoint in ValidMoves(x, y))
                {
                    int newX = movePoint.X;
                    int newY = movePoint.Y;
                    int newPass = passHere + 1;

                    if (_squares[newX, newY].DistanceSteps > newPass)
                    {
                        _squares[newX, newY].DistanceSteps = newPass;
                        madeProgress = true;
                    }
                }
            }
        }
        if (!madeProgress)
        {
            break;
        }
    }
}

Our algorithm could stop once it finds its destination, obviously. The important detail here is that I only mark a step with a number, if it is a smaller number than the one already on the square. This is because we must always look for the shortest distance and not the longest distance. The longest distance is infinitely long, as you might guess.

How do we "trace" the shortest path?

Here we trace the shortest path from hero to monster. What this code does is follow the smallest number each step of the way, and mark the squares with a true bool if it is part of the shortest path. Look carefully at how we stop the loop, when we hit the SquareContent.Hero square.

private void HighlightPath()
{
    // Mark the path from monster to hero.
    Point startingPoint = FindCode(SquareContent.Monster);
    int pointX = startingPoint.X;
    int pointY = startingPoint.Y;
    if (pointX == -1 && pointY == -1)
    {
        return;
    }

    while (true)
    {
        // Look through each direction and find the square
        // with the lowest number of steps marked.
        Point lowestPoint = Point.Empty;
        int lowest = 100;

        foreach (Point movePoint in ValidMoves(pointX, pointY))
        {
            int count = _squares[movePoint.X, movePoint.Y].DistanceSteps;
            if (count < lowest)
            {
                lowest = count;
                lowestPoint.X = movePoint.X;
                lowestPoint.Y = movePoint.Y;
            }
        }
        if (lowest != 100)
        {
            // Mark the square as part of the path if it is the lowest
            // number. Set the current position as the square with
            // that number of steps.
            _squares[lowestPoint.X, lowestPoint.Y].IsPath = true;
            pointX = lowestPoint.X;
            pointY = lowestPoint.Y;
        }
        else
        {
            break;
        }

        if (_squares[pointX, pointY].ContentCode == SquareContent.Hero)
        {
            // We went from monster to hero, so we're finished.
            break;
        }
    }
}

I am sorry that some pieces are missing from this document, but I have included them all in the download. I do hope my coding style is relatively clear for you. The final piece of code I am going to show you right now sends colors to a custom control that displays the field. That code is what eventually draws all the colored rectangles.

How do we highlight the final path?

We simply take the enum on each square, and then send colors to an object called boardControl1. This next section will discuss some of the code that goes into board control. It was if anything much more difficult to create than the algorithm I am showing you today, but luckily, I had already made it for a different game.

void DrawBoard()
{
    foreach (Point p in Squares())
    {
        int x = p.X;
        int y = p.Y;
        int num = _squares[x, y].DistanceSteps;
        Color setColor = Color.Gainsboro;
        SquareContent content = _squares[x, y].ContentCode;

        if (content == SquareContent.Empty)
        {
            if (_squares[x, y].IsPath == true)
            {
                setColor = Color.LightBlue;
            }
            else
            {
                setColor = Color.White;
            }
        }
        else
        {
            if (content == SquareContent.Hero)
            {
                setColor = Color.Coral;
            }
            else if (content == SquareContent.Monster)
            {
                setColor = Color.Coral;
            }
            else
            {
                setColor = Color.Gray;
            }
        }
        boardControl1.SetHighlight(setColor, x, y);
    }
    boardControl1.Invalidate();
}

Drawing graphics. I am not a graphics guru by any stretch of the imagination, but I have learned how to efficiently draw rectangles and use painting geometry in Windows Forms. The results are what you see in the above two screenshots. (The control that draws the board is only 130 lines long, but it would require a lot of explanation.)

Conclusion

Here we implemented a pathfinding algorithm, but it is very simple and fundamental. I encourage you to download the full source code and play with it. The code is linked is on my source code site. The program can be fun, as the path automatically adjusts itself as you add walls.

Ads by The Lounge