Effects & Systems

Implementing Pathfinding

Pathfinding lets characters decide how to reach a target without walking through walls. This tutorial builds on tilemaps by treating each tile as a walkable or blocked grid cell, then using Breadth-First Search and A* to find a route. By the end you will have a complete MonoGame sample where clicking a target tile makes an agent calculate an A* path and walk along it.

Representing the walkable grid

Most tile-based pathfinding starts with a grid. A simple bool[,] works when every walkable tile has the same cost: true means walkable, false means blocked. If mud, roads, water, or stairs should cost different amounts, use an int[,] or float[,] cost grid instead.

using Microsoft.Xna.Framework;

const int GridWidth = 10;
const int GridHeight = 8;

// true = walkable, false = wall.
bool[,] walkable = new bool[GridWidth, GridHeight];
for (int y = 0; y < GridHeight; y++)
{
    for (int x = 0; x < GridWidth; x++)
        walkable[x, y] = true;
}

walkable[4, 2] = false;
walkable[4, 3] = false;
walkable[4, 4] = false;

// Alternative: 0 = blocked, 1 = normal, 3 = expensive terrain.
int[,] cost = new int[GridWidth, GridHeight];
Point start = new Point(1, 1);
Point goal = new Point(8, 6);

💡 Keep the grid in tile coordinates, not pixels. Convert between tile coordinates and screen positions only at the edges of your system, just like a tilemap renderer.

Breadth-First Search

Breadth-First Search is perfect for unweighted grids where every move has the same cost. It expands outwards from the start using a queue, remembers visited cells, stores where each cell came from in a Dictionary<Point,Point>, then reconstructs the path from goal back to start.

using System.Collections.Generic;
using Microsoft.Xna.Framework;

public static class BreadthFirstSearch
{
    private static readonly Point[] Directions =
    {
        new Point(0, -1), new Point(1, 0), new Point(0, 1), new Point(-1, 0)
    };

    public static List<Point> FindPath(bool[,] walkable, Point start, Point goal)
    {
        var frontier = new Queue<Point>();
        var visited = new HashSet<Point>();
        var cameFrom = new Dictionary<Point,Point>();

        frontier.Enqueue(start);
        visited.Add(start);

        while (frontier.Count > 0)
        {
            Point current = frontier.Dequeue();
            if (current == goal)
                return ReconstructPath(cameFrom, start, goal);

            foreach (Point direction in Directions)
            {
                Point next = new Point(current.X + direction.X, current.Y + direction.Y);
                if (!InBounds(walkable, next) || !walkable[next.X, next.Y] || visited.Contains(next))
                    continue;

                visited.Add(next);
                cameFrom[next] = current;
                frontier.Enqueue(next);
            }
        }

        return new List<Point>();
    }

    private static bool InBounds(bool[,] walkable, Point cell) =>
        cell.X >= 0 && cell.Y >= 0 &&
        cell.X < walkable.GetLength(0) && cell.Y < walkable.GetLength(1);

    private static List<Point> ReconstructPath(Dictionary<Point,Point> cameFrom, Point start, Point goal)
    {
        var path = new List<Point>();
        Point current = goal;

        while (current != start)
        {
            path.Add(current);
            current = cameFrom[current];
        }

        path.Add(start);
        path.Reverse();
        return path;
    }
}

⚠️ Caution: BFS finds the shortest path only when every movement cost is equal. If one tile costs more than another, switch to Dijkstra or A* with movement costs.

A* search

A* improves on BFS by preferring cells that look closer to the goal. It tracks g (cost from start), h (estimated cost to the goal), and f = g + h. For 4-directional grid movement, the Manhattan heuristic is ideal: abs(dx) + abs(dy).

The open set can be a PriorityQueue<Point,int> on .NET 6+ or a simple List<Point> scan for older target frameworks. The sample below uses the list scan so it works broadly with MonoGame projects.

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;

public readonly struct Node
{
    public Node(Point position, int g, int h)
    {
        Position = position;
        G = g;
        H = h;
    }

    public Point Position { get; }
    public int G { get; }
    public int H { get; }
    public int F => G + H;
}

public static class AStar
{
    private static readonly Point[] Directions =
    {
        new Point(0, -1), new Point(1, 0), new Point(0, 1), new Point(-1, 0)
    };

