TileMap Pathfinding Made Simple (Godot 4 C#)

Hello, this is Chaiz with Team Kobold. Today I thought I’d share a simple demo of the Godot C# API’s for pathfinding. With Godot 4’s new TileMap features, building maps and other tiled assets becomes an attractive in-engine pipeline for your asset creation. If you’re looking for a quick overview of this feature, and you’re like me, you want to skip straight to the programmatic implementation. So for this overview I am focusing on the C# implementation of this feature, and I will assume you are already familiar with setting up your scenes with the relevant nodes and node types. So without delay, lets open up the script for the TileMap node in your scene

Our goal will be to simply find a shortest path between two cells on our TileMap. We will uses Godot’s in-engine AStar2D object to provide the pathing algorithm The overview of this process will be as follows:

1. Load all cells of the TileMap into the AStar2D object
2. Set the cell connections within the AStar2D object.
3. Use the AStar object to query for and return the list of in-order cells from start to finish

First set your local AStar2D object.

using Godot;

public partial class AstarTileMap : TileMap
{
  private AStar2D _aStar = new AStar2D();
}

AStar2D uses a point ID number hash to store its coordinates, rather than a direct call to cell coordinates. So you may find yourself needing to jump between cell IDs and cell coordinates as you expand your code to be more robust. You can request cell coordinates corresponding to a point ID and visa versa. I’d recommend checking out the documentation for this first, but you may get the gist of it after seeing the code below.

You can use the inherent GetUsedCells function to return an iterable list of your populated cells. I’m personally fond of implementing the .NET HashSet to store our cell vectors for convenience in some future features you may implement.

// Includes
using System.Collections.Generic;

// Class fields
private HashSet<Vector2> _usedCells;

private void InitializeTileMap()
{
  _usedCells = new HashSet<Vector2>();

  foreach(Vector2 cell in GetUsedCells(0);)
  {
    _usedCells.Add(cell);
    _aStar.AddPoint(_aStar.GetAvailablePointId(), cell);
  }
}

Now, you can get more crafty with how you order these events for sure, but for clarity, I’m splitting it all out into discreet steps.

For the next step, we need to connect all the cells within the AStar map, thankfully this is simple enough in the script. The issue is determining which cells traversable neighbors in my TileMap, Obviously trivial if your grid is a plain cartesian map with every cell’s North/East/South/West neighbor being a connecting cell. You may find trouble if you use an isometric TileMap and find see your map indexes are… weird.

For those dealing with isometric maps, check out the TileSet Tile Layout properties on your TileMap. You can simplify the indexing to a 45 degree shifted XY map with no zig-zagging.

Connect the cells based on neighbor’s relative index.

private Vector2i _neighbor_N = new Vector2( 0, -1);
private Vector2i _neighbor_E = new Vector2( 1,  0);
private Vector2i _neighbor_S = new Vector2( 0,  1);
private Vector2i _neighbor_W = new Vector2(-1,  0);

foreach (Vector2 point in _usedCells)
{
  // Fill the cardinal directions
  Vector2i neighbor;

  neighbor = point + _neighbor_N;
  if (_usedCells.Contains(neighbor))
  {
    _aStar.ConnectPoints(_aStar.GetClosestPoint(point), _aStar.GetClosestPoint(neighbor));
  }

  neighbor = point + _neighbor_E;
  if (_usedCells.Contains(neighbor))
  {
    _aStar.ConnectPoints(_aStar.GetClosestPoint(point), _aStar.GetClosestPoint(neighbor));
  }   
   
  // etc...
}

You may consider keeping the Vector2 coordinates of relative neighbors somewhere more dynamic like a const static list to iterate over. Also you can insert possible logic for linking cells across a map, or adding diagonal connections. Do consider, if you use diagonal directions, don’t forget to check the “cardinal” neighbors for traversable movement, lest you suscept your characters to squeezing between outer room corners.

Finally, invoking the AStar2D object to find the path for you is simple enough.

public Vector2[] GetPath(Vector2 startCell, Vector2 targetCell)
{
  Vector2[] returnPath = _aStar.GetPointPath(_aStar.GetClosestPoint(startCell), 
                                             _aStar.GetClosestPoint(targetCell));

  return returnPath;
}

Happy coding!