Sign in to follow this  

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

This topic is 2636 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

This topic is 2636 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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