AStarGrid2D doors implementation

Help Navigation
,
1

Godot Version

4.4.1 stable

Question

I’m using AStarGrid2D for path finding and I’ve got design issue and some doubts about which approach to use.

In my game, characters pass through doors, and the question is how to implement a path check if any door is closed to one character but not to others. Door states kept in

var door_states: Dictionary[Vector2i, Dictionary] = {Vector2i(1,1):{&"forbidden_users":[], &"forbidden_factions":[]}}

Does it performance wise to set impassable doors as solid points and get path, and then if path searched for character that can go through the door set solid for doors as false (possibly in same frame). May be there is a totally different way (except of use NavigationAgent)?

mainly question about performance of function set_point_solid()

2

I think you may be prematurely optimizing. I think there are unknown factors here that would affect performance. You would really need to test and profile different implementations.

I would think most of the performance cost comes from the actual path lookup.

  1. If you have very large rooms and the astar path lookup after the door is costly, then setting the doors to solid might make sense.
  2. If you have a lot of different users and different factions, then constantly updating the door cells between each of their path finding checks might be costly.
  3. If you have a lot of doors it may not make sense to update points for doors that are irrelevant to the path that needs to be calculated.

These factors simply make it difficult to know what is better or not.

To share another approach. I would look at this video by Tynan Sylvester of Ludeon Studios: https://www.youtube.com/watch?v=RMBQn_sg7DA

For Rimworld, they used a concept of regions (rooms would be a region) and only did path finding to calculate routes from one region to the next. This would be complicated to implement compared to the solutions you are exploring, but it’s another way to do what you’re looking to do.

1 Like
3

I like the idea of regions, keeping enlisted goods for a region and, for instance, to sort them by distance and pick one that meets conditions like if has_item(item) and then get AStarGrid2D path to that item. It gave me some tips, thank you! @withersail