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.