Determining and Re-Considering Trapped Targets when Path-finding

Question

I have a game that has multiple path-finding agents (A*) with a grid based map. The player can change the map by constructing walls, floors etc. and the agents will move to construct what the player has requested. I call the tasks that an agent will move to complete build tasks.

I have implemented a simple distance heuristic for when the agent is deciding which build task to pursue. Since there can be 100's of build tasks in the game at any one time, it's not really possible, as far as I can discern, to do a flood-fill to check if the task is reachable for a particular agent before doing a path-finding exercise.

At the moment, if an agent struggles to find a path to a task (for example, imagine the player has surrounded the agent with walls so it cannot escape a room), the task is stored as something that cannot be reached and a new item is looked for. I also flood-fill from the task and maintain a region which contains the task so that any other tasks in this area are not considered.

My problem is, how can I determine when an item can be released from the cannot-be-reached store or when the locked region can be cleared from consideration?

I though about doing some sort of timed expiration so that an item that cannot be reached will eventually be re-considered but this solution has several problems. Another idea I had was to path-find from the target to the agent every so often and if a new path is possible, clear the item and let it be re-considered. Neither of these solutions seem optimal and I feel I am missing something obvious...

Here is a rather lacking diagram of the problem I am trying to convey.

Answer 1

Break your graph up into connected components (See also).

(Image source)

This will have a high initial cost, but recomputation is cheap: when a wall is added, check if it disjointed a connected component; when a wall is removed, check if it connected two-or-more disjointed components. Then to check if one tile can be reached from another, just check if they're in the same connected component. You only need to recheck a "trapped" target when it's part of a component that was just connected to another.

Another option, which would also help with quickly finding the path once you know it exists, would be to use HPA*.