A* Pathfinding in 2D Games: A simple Top-down Scenario implemented with MonoGame/KNI

Introduction

In the last article of this series we introduced the A* algorithm and implemented a simple console application in C# for a top-down scenario. As a bonus, there was an interactive example implemented with the MonoGame derivative called KNI. If you don’t know what I’m talking about, then no worries, here it is again:

Click to load app

I know, at the end of the last post, I promised that next time we’d look at how to go from top-down to side-view with gravity and ladders and all that, but I thought it might be cool to shed some light on how the MonoGame version of the application is implemented. And that’s what we’re going to do in this article.

Note

I assume some basic knowledge about how MonoGame works. Ideally, you’ve already built something with MonoGame yourself. If not, I’d recommend going through one of those tutorials.

Requirements

First, let’s list a few functional requirements for the interactive app:

Display the 2D grid with its cells
Support two types of cells: Freely walkable cells and blocked cells that are not walkable
Display the start and target cell
Display the current state of the algorithm, e.g. by showing which cells are currently in the openSet etc.
Add an autoplay option that goes through the steps at a “slow” speed automatically
Also, let the user go through the pathfinding algorithm step by step
Let the user edit the grid, i.e. let the user move that start and target cell around and let them “paint” and erase walls (a.k.a. level editor).

A Wireframe of the GUI

Let’s draw a quick wireframe of the GUI to get an idea of what the final app will look like (of course, you already know what the final app will look like, but look at this awesome sketch):

At the top, you’ll see the 10x10 grid with free and blocked cells. Blocked cells are shown with a crosshatched pattern. The start cell is shown as A and the destination cell as B. Below the grid, we have a control panel with four buttons: “Play/Stop” to automatically execute the algorithm, “Step” for doing one step of the algorithm, “Reset” to reset the algorithm to its initial state, and “Show Parent Relation” for displaying the cells’ relations to their parent cell.

Component Diagram

The app can be broken down into three main parts each of which consists of one or more components: the GUI and user input handling, the data model (which includes the grid and its cells), and a component with the logic, which is based on the A* algorithm. The basic idea is to break the whole thing down into smaller components, with each one ideally responsible for one thing and one thing only (See Single-Responsibility Principle). Another benefit of separating the data and logic from the rendering and user input handling is that it makes the logic easier to unit test.

Let’s illustrate this with a quick component diagram:

The arrows depict the flow of data (or commands) from one component to another.

Let’s code!

The Data Model

Now, let’s get our hands dirty with some code. Unlike the console application, which is something you run once and then it’s done, an interactive application needs to be, well, interactive. This means we need to read user input while the algorithm runs and start and stop the algorithm on the user’s behalf. The current state of the algorithm needs to be displayed and even the grid needs to be editable, which means we need to build a simple level editor.

First, we need to extend the data model. We’ll add a few more properties to the Cell class, which correspond to the current state of the A* algorithm, e.g. we’ll let the cell “know” if it’s in the openSet or later if it’s part of the path, etc.

Note

By the way, you don’t have to manually copy code snippets around. The complete project is available on GitHub.

public class Cell(int x, int y, bool isWalkable)
{
    // Already familiar properties ahead
    public Point Position { get; } = new(x, y);
    public int X => Position.X;
    public int Y => Position.Y;
    public bool IsWalkable { get; } = isWalkable;
    public float CostToTarget { get; set; } = float.PositiveInfinity;
    public float CostFromStart { get; set; } = float.PositiveInfinity;
    public Cell? Parent { get; set; }
        
    // Here come the new properties
    public bool IsOnPath { get; set; }
    public bool IsInOpenSet { get; set; }
    public bool WasInspected { get; set; }
}

Let’s have a quick look at the added properties.

IsOnPath will bet set to true when a path is found and the cell is part of the path.
IsInOpenSet is set to true if the cell is in the openSet.
WasInspected is set to true if the cell was inspected by the algorithm.

In addition, we need a way to reset the cell to its initial state, e.g. in case the user hits the “Reset” button or the A* algorithm needs to start over because the grid changed. For this we add a Reset method to the Cell class:

public class Cell(int x, int y, bool isWalkable)
{
    // ...
    
    public void Reset()
    {
        CostToTarget = float.PositiveInfinity;
        CostFromStart = float.PositiveInfinity;
        Parent = null;
        IsOnPath = false;
        IsInOpenSet = false;
        WasInspected = false;
    }
}

Note

But, isn’t the Cell class doing too much?

