I have implemented A* pathfinding on my map. In order to prevent skipping/jerkiness, the searches get spread over multiple cycles/frames if they take too long. So far, so good.

But the map also needs to be updated once in a while with threats to avoid. I would like to update the threats on the map every 1-2 seconds or so.

Is it prudent to just make the updates to the map while searches might be ongoing...? I would think that it would screw up the search algorithm, but perhaps it is acceptable with incorrect paths once in a while if the program could be kept simpler that way.

If not, should I freeze/clone the map before the search starts. I fear that making copies of a large map could hit performance. There are over 2 mio. edges in my search graph.

To make matters more complicated, the update of the threats on the map takes much longer than 1 frame (due to the 2 mio edges), so this operation also needs to be spread over multiple frames to prevent skipping/jerkiness...

Any advice is appreciated.

What kind of threats are we talking about? E.g. you're calculating the shortest path from A to B for a kitten, and there are wild dogs roaming around. The kitten shall not stumble upon one in his/her journey?

What I would do, would be that divide the map into sections, and when the threats are updated, IF there's a path in a section where a change occured, redo the pathfinding function in only that/those sections.

Quote:

Original post by Calmatory What kind of threats are we talking about? E.g. you're calculating the shortest path from A to B for a kitten, and there are wild dogs roaming around. The kitten shall not stumble upon one in his/her journey?

Yes, exactly.

Quote:

Original post by Calmatory What I would do, would be that divide the map into sections, and when the threats are updated, IF there's a path in a section where a change occured, redo the pathfinding function in only that/those sections.

Although it sounds sensible, it is the sort of complication I was hoping to avoid...

Is it generally accepted in real time games to change the map while searches are going on, or is it a complete no-no...?