Jump to content
  • Advertisement
Sign in to follow this  
suliman

Pathfinding in city builders. Store the paths?

Recommended Posts

Hi

In a game like stronghold with many workers going back and forth from a workplace to a dropoff-point for example, would I store the path and then use it backwards to not have to redo pathfinding all the time? If the moving units in the city doesnt block movement, very often I could just reuse the old path. Only if i run into a wall (if the player constructs a new building in the path of the old workers) will I recalculate the path.

Workers in old age of empires for example, do they pathfind every time they go back to drop off gold in the storage?

Thanks!
Erik

Share this post


Link to post
Share on other sites
Advertisement

Normally, it depends on the algorithm you're using (you can alter those in whatever way you want though)
Let's take Flow Fields as an example.
For a single path, the Grid is only calculated once. That is, as long as you don't need a different path, you just don't need to update the grid.

Share this post


Link to post
Share on other sites
23 minutes ago, suliman said:

would I store the path and then use it backwards to not have to redo pathfinding all the time?

Sure, why not? The worst case is that the path becomes invalidated and then you have to redo the pathfinding - just like you would have had to anyway.

 

Share this post


Link to post
Share on other sites

Note that if your rate of path searching is relatively low, you don't even need to cache paths. Cache invalidation can be tricky, so if you're not doing hundreds of path plans per game tick, you can totally get away with not caching at all and just recomputing paths from scratch every time you need to.

Share this post


Link to post
Share on other sites
7 hours ago, ApochPiQ said:

if you're not doing hundreds of path plans per game tick, you can totally get away with not caching at all

Yeah i've already got a system for cueing pathfinding so I plan on starting like this (allowing max 10 or whatever pathfinds per tick) and see if that works out (no noticable impact on performance). Just wanted to ask the forum anyway to see if I was planning this correctly.

Thanks guys!
Erik

Edited by suliman

Share this post


Link to post
Share on other sites

And if you environment isn't that dense and fairly regular, the complexity of your paths is going to be small. Not like you are plowing through 1000 node paths.

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  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!