One could argue that the new properties (and really all properties that have something to do with the state of the A* algorithm) and the new method shouldn’t be part of the Cell class but should rather be in a data structure of their own. And you could do that, e.g. by letting the Cell class store only its position and whether it’s walkable and then have something like an AStarCell class that inherits from or maybe better decorates the Cell class and adds the additional properties and methods needed for the A* algorithm.

This would definitely help to keep things more separate into single classes (Single-Responsibility Principle, remember?). And guess what, I gave that a shot, but I felt it would be overkill for this relatively simple example and only makes the code unnecessarily complex and it doesn’t really benefit anything. It just adds an additional layer of unnecessary indirection and makes it more complicated to work with.

So, for the sake of simplicity and my own peace of mind we’ll stuff all that into the Cell class and be done with it.

For now, let’s move on to the Grid class and additionally store the start and target positions and do a few sanity checks when setting these. Also, add two convenience properties for getting the start and target cell directly (Note: we’re going to use the MonoGame implementation of Point rather than our own):

public class Grid
{
    private readonly Cell[,] _cells;

    private Point _startPosition;
    private Point _targetPosition;

    public Point StartPosition {
        get => _startPosition;
        set {
            if (_startPosition == value) return;
            if (!IsInsideBounds(value)) return;
            if (!_cells[value.X, value.Y].IsWalkable) return;
            _startPosition = value;
        }
    }
    public Point TargetPosition {
        get => _targetPosition;
        set {
            if (_targetPosition == value) return;
            if (!IsInsideBounds(value)) return;
            if (!_cells[value.X, value.Y].IsWalkable) return;
            _targetPosition = value;
        }
    }

    public Cell Start => _cells[StartPosition.X, StartPosition.Y];
    public Cell Target => _cells[TargetPosition.X, TargetPosition.Y];

    private Grid(Cell[,] cells)
    {
        _cells = cells;
        // ...
    }

    public static Grid CreateFromArray(int[,] map)
    {
        // ...
    }

    public bool TryGetCellAtPosition(Point position, out Cell cell)
    {
        // ...
    }

    private bool IsInsideBounds(Point position)
    {
        var (x, y) = position;
        return x >= 0  && x < _cells.GetLength(0) 
            && y >= 0  && y < _cells.GetLength(1);
    }
}

You might have noticed that the old Grid class had a public property of type Cell[,] with which you could access the grid’s cells array directly. One problem with that approach is that you can, in theory, set individual cells in the array from outside the Grid class and thus break data encapsulation. You could do even something nasty and for example insert a cell with an incorrect position:

grid.Cells[1, 2] = new Cell(17, 8, false); // Yuck!

Now, instead of exposing the array to the outer world, we let the Grid class implement its own indexer so the grid can be used directly as a 2-dimensional array of Cell objects which is quite nice. By omitting the setter it is now impossible to overwrite cells in the array.

public class Grid
{
    // ...

    public Cell this[int x, int y] {
        get {
            if (!IsInsideBounds(new Point(x, y))) {
                throw new IndexOutOfRangeException();
            }
            return _cells[x, y];
        }
    }
   
    // ...
}

You can now do something along the lines of

var cell = grid[3,2];

instead of

var cell = grid.Cells[3,2];

Let’s not forget we need to be able to reset the grid, e.g. when the user tears down a wall. So, let’s add a Reset method which in turn calls the individual cells’ Reset methods:

public class Grid
{
    // ...
    
    public void Reset()
    {
        foreach (var cell in _cells) {
            cell.Reset();
        }
    }
}

The Logic

Now that we’ve updated the data model for the grid and cells, let’s have a look at the A* algorithm. The challenge now is that we need to be able to go through the algorithm step by step. What we need is a method, let’s call it … drum roll … Step, which does one step (or rather one iteration) of the algorithm and then returns:

public class AStarPathfinder(Grid grid)
{
    private List<Cell> _openSet = [];
    private bool _needsInit = true;

    /// <summary>Evaluates one step of the algorithm</summary>
    /// <returns>True if done (i.e. a path was found or there is no path), false otherwise</returns>
    public bool Step()
    {
        if (_needsInit) {
            grid.Start.CostFromStart = 0;
            grid.Start.CostToTarget = GetDistance(grid.Start, grid.Target);
            _openSet = [grid.Start];
            _needsInit = false;
        }

        if (_openSet.Count == 0) return true;

        var current = _openSet.OrderBy(c => c.CostToTarget).First();
        if (current == grid.Target) {
            ReconstructPath(current);
            return true;
        }

        _openSet.Remove(current);
        current.IsInOpenSet = false;

        var tentativeCost = current.CostFromStart + 1;
        foreach (var n in Neighbors(current).Where(n => tentativeCost < n.CostFromStart)) {
            n.Parent = current;
            n.CostFromStart = tentativeCost;
            n.CostToTarget = tentativeCost + GetDistance(n, grid.Target);
            if (_openSet.Contains(n)) continue;

            _openSet.Add(n);
            n.WasInspected = true;
            n.IsInOpenSet = true;
        }

        return false;
    }

