Sign in to follow this  
captain_crunch

Spreading pathfinding over multiple frames and updating the graph...

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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...?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this