# 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 on other sites

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 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 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 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 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.

## Create an account

Register a new account

• 9
• 10
• 12
• 10
• 10
• ### Similar Content

• Let's say, on abstract level, the path, namely, A->B->C->D->E is valid, but the agent must choose portal #1 to reach E.... Presumably the agent has chosen portal #2, and go to B, C and D and finally ending up finding itself getting stuck at D and cannot move over to E... The whole computation is wasted. How do I avoid this problem?
thanks
Jack

• There are a bunch of path finding implementations online. But, to be honest, I wasn't much satisfied with  most of them, for one of these reasons:
Dynamic memory allocation in the middle of the algorithm Algorithm that does too much (more than what is needed) Too many files for just a single task So I made this two-files (uastar.c and uastar.h) library: https://github.com/ferreiradaselva/uastar
No memory dynamic allocation. Straight to the point (the README.md explains how to use).
It's nothing biggie, but certainly useful.
Path finder at work:

I'm leaving this in announcements, because I probably won't add more features (it's pretty much done).

• I am not sure I can ask questions about a specific library here, but if you haven't already. I'd like to tag some polys in a navigation mesh that correspond to grass or road etc, I can give an extent to do so, or in another way, I can directly feed a geometry in and the polys are tagged this way. But I am looking into alternative ways such as allowing the user to tag the polys using a text file or bitmap file (like the way heightfields are done).. If I define a area map which is a grayscale  image, and the values range from 0-255, and for example, if the value of the first char is 0, then I can map this index to certain place in the navigation mesh, and say this is a walkable ground etc, unlike heightfields, where you define an image and the resultant thing is some terrain, but when you start off with a bitmap for area map, you end up with what? you see, I had the geometry already, the area map probably doesn't make sense here, same way as the text file thing....
Any ideas?
Jack

• Hello guys, I just registered this site and heard from my lecturer that this a good site to talk about certain topics since my research topic are mostly programmer who are experienced with AI can answer the survey.

The reason of the survey below is to understand which is suitable solution for 2d platformer pathfinding for AI and which one is easier to implement for 2D platformer.

I would appreciate if you guys give your responses for the survey link shared and thank you for spending time answering the survey. Sorry if the survey is a bit hard to understand, I tried to make it understandable as best as I can. Again, thank you!

https://goo.gl/forms/S0etAlAAHL6S5kTI2
• By baabaa
Hello hello. I'm in the preliminary design phase for a space based game, and I need some advice on how to approach the AI side of things.
Here's the situation in a nutshell. Say I'm a space explorer with a spaceship, and I am competing with other space explorers to be the first one to discover things. I have a procedurally generated 2D top-down solar system, and to make things a little simpler, let's say all the planets in the system are static, meaning they are not orbiting their sun. But they all have their gravity wells of varying strength. As a player I have to negotiate newtonian physics around these planets, using engine thrust at the right amounts and timing, to get to where I want. That part is not a problem. I'm also willing to assume non-newtonian rotation so that AI and player do not need to account for appyling torque to get a correct bearing.
So far I have not mentioned whether this is real-time or turn-based and that's because of my uncertainty around AI.
Problem is I'm not sure how to approach the AI side of things either way. Ideally I'd like to have an AI that can optimize trajectory for speed and/or fuel efficiency, but I have been able to find precious little on the topic on the interwebs. The best I've found so far is the following article from a decade ago, and it does not really point to a solution: http://playtechs.blogspot.ca/2007/05/pathfinding-in-space.html
If I can find a good resource on how to pull this off in realtime, I'd like to go that route. At the moment my fallback is using a turn based system for exploration and visualizing the system as a hex grid. Then using A* I could get AI agents to naively assume use of thrust to come to a stand still each time they want to change trajectory, and then add extra thrust to move in the next direction, but I'm worried this would be extremely under-optimized in terms of fuel efficiency and the reach of rival ships as a result. I could also factor in the AI ship's current velocity into the graph search, which would likely greatly increase the search space for pathfinding, but I haven't experimented with it yet to be able to say whether it's viable.
Any thoughts?