    public void Reset()
    {
        grid.Reset();
        _needsInit = true;
    }

    private static void ReconstructPath(Cell current)
    {
        current.IsOnPath = true;

        var walkingCell = current;
        while (walkingCell.Parent != null) {
            walkingCell.Parent.IsOnPath = true;
            walkingCell = walkingCell.Parent;
        }
    }
    
    private static float GetDistance(Cell a, Cell b)
    {
        return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
    }

    private IEnumerable<Cell> Neighbors(Cell cell)
    {
        int[] dx = [-1, 1, 0, 0];
        int[] dy = [0, 0, -1, 1];

        for (var i = 0; i < 4; i++) {
            var checkX = cell.X + dx[i];
            var checkY = cell.Y + dy[i];

            if (grid.TryGetCellAtPosition(new Point(checkX, checkY), out var neighbor) && neighbor.IsWalkable) {
                yield return neighbor;
            }
        }
    }
}

The attentive reader will have noticed that the outer while-loop, which was designed to loop as long as there were still cells in openSet, has disappeared. Instead, the Step method does exactly that, one step (or one iteration to be precise), so each time the method is called, the algorithm advances one step until it is finished which means that either a path was found or there are no more cells in openSet.

Another thing we got rid of is the Path property which was used to store the found path in the earlier version of the class. We don’t need that anymore because the path is now stored in the cells themselves via the Parent and IsOnPath properties, which are updated in the ReconstructPath method:

private static void ReconstructPath(Cell current)
{
    current.IsOnPath = true;

    var walkingCell = current;
    while (walkingCell.Parent != null) {
        walkingCell.Parent.IsOnPath = true;
        walkingCell = walkingCell.Parent;
    }
}

One last thing we needed to change is that when the Step method is called for the very first time or the first time after the grid was reset, we need to do the initialization step, which is done when _needsInit is set to true via the Reset method (which also calls the grid’s Reset method).

public bool Step()
{
    if (_needsInit) {
        grid.Start.CostFromStart = 0;
        grid.Start.CostToTarget = GetDistance(grid.Start, grid.Target);
        _openSet = [grid.Start];
        _needsInit = false;
    }
    
    // ...
}

public void Reset()
{
    grid.Reset();
    _needsInit = true;
}

The rest is pretty much the same, it’s still the A* pathfinding algorithm.

Up until now we have the grid and the A* algorithm capable of doing single iterations. What’s next you ask? I think a good next step is to render the grid and to let the A* algorithm do its work.

Rendering the Grid

What we need is a class that takes the grid and renders it on the screen. The idea is simple: Iterate over the 2-dimensional array of Cell objects and render an appropriate texture with the right color at the right position for each cell.

Note

So far we haven’t touched anything MonoGame-specific (except maybe the Point struct). From here on, some basic knowledge of MonoGame would not hurt, e.g. it would be helpful to know what SpriteBatch, ContentManager or Texture2D are all about, or what the heck the Update and Draw methods do and what on earth GameTime is supposed to be.

Let’s create a class GridRenderer which is responsible for rendering a Grid object.

public class GridRenderer(Grid grid) : IDrawable
{
    private Texture2D? _textureCellFree;
    private Texture2D? _textureCellBlocked;
    private Texture2D? _textureCellStart;
    private Texture2D? _textureCellTarget;
    private SpriteFont? _font;

    public bool IsShowParent { get; set; }

    public void LoadContent(ContentManager cm)
    {
        _textureCellFree = cm.Load<Texture2D>("Textures/CellFree");
        _textureCellBlocked = cm.Load<Texture2D>("Textures/CellBlocked");
        _textureCellStart = cm.Load<Texture2D>("Textures/CellStart");
        _textureCellTarget = cm.Load<Texture2D>("Textures/CellTarget");
        _font = cm.Load<SpriteFont>("Fonts/Font1");
    }
    
    // ...
}

Let us take a brief look at what’s going on here. First of all the GrindRenderer has a dependency on the Grid object it is supposed to render which is passed to the primary constructor.

Next, we have few Texture2D objects (which are basically images), one for each type of cell: “free”, “blocked”, “start” and “target”. These are loaded in the LoadContent method with the use of a ContentManager instance. Because we also want to write down a few numbers, we need a font of type SpriteFont, which is also loaded here. So far, nothing too fancy. Let’s add a Draw method for actually drawing things (also, that’s what the IDrawable interface is about):

