Pathfinding—Efficient Checking for Changes


I’ve written my own A* pathfinding script for some basic NPCs, but the game I’m attempting to make allows the player to make changes to the environment that the NPCs are pathfinding in. Updating the navmesh isn’t a problem, but I’m not sure how to tackle updating a given NPCs already-calculated path. Obviously I don’t want to just update the whole path for every NPC every frame.

The code I’ve written has the calculated path put into path<>, which is worked through from location to location. The best I’ve come up with is to do a full check of the path<> list regularly (every Update?) and compare it with the navmesh to see if anything has changed.

So my question is, how resource-intensive is checking through a list (there’d be multiple NPCs, too) every frame? If anyone knows of a better way and would like to share, that would also be appreciated.

A good solution is always do the easy solution. Only then profile and optimize.

Some alternatives that come to me now:

a) Don’t compute each frame, but each random time elapsed. Start like each second and reduce until it is not noticable and have a good performance.

b) Create a trigger that notify for changes. It is like a inverse index, when you create a path you register what area you are interested, and when you change your navimesh you notify only that paths.

c) Don’t bother for changes, but let the unity be smart enough to detect when its path is wrong and recompute it or change its behaviour (like attack walls).

d) Update your navimesh and its paths in same algorithm (crazy :P)

e) It is a very common approach split your problem into pathfinding (big picture) and steerning (local avoidance).