Most performant way to check if path is possible?

#1

Since my grid graph changes at runtime, a path might get blocked after an agent already set it as its destination. This mean I have to continuosly check if path is possible, what would be the most performant way to do that on a grid graph?

#2

Hi :slight_smile:
I had similar problem and I think there is no “perfect” solution.

In my opinion you can try these approaches:

  1. Refresh path every X seconds for each unit.
    Pros: Most accurate
    Cons: More units you have, less FPS you got
  2. Save information about all the changes on the map (like adding or deleting building). Loop all the units and their “waypoints”. If change on the map was close enough to one of the waypoints: run “request for new path”.
    Cons: It’s not 100% accurate. They can be a lot of pathfinding request in you have a large group
    Pros: Can be executed asynchronously, so no delay when you place/remove building.
  3. Use two grids (or more). One (main) detailed as possible and the second one not so much. You can then check path every X seconds on “not so much detailed grid”. If it’s different than previous: request for a path on most detailed path.
    Pros: should be a lot faster than point 1
    Cons: depends on your game design
  4. If you request path for every unit in the group, only check path every X seconds for only one unit. If something changed a lot, run “new path request” for all the units in the group.
    Pros: there is a change that this specific unit will had the same path
    Cons: there is not 100% chance that system will detect the changes

I like point 2 idea.
In my option: just do some solution. If it will be a problem then look for optimization. Personally I think that different game design need different approach in terms of pathfinding optimization.

I also recommend to check how Factorio handled pathfinding optimisation

2 Likes
Check when new obstacle appear
#3

Another alternative is to repeatedly go through all nodes in the path and check if any of them are now unwalkable (node.Walkable = false).
I would also recommend recalculating the path every so often because what if a new path opens up that is faster than the one the agent is currently on.

2 Likes
#4

I already recalculate path automatically every 2 seconds with a sensitivity of 10, set to dynamic.

The only problem is when the destination becomes completely unreachable, so I think your suggestion sounds like a good solution. If a node is unwalkable I can then check if the destination is reachable.