    public static List<Point> FindPath(bool[,] walkable, Point start, Point goal)
    {
        var open = new List<Point> { start };
        var cameFrom = new Dictionary<Point,Point>();
        var gScore = new Dictionary<Point,int> { [start] = 0 };
        var closed = new HashSet<Point>();

        while (open.Count > 0)
        {
            Point current = TakeBestOpenCell(open, gScore, goal);
            if (current == goal)
                return ReconstructPath(cameFrom, start, goal);

            closed.Add(current);

            foreach (Point direction in Directions)
            {
                Point next = new Point(current.X + direction.X, current.Y + direction.Y);
                if (!InBounds(walkable, next) || !walkable[next.X, next.Y] || closed.Contains(next))
                    continue;

                int tentativeG = gScore[current] + 1;
                if (gScore.TryGetValue(next, out int knownG) && tentativeG >= knownG)
                    continue;

                cameFrom[next] = current;
                gScore[next] = tentativeG;
                if (!open.Contains(next))
                    open.Add(next);
            }
        }

        return new List<Point>();
    }

    private static Point TakeBestOpenCell(List<Point> open, Dictionary<Point,int> gScore, Point goal)
    {
        int bestIndex = 0;
        int bestF = int.MaxValue;
        int bestH = int.MaxValue;

        for (int i = 0; i < open.Count; i++)
        {
            Point cell = open[i];
            var node = new Node(cell, gScore[cell], Manhattan(cell, goal));

            if (node.F < bestF || (node.F == bestF && node.H < bestH))
            {
                bestIndex = i;
                bestF = node.F;
                bestH = node.H;
            }
        }

        Point best = open[bestIndex];
        open.RemoveAt(bestIndex);
        return best;
    }

    private static int Manhattan(Point a, Point b) =>
        Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);

    private static bool InBounds(bool[,] walkable, Point cell) =>
        cell.X >= 0 && cell.Y >= 0 &&
        cell.X < walkable.GetLength(0) && cell.Y < walkable.GetLength(1);

    private static List<Point> ReconstructPath(Dictionary<Point,Point> cameFrom, Point start, Point goal)
    {
        var path = new List<Point>();
        Point current = goal;

        while (current != start)
        {
            path.Add(current);
            current = cameFrom[current];
        }

        path.Add(start);
        path.Reverse();
        return path;
    }
}

⚠️ Warning: Do not use Euclidean distance for a strict 4-directional grid unless you understand the trade-off. Manhattan distance matches up, down, left, and right movement and keeps A* focused.

Reconstructing and smoothing paths

Reconstruction follows cameFrom backwards from the goal, then reverses the result. The path can then be simplified by removing points that do not change direction. This keeps the agent's route readable while preserving the same grid route.

using System.Collections.Generic;
using Microsoft.Xna.Framework;

public static List<Point> KeepOnlyCorners(List<Point> path)
{
    if (path.Count <= 2)
        return new List<Point>(path);

    var smoothed = new List<Point> { path[0] };
    Point previousDirection = new Point(
        path[1].X - path[0].X,
        path[1].Y - path[0].Y);

    for (int i = 2; i < path.Count; i++)
    {
        Point direction = new Point(
            path[i].X - path[i - 1].X,
            path[i].Y - path[i - 1].Y);

        if (direction != previousDirection)
        {
            smoothed.Add(path[i - 1]);
            previousDirection = direction;
        }
    }

    smoothed.Add(path[path.Count - 1]);
    return smoothed;
}

💡 This corner-only smoothing is safe for grid paths. More advanced line-of-sight smoothing must test walls between points, or the agent may cut through blocked tiles.

Moving an agent along a path

Once A* returns a List<Point>, move the agent towards the centre of the next tile. Use delta time so movement speed is measured in pixels per second. When the agent reaches a waypoint, advance to the next one.

using System.Collections.Generic;
using Microsoft.Xna.Framework;

const int TileSize = 32;
Vector2 agentPosition = new Vector2(48, 48);
float speedPixelsPerSecond = 120f;
List<Point> path = new List<Point>();
int pathIndex = 0;

void FollowPath(GameTime gameTime)
{
    if (pathIndex >= path.Count)
        return;

    Vector2 target = CellCentre(path[pathIndex]);
    Vector2 toTarget = target - agentPosition;
    float distance = toTarget.Length();
    float step = speedPixelsPerSecond * (float)gameTime.ElapsedGameTime.TotalSeconds;

    if (distance <= step)
    {
        agentPosition = target;
        pathIndex++;
    }
    else
    {
        agentPosition += Vector2.Normalize(toTarget) * step;
    }
}

Vector2 CellCentre(Point cell) =>
    new Vector2(cell.X * TileSize + TileSize / 2f, cell.Y * TileSize + TileSize / 2f);

Complete example: click-to-move pathfinding

This complete Game1.cs generates a tile grid, wall tiles, and a 1×1 pixel texture in code. Click a walkable target cell and the agent computes an A* path, highlights the route, then walks to the destination.

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;

public class Game1 : Game
{
    private const int TileSize = 32;
    private const int GridWidth = 20;
    private const int GridHeight = 14;
    private const int AgentSize = 18;