public class GridRenderer(Grid grid) : IDrawable
{
    // ...
    
    public void Draw(SpriteBatch spriteBatch)
    {
        foreach (var cell in grid) {
            // Draw that cell already!
        }
    }
    
    // ...
}

We now have a Draw method that is passed a SpriteBatch object which is a MonoGame class for drawing text and sprites. This is where we iterate over the 2-dimensional array of cells … Hold on! … How can we iterate over the grid’s cells when we don’t have direct access to the cells array anymore? Let’s go quickly back to the Grid class and let it implement the IEnumerable interface:

public class Grid : IEnumerable<Cell>
{
    private readonly Cell[,] _cells;
    
    // ...
    
    public IEnumerator<Cell> GetEnumerator()
    {
        for (var x = 0; x < _cells.GetLength(0); x++) {
            for (var y = 0; y < _cells.GetLength(1); y++) {
                yield return _cells[x, y];
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

With that in place we can now indeed simply iterate over the grid’s cells in the Draw method in the GridRenderer class:

public class GridRenderer(Grid grid) : IDrawable
{
    // ...
    
    public void Draw(SpriteBatch spriteBatch)
    {
        foreach (var cell in grid) {
            var position = new Vector2(cell.X, cell.Y) * Constant.TileSize;

            // draw cell
            var texture = GetCellTexture(cell);
            if (texture != null) {
                spriteBatch.Draw(
                    texture: texture,
                    position: position,
                    sourceRectangle: null,
                    color: GetCellColor(cell),
                    rotation: 0,
                    origin: Vector2.Zero,
                    scale: Vector2.One,
                    effects: SpriteEffects.None,
                    layerDepth: 1
                );
            }

            // ...
        }
    }
    
    private Texture2D? GetCellTexture(Cell cell)
    {
        if (!cell.IsWalkable) return _textureCellBlocked;
        if (cell == grid.Start) return _textureCellStart;
        return cell == grid.Target ? _textureCellTarget : _textureCellFree;
    }
    
    private static Color GetCellColor(Cell cell)
    {
        if (cell.IsOnPath) return Color.LightGreen;
        if (cell.IsInOpenSet) return Color.Orange;
        return cell.Parent != null ? Color.Yellow : Color.White;
    }
    
    // ...
}

Inside the foreach loop we determine the appropriate texture for the cell. Then, we calculate the position of the cell on the screen by simply multiplying its position by the size of the (quadratic) texture (or tile). The following call to spriteBatch.Draw() contains one more detail which is getting the color of the cell depending on its status with respect to the current state of the A* algorithm, e.g. whether the cell is in openSet etc. The color is then used to tint the sprite:

If the cell is part of a path, tint it green.
If it’s in the open set for cells to examine, tint it orange.
If it already has a parent cell set, tint it yellow.
In all other cases, tint it white, which means, don’t tint it at all.

Next, add those numbers for the costs to the Draw method:

public class GridRenderer(Grid grid) : IDrawable
{
    // ...
    
    public void Draw(SpriteBatch spriteBatch)
    {
        foreach (var cell in grid) {
            // ...

            // draw numbers
            if (cell.CostFromStart < float.PositiveInfinity) {
                DrawNumber(spriteBatch, cell.CostFromStart, position + new Vector2(2, 1));
            }

            if (cell.CostToTarget < float.PositiveInfinity) {
                DrawNumber(spriteBatch, cell.CostToTarget, position + new Vector2(2, 12));
            }
            
            // ...
        }
    }
    
    private void DrawNumber(SpriteBatch spriteBatch, float number, Vector2 position)
    {
        if (_font == null) return;
        spriteBatch.DrawString(
            spriteFont: _font,
            text: $"{number}",
            position: position,
            color: Color.Black,
            rotation: 0,
            origin: Vector2.Zero,
            scale: Vector2.One,
            effects: SpriteEffects.None,
            layerDepth: 0
        );
    }
    
    // ...
}

Pretty straight forward, no? Last, add that parent relation, i.e. when a cell has a parent then draw a line from the cell to its parent cell:

public class GridRenderer(Grid grid) : IDrawable
{
    // ...
    
    public void Draw(SpriteBatch spriteBatch)
    {
        foreach (var cell in grid) {
            // ...
            
            if (IsShowParent) {
                DrawLineToParentCell(spriteBatch, cell, position);
            }
        }
    }
    
    // ...
    
    private static void DrawLineToParentCell(SpriteBatch spriteBatch, Cell cell, Vector2 position)
    {
        if (cell.WasInspected) {
            spriteBatch.DrawPoint(
                position: position + new Vector2(Constant.HalfTileSize, Constant.HalfTileSize - 1),
                color: Color.DarkSlateGray,
                size: cell.IsOnPath ? 10 : 6,
                layerDepth: 0.5f
            );
        }

        if (cell.Parent == null) return;

        var parentPosition = new Vector2(cell.Parent.X, cell.Parent.Y) * Constant.TileSize;
        spriteBatch.DrawLine(
            point1: position + Vector2.One * Constant.HalfTileSize,
            point2: parentPosition + Vector2.One * Constant.HalfTileSize,
            color: Color.DarkSlateGray,
            thickness: cell.IsOnPath ? 6 : 2,
            layerDepth: 0.5f
        );
    }
}

That’s basically it concerning the rendering of the grid. With what we have now we can run the algorithm once and watch it run until it finds a path from start to target. There isn’t much interaction yet. We’re going to add this in the next section.

Add the Control Panel

First, we’ll add the control panel, which will allow the user to start and stop the automatic execution of the A* algorithm, go stepwise through the algorithm, reset the grid, and toggle the display of the parent relationships. To do this, we need two types of form elements: a button and a toggle (or a checkbox if you will). The button is used to step through the pathfinding process and to reset the grid. Without further ado, here’s the implementation:

public class Button(Texture2D texture, Point position) : IDrawableUpdateable
{
    private bool _isPressed;
    private Rectangle _worldBounds = new(position.X, position.Y, texture.Width, texture.Height);

    public event Action? Clicked;

    public void Update(GameTime _)
    {
        var mouseState = Mouse.GetState();
        if (!_isPressed && mouseState.LeftButton == ButtonState.Pressed && _worldBounds.Contains(mouseState.Position)) {
            _isPressed = true;
            Clicked?.Invoke();
        }
        if (mouseState.LeftButton == ButtonState.Released) {
            _isPressed = false;
        }
    }

    public void Draw(SpriteBatch spriteBatch)
    {
        spriteBatch.Draw(
            texture: texture,
            position: new Vector2(position.X, position.Y),
            sourceRectangle: null,
            color: _isPressed ? Color.White : Color.LightGray
        );
    }
}

Pretty simple, right? The button has a texture (most probably with a fancy icon!) and a position in the game world. It has a Clicked event that fires when the button is clicked, which can be subscribed to. It has a Draw method that draws the button on the screen.

The button logic itself is implemented in the Update method: We read the current state of the left mouse button. If it is pressed in the current frame and wasn’t in the previous frame, plus the mouse pointer is inside the button’s bounding rectangle, then the button is being recognized as clicked and the Clicked event is invoked. To prevent the event from firing repeatedly while the button is pressed, we set the flag _isPressed to true. As soon as the mouse button is released, the flag is reset to false.

Next, we need a toggle which can be switched on and off by clicking on it. Let’s create a Toggle class that’s basically a slightly extended version of the Button class we just looked at:

public class Toggle(Texture2D textureSwitchedOff, Texture2D textureSwitchedOn, Point position) : IDrawableUpdateable
{
    private bool _isPressed;
    private bool _isSwitchedOn;
    private Rectangle _worldBounds = new(position.X, position.Y, textureSwitchedOff.Width, textureSwitchedOff.Height);

    public event Action<bool>? Toggled;

    public void Update(GameTime _)
    {
        var mouseState = Mouse.GetState();
        if (!_isPressed && mouseState.LeftButton == ButtonState.Pressed && _worldBounds.Contains(mouseState.Position)) {
            _isPressed = true;
            _isSwitchedOn = !_isSwitchedOn;
            Toggled?.Invoke(_isSwitchedOn);
        }
        if (mouseState.LeftButton == ButtonState.Released) {
            _isPressed = false;
        }
    }

    public void Draw(SpriteBatch spriteBatch)
    {
        spriteBatch.Draw(
            texture: _isSwitchedOn ? textureSwitchedOn : textureSwitchedOff,
            position: new Vector2(position.X, position.Y),
            sourceRectangle: null,
            color: _isPressed ? Color.White : Color.LightGray
        );
    }
}

The differences to the Button class are:

The toggle has two textures: one for when it is switched off and another one for when it is switched on.
It has an additional flag _isSwitchedOn which is used for … well, you already guessed it.
The event has a bool parameter and is fired whenever the state of the toggle changes from switched on to off and vice versa. The current state after the switch is passed to the delegate.

We need now one more class for the actual control panel:

public class ControlPanel(Point position) : IDrawableUpdateable
{
    private readonly List<IDrawableUpdateable> _formElements = [];

    public event Action<bool>? PlayButtonToggled;
    public event Action<bool>? ShowParentButtonToggled;
    public event Action? StepButtonClicked;
    public event Action? ResetButtonClicked;

    public void LoadContent(ContentManager cm)
    {
        var textureButtonPlay = cm.Load<Texture2D>("Textures/ButtonPlay");
        var textureButtonStop = cm.Load<Texture2D>("Textures/ButtonStop");
        var textureButtonStep = cm.Load<Texture2D>("Textures/ButtonStep");
        var textureButtonReset = cm.Load<Texture2D>("Textures/ButtonReset");
        var textureToggleShowParentOff = cm.Load<Texture2D>("Textures/ToggleShowParentOff");
        var textureToggleShowParentOn = cm.Load<Texture2D>("Textures/ToggleShowParentOn");

        var togglePlay = new Toggle(textureButtonPlay, textureButtonStop, position);
        var buttonStep = new Button(textureButtonStep, position + new Point(80, 0));
        var buttonReset = new Button(textureButtonReset, position + new Point(160, 0));
        var toggleShowParent = new Toggle(textureToggleShowParentOff, textureToggleShowParentOn, position + new Point(240, 0));

        togglePlay.Toggled += PlayButtonToggled;
        buttonStep.Clicked += StepButtonClicked;
        buttonReset.Clicked += ResetButtonClicked;
        toggleShowParent.Toggled += ShowParentButtonToggled;

        _formElements.Add(togglePlay);
        _formElements.Add(buttonStep);
        _formElements.Add(buttonReset);
        _formElements.Add(toggleShowParent);
    }

    public void Update(GameTime gameTime)
    {
        foreach (var formElement in _formElements) {
            formElement.Update(gameTime);
        }
    }

    public void Draw(SpriteBatch spriteBatch)
    {
        foreach (var formElement in _formElements) {
            formElement.Draw(spriteBatch);
        }
    }
}

The class ControlPanel is basically just a container for the two buttons and two toggles. It subscribes to the buttons' and toggles’ events and exposes more meaningfully named events itself, plus it calls their Draw and Update methods.

Make the Grid editable

The last feature we need to add is the grid editor. For that we need to detect mouse clicks and movements in the grid and change the grid accordingly, e.g. switch cells’ statuses from free to blocked or vice versa and make the start and target cells draggable across the grid.

We’ll approach that by implementing a finite state machine by applying the state pattern. The basic idea of the state pattern is to allow an object to alter its behaviour based on which state it currently is in. Each state is implemented in its own class and contains logic only for that state, e.g. there will be a class for when the mouse button is released and another class for when the button was clicked, etc. That again helps with separating concerns and put state-specific behaviour in a separate class rather than stuff everything into a single class.

Here’s a quick sketch of the state machine we’re going to build:

A finite state machine for handling user input in the grid

So, what’s happening here? We start with the mouse button released. When the mouse button is clicked, we need to decide whether we click the start or target cell or a normal cell. If we clicked the start or target cell, we simply keep making the cell the mouse pointer currently is in the start cell or target cell respectively. We do this as long as the mouse button is pressed. Once it’s released, we go back to the initial state. If we clicked a normal cell, we determine whether the cell is free or blocked and we store that information for later use. Now, as long as the button is pressed we make the cell the mouse pointer is in the opposite of what the initial cell was, i.e. if the initial cell was free, then the cells becomes blocked, while already blocked cells keep being blocked. If the initial cell was blocked, then the cell becomes free. That way we can paint and erase walls with the mouse pointer. As soon as the mouse button is released, we go back to the initial state.

As you can imagine, we need at least five classes, one for each state of the state machine in the diagram above. Plus, we need something that holds everything together, keeps track of the current state and also delegates work to it (which is called Context in the state pattern).

For a state class to do its work it needs information about the mouse, i.e. if a button is clicked, which cell the mouse pointer is in and in what cell it was previously (i.e. during the last frame) in. Also, it needs a reference to the grid, because it might need to read and set the start and target cells. We’ll make all that available through the context. In addition, at some point the current state needs to tell the context to transition to another state. Obviously, the state class needs a reference to the context.

Let’s whip up an interface IContext for the context and another interface IState for the state classes (Btw, we’re using the extended mouse state here from MonoGame.Extended):

public interface IContext
{
    MouseStateExtended MouseState { get; }
    Cell CurrentCell { get; }
    Cell? PreviousCell { get; }
    Grid Grid { get; }
    void TransitionTo(IState state);
}

public interface IState
{
    public void Handle(IContext context);
}

Here’s what the context implementation looks like - we’ll use a special dummy value Cell.None for CurrentCell just so it’s never null:

public class Cell(int x, int y, bool isWalkable)
{
    // ...
    
    public static Cell None { get; } = new(0, 0, false);

    // ...
}

public class GridInputContext(Grid grid) : IUpdateable, IContext
{
    private IState _currentState = new ButtonReleasedState();

    public MouseStateExtended MouseState { get; private set; }
    public Cell CurrentCell { get; private set; } = Cell.None;
    public Cell? PreviousCell { get; private set; }
    public Grid Grid { get; } = grid;

    public void TransitionTo(IState state)
    {
        _currentState = state;
    }

    public void Update(GameTime _)
    {
        MouseState = MouseExtended.GetState();
        var gridPosition = MouseState.Position.DivBy(Constant.TileSize);

        if (!Grid.TryGetCellAtPosition(gridPosition, out var cell)) {
            // The mouse pointer isn't in the grid, do nothing.
            return;
        }

        CurrentCell = cell;
        _currentState.Handle(this);
        PreviousCell = cell;
    }
}

You’ll have noticed that there’s a check in the Update method to test whether the mouse pointer is actually inside the grid. If it’s not, we can “pause” the state machine and just stay in the current state, because there’s nothing useful to do when the mouse pointer is outside the grid.

For the sake of brevity, we’ll only look at one concrete state class:

public class ButtonReleasedState : IState
{
    public void Handle(IContext context)
    {
        if (!context.MouseState.WasButtonPressed(MouseButton.Left)) {
            return;
        }

        if (context.Grid.StartPosition == context.CurrentCell.Position) {
            context.TransitionTo(new StartClickedState());
            return;
        }

        if (context.Grid.TargetPosition == context.CurrentCell.Position) {
            context.TransitionTo(new TargetClickedState());
            return;
        }

        if (context.CurrentCell.IsWalkable) {
            context.TransitionTo(new EmptyCellClickedState());
            if (context.Grid.StartPosition != context.CurrentCell.Position
                && context.Grid.TargetPosition != context.CurrentCell.Position
            ) {
                context.CurrentCell.IsWalkable = false;
            }

            return;
        }

        context.TransitionTo(new BlockedCellClickedState());
        context.CurrentCell.IsWalkable = true;
    }
}

I’m going to leave it as an exercise for the reader to figure out what this class does. The other state classes (in fact the whole project) you’ll find on GitHub.

There is one more thing we need to take into consideration. Everytime the grid changes, the A* algorithm has to be restarted. We will solve this as follows:

The Cell class gets an event that fires when the cell changes, i.e. when its walkability changes.
Next, the Grid class gets an event that fires when one of the cells or the position of the start or target cell changes.
Finally, the event of the Grid class is wired to the Reset method of the A* algorithm.

Here is the additional code:

public class Cell(int x, int y, bool isWalkable)
{
    // ...
    
    public event Action? WalkabilityChanged;

    public bool IsWalkable {
        get => _isWalkable;
        set {
            if (value == _isWalkable) return;
            _isWalkable = value;
            WalkabilityChanged?.Invoke();
        }
    }
    
    // ...
}

public class Grid : IEnumerable<Cell>
{
    // ...
    
    public event Action? GridChanged;

    public Point StartPosition {
        get => _startPosition;
        set {
            if (_startPosition == value) return;
            if (!IsInsideBounds(value)) return;
            if (!_cells[value.X, value.Y].IsWalkable) return;
            _startPosition = value;
            GridChanged?.Invoke();
        }
    }
    public Point TargetPosition {
        get => _targetPosition;
        set {
            if (_targetPosition == value) return;
            if (!IsInsideBounds(value)) return;
            if (!_cells[value.X, value.Y].IsWalkable) return;
            _targetPosition = value;
            GridChanged?.Invoke();
        }
    }

    private Grid(Cell[,] cells)
    {
        _cells = cells;
        foreach (var cell in _cells) {
            cell.WalkabilityChanged += () => GridChanged?.Invoke();
        }
    }
    
    // ...
}

You might notice that that’s actually an implementation of the observer pattern.

Note

(Not) unsubscribing from Events

In general, it’s good practice to unsubscribe from events when you no longer need them. In this example, however, we’ll skip the step of unsubscribing for simplicity’s sake, because it’s just one level, if you will, and the “game” is not progressing in the sense that a new level or area needs to be loaded while the current one is being unloaded, or new game objects are being created or existing ones are being destroyed. The only time we would need to unsubscribe is when the whole game ends, in which case everything will end up in data nirvana anyway.

The algorithm’s Reset method is going to be wired up in the next section.

Wiring things up

Good news: We are slowly approaching the well-deserved end of this article. Let’s finally create a class named Pathfinding (how original!) to wire everything up:

public class Pathfinding
{
    private const double StepDelay = 50;

    private readonly int[,] _map = {
        { 0, 0, 1, 0, 0, 0, 1, 0, 1, 0 },
        { 0, 0, 1, 0, 1, 1, 1, 0, 0, 0 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 0, 0, 1, 0, 1, 1 },
        { 1, 1, 1, 1, 0, 1, 1, 0, 1, 0 },
        { 0, 0, 0, 0, 0, 1, 1, 0, 1, 0 },
        { 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
    };

    private readonly GridRenderer _gridRenderer;
    private readonly GridInputContext _gridInputContext;
    private readonly ControlPanel _controlPanel;
    private readonly AStarPathfinder _pathFinder;

    private bool _isPathfindingFinished;
    private double _lastStepOccurredAt;
    private bool _isPlaying;

    public Pathfinding()
    {
        var grid = Grid.CreateFromArray(_map);
        grid.StartPosition = new Point(1, 1);
        grid.TargetPosition = new Point(4, 2);
        grid.GridChanged += Reset;

        _gridRenderer = new GridRenderer(grid);
        _gridInputContext = new GridInputContext(grid);
        _pathFinder = new AStarPathfinder(grid);

        _controlPanel = new ControlPanel(new Point(8, _map.GetLength(1) * Constant.TileSize + Constant.HalfTileSize));
        _controlPanel.PlayButtonToggled += isSwitchedOn => { _isPlaying = isSwitchedOn; };
        _controlPanel.StepButtonClicked += Step;
        _controlPanel.ResetButtonClicked += Reset;
        _controlPanel.ShowParentButtonToggled += isSwitchedOn => { _gridRenderer.IsShowParent = isSwitchedOn; };
    }

    public void LoadContent(ContentManager cm)
    {
        _gridRenderer.LoadContent(cm);
        _controlPanel.LoadContent(cm);
    }

    public void Update(GameTime gameTime)
    {
        _gridInputContext.Update(gameTime);
        _controlPanel.Update(gameTime);

        if (!_isPlaying) return;
        if (_isPathfindingFinished) return;

        var timeSinceLastStep = gameTime.TotalGameTime.TotalMilliseconds - _lastStepOccurredAt;
        if (timeSinceLastStep < StepDelay) return;

        Step();
        _lastStepOccurredAt = gameTime.TotalGameTime.TotalMilliseconds;
    }

    public void Draw(SpriteBatch spriteBatch)
    {
        _controlPanel.Draw(spriteBatch);
        _gridRenderer.Draw(spriteBatch);
    }

    private void Step()
    {
        _isPathfindingFinished = _pathFinder.Step();
    }

    private void Reset()
    {
        _pathFinder.Reset();
        _isPathfindingFinished = false;
    }
}

Let’s now hook this up with the main game class which inherits from MonoGame’s Game class. This should be familiar for you if you’ve already worked with MonoGame and shouldn’t contain any big surprises:

public class PathfindingGame : Game
{
    private readonly Color _backgroundColor = new(35, 36, 37);

    private SpriteBatch _spriteBatch;
    private Application.Pathfinding _pathfinding;

    public PathfindingGame()
    {
        _ = new GraphicsDeviceManager(this);
        Content.RootDirectory = "Content";
    }

    protected override void LoadContent()
    {
        _spriteBatch = new SpriteBatch(GraphicsDevice);

        _pathfinding = new Application.Pathfinding();
        _pathfinding.LoadContent(Content);
    }

    protected override void UnloadContent()
    {
        Content.Unload();
    }

    protected override void Update(GameTime gameTime)
    {
        _pathfinding.Update(gameTime);
        base.Update(gameTime);
    }

    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.Clear(_backgroundColor);

        _spriteBatch.Begin(
            samplerState: SamplerState.PointClamp,
            sortMode: SpriteSortMode.BackToFront
        );
        _pathfinding.Draw(_spriteBatch);
        _spriteBatch.End();

        base.Draw(gameTime);
    }
}

That’s it, you’ve made it! I hope you found this post useful and that it wasn’t too lengthy.

Conclusion

In this blog post, we’ve taken a look into implementing the interactive A* pathfinding app from the last blog post with MonoGame. In the next part of this series, we’ll finally move from the top-down view to a side-view scenario (or so I hope).

A* Pathfinding in 2D Games: A simple Top-down Scenario implemented with MonoGame/KNI

Introduction

Requirements

A Wireframe of the GUI

Component Diagram

Let’s code!

The Data Model

The Logic

Rendering the Grid

Add the Control Panel

Make the Grid editable

Wiring things up

Conclusion

Resources