Bite-Sized Godot: Easier pathfinding with AStarGrid2D

Sample project

NOTE: Today’s sample project is actually a small playground to play around with AStarGrid2D, so there’s a bit more going on than usual, but it should let you really see what this class can offer.

If you’ve used Godot’s AStar2D class, then you’ll know that while it’s a perfectly serviceable, all-purpose solution, it can leave a bit to be desired for grid-based games due to its generic nature. You have to manually add each cell, the connections to surrounding cells, and indirectly lookup cells (whether by a hash function, the get_closest_point function, etc) since node ids are arbitrary as far as the algorithm is concerned.

New to Godot 4, though, is the AStarGrid2D class, which implements A* pathfinding specifically for 2D grids and brings along a few useful features, including some performance improvements.

The Basics

Setting everything up is as easy as creating an instance, defining the size of the grid and its cells (allowing you to get both the grid cell and actual position of the nodes in a path), and then calling update() to prepare it for pathfinding with these parameters. This example from the Godot docs shows it nicely:

var astar_grid = AStarGrid2D.new()
astar_grid.size = Vector2i(32, 32)
astar_grid.cell_size = Vector2(16, 16)
astar_grid.update()

# prints (0, 0), (1, 1), (2, 2), (3, 3), (3, 4)
print(astar_grid.get_id_path(Vector2i(0, 0), Vector2i(3, 4)))
# prints (0, 0), (16, 16), (32, 32), (48, 48), (48, 64)
print(astar_grid.get_point_path(Vector2i(0, 0), Vector2i(3, 4)))

You’ll also notice that cell ids aren’t arbitrary in AStarGrid2D, but are simply the locations of the cell in the grid, making it easy to match up with tilemaps and other grid solutions.

By default, all cells are connected to one another, which is a bit boring. To mark a cell as impassable, you can call set_point_solid() and set the cell value to true:

var astar_grid = AStarGrid2D.new()
astar_grid.size = Vector2i(32, 32)
astar_grid.cell_size = Vector2(16, 16)
astar_grid.update()

astar_grid.set_point_solid(Vector2i(1, 1), true)

# prints (0, 0), (0, 1), (1, 2), (2, 3), (3, 4)
print(astar_grid.get_id_path(Vector2i(0, 0), Vector2i(3, 4))) 

Tweaking things

There’s three properties that drive how the optimal solution is found: the default heuristic, use of diagonals, and jumping. The why and how of A* pathfinding is a discussion for another time, so I’ll be keeping things fairly high level and just focused on usage here. If you do want to dive in further in the meantime, Red Blob Games has some great articles on A* pathfinding.

The default heuristic

The heuristic determines how the optimal path is calculated, and the options are listed, with the formulas, in the docs. We can choose the heuristic to use by setting astar_grid.default_heuristic. I’m only going to give a very brief overview of the available heuristics here, but if you want to dive deeper there’s a great article on A* heuristics by Amit Patel.

• Manhattan: For uses where diagonal movement is not allowed. Calculates the travel cost using right corners between nodes.
• Chebyshev: Useful for diagonal movement that’s snapped to the grid. Ie movement in eight directions: north, south, east, west, northeast, southeast, northwest, southwest. Diagonal movement costs the same as orthogonal movement
• Octile: Another diagonal movement heuristic for moving along the grid. Diagonal movement cost slightly more than orthogonal movement.
• Euclidean: Useful when diagonal movement is allowed at any angle (ie you want to move over a grid, but don’t need to snap to it perfectly). Calculates the cost using the straight line distance between nodes.

Other than Manhattan distance, which is the obviously different one since it doesn’t allow for diagonal movement, these heuristics can seem pretty similar, and you may often find their output to not be that different, but the differences will appear in the right circumstances so play around with them and see what makes the most sense for your game. And if that’s not a good enough answer, here’s what Amit recommends: Manhattan for four-directional movement, Octile or Chebyshev for eight-directional movement, and anything other than Manhattan if movement is allowed in any direction.

Diagonals

The diagonal_mode property determines how valid diagonal movement is determined. We once again have four options to choose from:

• Always: Any diagonal movement between two open cells is allowed.
• Never: Movement will always be orthogonal and diagonally located neighbors will not be taken into consideration.
• At least one walkable: At least one cell must be open along the diagonal path. This prevents trying to walk between the corners of two walls, for instance.
• Only if no obstacles: No obstacles can exist around a diagonal. This will prevent moving diagonally along an obstacle.

Jumping

The jumping_enabled setting enables Jump Point Searching, which is an established method for optimizing A* pathfinding for the uniformly weighted grid that AStarGrid2D uses. Because this algorithm “jumps” over open areas, you’re only returned the location of each jump as opposed to a list of every cell along the path when this mode is enabled, but this mode can give you a nice performance improvement, especially in fairly open maps.

Wrapup

And that’s it for the AStarGrid2D class. Not a lot to it, which is what makes is so much nicer to work with in a grid-based context compared to the AStar2D class. Really, the only downside to it is that you must use a grid with uniform costs, which works great for basic pathfinding but may not always result in the best solution for more complicated uses where you want to discourage, but not prevent, traversing certain cells. In such an instance, you’ll want to go with the AStar2D class or roll your own solution.

I’ve covered most of what the AStarGrid2D class has to offer, but there is a little bit more you may want to know about so be sure to check out the docs to learn more or go play with the sample project to see everything I’ve discussed in action.