    private GraphicsDeviceManager _graphics;
    private SpriteBatch _spriteBatch;
    private Texture2D _pixel;
    private bool[,] _walkable;
    private List<Point> _path = new List<Point>();
    private int _pathIndex;
    private Vector2 _agentPosition;
    private MouseState _previousMouse;

    public Game1()
    {
        _graphics = new GraphicsDeviceManager(this);
        _graphics.PreferredBackBufferWidth = GridWidth * TileSize;
        _graphics.PreferredBackBufferHeight = GridHeight * TileSize;
        Content.RootDirectory = "Content";
        IsMouseVisible = true;
    }

    protected override void Initialize()
    {
        _walkable = CreateGrid();
        _agentPosition = CellCentre(new Point(1, 1));
        base.Initialize();
    }

    protected override void LoadContent()
    {
        _spriteBatch = new SpriteBatch(GraphicsDevice);
        _pixel = new Texture2D(GraphicsDevice, 1, 1);
        _pixel.SetData(new[] { Color.White });
    }

    protected override void Update(GameTime gameTime)
    {
        if (Keyboard.GetState().IsKeyDown(Keys.Escape))
            Exit();

        MouseState mouse = Mouse.GetState();
        if (mouse.LeftButton == ButtonState.Pressed && _previousMouse.LeftButton == ButtonState.Released)
            TrySetTarget(new Point(mouse.X / TileSize, mouse.Y / TileSize));

        _previousMouse = mouse;
        FollowPath(gameTime);
        base.Update(gameTime);
    }

    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.Clear(new Color(13, 17, 23));

        _spriteBatch.Begin();
        DrawGrid();
        DrawPath();
        DrawAgent();
        _spriteBatch.End();

        base.Draw(gameTime);
    }

    private static bool[,] CreateGrid()
    {
        var walkable = new bool[GridWidth, GridHeight];
        for (int y = 0; y < GridHeight; y++)
        {
            for (int x = 0; x < GridWidth; x++)
                walkable[x, y] = true;
        }

        for (int y = 2; y < 12; y++)
            walkable[7, y] = false;

        for (int x = 10; x < 18; x++)
            walkable[x, 6] = false;

        walkable[7, 5] = true;
        walkable[13, 6] = true;
        return walkable;
    }

    private void TrySetTarget(Point targetCell)
    {
        if (!InBounds(targetCell) || !_walkable[targetCell.X, targetCell.Y])
            return;

        Point startCell = PositionToCell(_agentPosition);
        List<Point> newPath = AStar.FindPath(_walkable, startCell, targetCell);
        if (newPath.Count == 0)
            return;

        _path = KeepOnlyCorners(newPath);
        _pathIndex = _path.Count > 1 ? 1 : 0;
    }

    private void FollowPath(GameTime gameTime)
    {
        if (_pathIndex >= _path.Count)
            return;

        Vector2 target = CellCentre(_path[_pathIndex]);
        Vector2 toTarget = target - _agentPosition;
        float distance = toTarget.Length();
        float step = 120f * (float)gameTime.ElapsedGameTime.TotalSeconds;

        if (distance <= step)
        {
            _agentPosition = target;
            _pathIndex++;
        }
        else if (distance > 0f)
        {
            _agentPosition += Vector2.Normalize(toTarget) * step;
        }
    }

    private void DrawGrid()
    {
        for (int y = 0; y < GridHeight; y++)
        {
            for (int x = 0; x < GridWidth; x++)
            {
                var rect = new Rectangle(x * TileSize, y * TileSize, TileSize - 1, TileSize - 1);
                Color colour = _walkable[x, y] ? new Color(30, 41, 59) : new Color(2, 6, 23);
                _spriteBatch.Draw(_pixel, rect, colour);
            }
        }
    }

    private void DrawPath()
    {
        for (int i = _pathIndex; i < _path.Count; i++)
        {
            Point cell = _path[i];
            var rect = new Rectangle(cell.X * TileSize + 8, cell.Y * TileSize + 8, TileSize - 16, TileSize - 16);
            _spriteBatch.Draw(_pixel, rect, Color.Gold);
        }
    }

    private void DrawAgent()
    {
        var rect = new Rectangle(
            (int)(_agentPosition.X - AgentSize / 2f),
            (int)(_agentPosition.Y - AgentSize / 2f),
            AgentSize,
            AgentSize);

        _spriteBatch.Draw(_pixel, rect, Color.DeepSkyBlue);
    }

    private static List<Point> KeepOnlyCorners(List<Point> path)
    {
        if (path.Count <= 2)
            return new List<Point>(path);

        var smoothed = new List<Point> { path[0] };
        Point previousDirection = new Point(path[1].X - path[0].X, path[1].Y - path[0].Y);

        for (int i = 2; i < path.Count; i++)
        {
            Point direction = new Point(path[i].X - path[i - 1].X, path[i].Y - path[i - 1].Y);
            if (direction != previousDirection)
            {
                smoothed.Add(path[i - 1]);
                previousDirection = direction;
            }
        }

        smoothed.Add(path[path.Count - 1]);
        return smoothed;
    }

    private bool InBounds(Point cell) =>
        cell.X >= 0 && cell.Y >= 0 && cell.X < GridWidth && cell.Y < GridHeight;

    private static Point PositionToCell(Vector2 position) =>
        new Point((int)(position.X / TileSize), (int)(position.Y / TileSize));

    private static Vector2 CellCentre(Point cell) =>
        new Vector2(cell.X * TileSize + TileSize / 2f, cell.Y * TileSize + TileSize / 2f);
}

