Godot Version
4.5.1
Question
I’m making a tile-based game and I’ll need pathfinding. My first instinct would be to use the built-in AStarGrid2D class. Except I’m going to allow multi-tile actors of varying widths and heights, which AStarGrid2D doesn’t support.
Right now what I’m doing is keeping multiple AStarGrid2Ds around. One base AStarGrid2D for 1x1 actors, and several other AStarGrid2Ds for larger actors that get updated based on the base AStarGrid2D.
Now, I’m updating the base AStarGrid2D frequently in response to actors moving and other terrain alterations like doors opening and closing. So the other AStarGrid2Ds need to be updated to stay in sync with the base AStarGrid2D, which is complex. And that’s just to set tiles as solid or not solid. I soon also want to have tiles with different weights and be able to dynamically alter tile weights too (my actual use case for dynamically altering tile weights is for setting the tiles an actor is standing on as having high weights instead of actually solid like I am currently, since that actor may move soon).
I may also eventually have actors with different types of locomotion, like birds that can cross pits or fish that can only go on water tiles.
So I’ve begun to wonder if I should just ignore AStarGrid2D and write my own AStar pathfinder where I can do whatever I want. I’m worried about the performance though if I use GDScript. Though this is a turn-based game so maybe the impact won’t be that noticeable.
Better to use multiple AstarGrid2D, each adapted to a specific actor type.
I guess if I should indeed keep multiple AStarGrid2Ds around, the question becomes is there an easy way to keep them in sync?
This is what I’m doing currently:
class_name Pathfinder
# Represents the base terrain. Used by 1x1 actors.
var _base_grid: AStarGrid2D
# Grids used by actors bigger than 1x1.
# Actors bigger than 1x1 are positioned by their top-left tile.
var _grids: Dictionary[Vector2i, AStarGrid2D] = {}
...
func set_rect_solid(rect: Rect2i, solid: bool) -> void:
_base_grid.fill_solid_region(rect, solid)
_update_other_grids()
func _update_other_grids() -> void:
var region := _base_grid.region
for actor_size in _grids:
var grid := _grids[actor_size]
grid.clear()
grid.region = region
grid.update()
for x in range(region.position.x, region.end.x):
for y in range(region.position.y, region.end.y):
var cell := Vector2i(x, y)
if _base_grid.is_point_solid(cell):
var block_rect := Rect2i(
cell - actor_size + Vector2i.ONE,
actor_size
)
grid.fill_solid_region(block_rect, true)
# Larger actor's can't get close to the
# bottom and right borders of the map.
var bottom_border := Rect2i(
Vector2i(region.position.x, region.end.y - actor_size.y + 1),
Vector2i(region.size.x, actor_size.y - 1)
)
var right_border := Rect2i(
Vector2i(region.end.x - actor_size.x + 1, region.position.y),
Vector2i(actor_size.x - 1, region.size.y)
)
grid.fill_solid_region(bottom_border, true)
grid.fill_solid_region(right_border, true)
Note that so far I’m only switching tiles as solid or not solid (e.g. for the tiles an actor is standing on, or for doors opening or closing). As I said I also want to add setting and changing the weights of different tiles, so that’ll need to be included in the syncing code.
There’s no way around synching them one by one but it shouldn’t be a problem performance wise for a turn based game.
But overall it’s still better to use the built-in AStarGrid2D class, even if I have to sync multiple AStarGrid2Ds for different types of actors, over hand-rolling my own even for a turn based game?
Depends on your exact use cases but it very likely is as you delegate all pathfinding calculations to fast native code and you don’t need to mess with A* implementation details.
Make it operational with multiple built in grids first. Start thinking about alternatives only if profiling shows that performance in not acceptable.
You don’t need to sync everything in a single frame. You can do it in a worker thread.
Do not optimize prematurely.
2 Likes
It’s not that I think doing my own A-star would improve performance. I’m actually worried it would have worse performance than managing multiple AStarGrid2Ds. I was considering making my own A-star because I thought it would be simpler than managing multiple AStarGrid2Ds given the different types of actors I’ll have.
I don’t see how it would be simpler. Keeping multiple grids would probably be the simplest approach in both cases.
But if you have a clear idea about an implementation that may simplify your use case - go for it.
You don’t see how keeping multiple grids in sync would be more complex than just implementing a custom A-star pathfinder that just checks whatever actor I’m pathfinding for whenever it checks if a tile should be in the path?
If a different actor has different configuration of obstacles then that effectively amounts to a different grid. You could have some sort of layering but that’s again nothing more than multiple girds.
Reasons why you may want to write your own A*:
With your own implementation you can have any kind of node structure that can contain both static (for example terrain) or dynamic (npcs, doors, weather) information.
If you want to run your path-finding in a separate thread then it may be more clear to have your own implementation.
Debugging is easier, you can for example visually show what nodes were checked during the algorithm.
Godot’s implementation doesn’t seem to have any easy way to limit how far the path is searched. Imagine if you have a very large map and the path is not found then in the worst case scenario the search must go through the whole map.
Godot’s implementation is very coordinate-focused. Often when the map consist of nodes that are on equal distance of each other (grid, hexagons) there is no need for coordinates.
You want to educate yourself and understand how the algorithm works.
Reasons to use built-in A*:
While the A* algorithm is only something like 50 lines of code it takes time to understand and implement it correctly. It is easy to make something that seems to work but in reality is really bad performance-wise.
If Godot’s implementation works in your use case then obviously just use it.
2 Likes
If you are updating Astar paths frequently, it might be worth your while to write your own implementation, but instead of AStar go for DStar Lite, which is way more efficient for dynamic path recalculations.