Best way to determine if an AStar path is interrupted if a building is placed on it?

Unity Engine
1

I have a simple AStar class that calculates a path between two Vector2 locations. I can also add new obstacles to the scene and update the grid so NPC’s avoid them when a new path is calculated.

The problem is, if I add an obstacle to the scene on top of an existing calculated path that an NPC is using, they are not aware of that new obstacle and walk right through it. I don’t want to recalculate all the NPC paths each time I add a new obstacle, so what kind of ways could I tell if a path needs recalculating in these kind of situations?

I was thinking of keeping a list of all cells in the grid and updating it with a NPC id whenever a cell was included in its calculated path. Then, when an obstacle is added, I check the cells I’m adding the obstacle to and if an NPC is found, I recalculate that it’s path.

Has anyone done something similar?

2

Well if you are using a A* path method, that means you are working with a grid, and cells.
Every assets should be listed into each cell, a huge library with your cells. I do like it that way.
Then if you add an asset in a cell, it’s asset’s list is updated as well.
From here you already know which is filled.
Then you run a quick test from the entity’s trajectory cell list and if found it, then evaluate a new path removing that cell from the cell available.

3

Thanks Sama-van. The problem is, although the NPC’s path is calculated using the Grid, the result of the path is just stored in an array which only the NPC knows about.

I wrote some pseudocode last night and will try adding it in this week. I’ll keep a separate dictionary with a key of the cell id and a value that is an array of NPC’s. When I add a new building to the grid I can check if any of the cells that I’m marking as non-walkable have an NPC list in the dictionary at that cell id. I think that should work

1 Like
4

Ma[quote=“_6, post:1, topic: 791144, username:_6”]
I was thinking of keeping a list of all cells in the grid and updating it with a NPC id whenever a cell was included in its calculated path. Then, when an obstacle is added, I check the cells I’m adding the obstacle to and if an NPC is found, I recalculate that it’s path.
[/quote]

Yep this seems prudent. This way you’ll only recalculate paths for NPCs whose paths have been interrupted. Just be careful with the bookkeeping:

  • Make sure you add the NPC reference to every space on its path when you calculate a path
  • Make sure you recalculate paths for ALL NPCs whose paths are interrupted.
  • Make sure you remove the NPC references from all the spaces on their original path when you recalculate paths.
1 Like