public readonly struct Node
{
    public Node(Point position, int g, int h)
    {
        Position = position;
        G = g;
        H = h;
    }

    public Point Position { get; }
    public int G { get; }
    public int H { get; }
    public int F => G + H;
}

public static class AStar
{
    private static readonly Point[] Directions =
    {
        new Point(0, -1), new Point(1, 0), new Point(0, 1), new Point(-1, 0)
    };

    public static List<Point> FindPath(bool[,] walkable, Point start, Point goal)
    {
        var open = new List<Point> { start };
        var cameFrom = new Dictionary<Point,Point>();
        var gScore = new Dictionary<Point,int> { [start] = 0 };
        var closed = new HashSet<Point>();

        while (open.Count > 0)
        {
            Point current = TakeBestOpenCell(open, gScore, goal);
            if (current == goal)
                return ReconstructPath(cameFrom, start, goal);

            closed.Add(current);

            foreach (Point direction in Directions)
            {
                Point next = new Point(current.X + direction.X, current.Y + direction.Y);
                if (!InBounds(walkable, next) || !walkable[next.X, next.Y] || closed.Contains(next))
                    continue;

                int tentativeG = gScore[current] + 1;
                if (gScore.TryGetValue(next, out int knownG) && tentativeG >= knownG)
                    continue;

                cameFrom[next] = current;
                gScore[next] = tentativeG;
                if (!open.Contains(next))
                    open.Add(next);
            }
        }

        return new List<Point>();
    }

    private static Point TakeBestOpenCell(List<Point> open, Dictionary<Point,int> gScore, Point goal)
    {
        int bestIndex = 0;
        int bestF = int.MaxValue;
        int bestH = int.MaxValue;

        for (int i = 0; i < open.Count; i++)
        {
            Point cell = open[i];
            int h = Math.Abs(cell.X - goal.X) + Math.Abs(cell.Y - goal.Y);
            var node = new Node(cell, gScore[cell], h);

            if (node.F < bestF || (node.F == bestF && node.H < bestH))
            {
                bestIndex = i;
                bestF = node.F;
                bestH = node.H;
            }
        }

        Point best = open[bestIndex];
        open.RemoveAt(bestIndex);
        return best;
    }

    private static bool InBounds(bool[,] walkable, Point cell) =>
        cell.X >= 0 && cell.Y >= 0 &&
        cell.X < walkable.GetLength(0) && cell.Y < walkable.GetLength(1);

    private static List<Point> ReconstructPath(Dictionary<Point,Point> cameFrom, Point start, Point goal)
    {
        var path = new List<Point>();
        Point current = goal;

        while (current != start)
        {
            path.Add(current);
            current = cameFrom[current];
        }

        path.Add(start);
        path.Reverse();
        return path;
    }
}

dotnet build
dotnet run

Performance cautions

• Recompute only when needed. Run pathfinding when the target changes, the map changes, or the agent becomes blocked — not every frame.
• Cap the search. Large maps should limit node expansions per request or split work across frames to avoid a visible hitch.
• Use the right open set. A simple list scan is fine for small grids; use PriorityQueue<Point,int> on .NET 6+ or a binary heap for larger maps.
• Handle diagonals deliberately. Diagonal movement costs about sqrt(2), not 1. Also prevent cutting through blocked corners.
• Cache paths carefully. Cached results become invalid when doors open, walls move, or tile costs change.

⚠️ Caution: MonoGame itself does not supply pathfinding. Keep the algorithm separate from rendering so you can unit test it and reuse it for enemies, companions, and cursor previews.

💡 Older MonoGame target frameworks may not include System.Collections.Generic.PriorityQueue<TElement,TPriority>. Either target .NET 6+ or keep a small list-scan implementation until the grid becomes large enough to justify a custom heap.

Next steps

• Creating a Tilemap
• Finite-State Machine
• Collision Detection
• Back to all Code Samples