Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: [1] 2 3 4

Author Topic: Increasing framerates... without money - fortress design for fast pathfinding  (Read 21666 times)

hermano

  • Bay Watcher
    • View Profile

One of the most processing time consuming aspects of df is the pathfinding. Pathfinding happens all the time, and with rising population and fortress size its negative impact on game speed rises exponentially.
In this thread I want to explore which fortress designs speed up pathfinding, what decisions will slow down the game considerably, talk a little about pathfinding methods (without getting to technical) and tell you why your dwarfs always take the stone two z-levels above (and 80 steps away) instead of the stone three steps away on the same z-level. I have not seen serious threads about this so far.
If you disagree with my conclusions or have anything worthwhile to add, please do so. (Also I'm not a native speaker, so this text might suck in many different ways...)

Whats coming up (just skip what you are not interested in):
1. About pathfinding - and which method toady probably uses
2. What does that mean for fortress design?
3. What you should do (also for tldr folks)
4. Burrows


1. About pathfinding - and which method toady probably uses

In our everyday life we have to make decisions which path to take again and again, and we are pretty good at this. When we want to get a book from a shelf we just go there in a straight path, if something is in the way we step around it. It seems so trivial that it is at first glance hard to understand why computers are so slow at pathfinding, why they find inefficient paths (why don't you just go there stupid dwarf!?) or why they would select a suboptimal target (there is a log right next to you, idiot!).
Unlike humans computers do not have intelligence, they don't have instinct or experiences to fall back on. All a computer does is compute, so to solve a problem we have to describe it and the way to solve it in mathematical terms. There are three things to consider: we have to find a path at all (if possible, otherwise find out that there is no path), we want the shortest path and we want to find it fast. Finding the shortest path and finding a path as fast as possible often conflicts, for the game the best solution is to find a path that is somewhat good and is found as fast as possible.

Lets talk about two methods that are commonly used. I will show some pictures of a small program that demonstrates pathfinding algorithms - you will find it here: http://www.stefan-baur.de/cs.web.mashup.pathfinding.html.

The first one is called Dijkstras algorithm. This one is good to find the shortest path even to a target that is at a unknown position.
Lets look at a 2d fortress first which is made up of walkable tiles and unwalkable tiles. We also have a starting point, our carpenter dwarf who needs a log wood of wood, and a target which is a log of wood lying around somewhere on the map.

The method works this way (simplified):
- Check all accessible tiles next to the dwarfs position and mark down for them how many steps were needed to get there and from which other tile we found them.
- Repeat this for all tiles next to the tiles we checked in the last iteration (excluding neighboring tiles we already checked) until we find a log.
Have a look at this picture, the green tile is our dwarf, the red one is the (closest) log, light grey tiles are ones that have been checked, yellow tiles show the path chosen:


As you see the path is pretty good, but many many tiles had to be checked. This method would find the stone 3 tiles away from your mason instead of the one 80 steps away on the z-level above him. Some people around here call it 'flood filling' and it takes a serious amount of time to find a path with it. It is pretty obvious that this method is not used by toady, it is just too inefficient, it is better to have a game that actually is playable, even when it means that dwarfs make (seemingly) stupid decisions all the time.

The other method is called A*, and here is how it works:
Again we have a starting position, a target and an 2d fortress area.
A* uses Dijkstras method but adds a trick to speed up the process. We first guess a good target, then we preferably check tiles that bring us closer to the target (and ignore other tiles if possible).
The guessing method (or heuristic) commonly used is the manhattan method. In our example we check for all logs how far they are in a (pretty) direct line from our starting point. We do this by computing x-distance + y-distance (in 3d we also add z-distance). This is a very fast way, as it just needs a few additions and substractions. It will get slower if there are lots of logs (or lets say more realistically thousands of stones) that have to be checked.

This tells us why the stupid dwarfs always prefer the stone that is closer in a direct line, ignoring how long the path to that location is: We have one stone that is two z-levels away from our dwarf, so the computed distance is 2 ( 0 + 0 + 2), the other one, that we would prefer, is one y-step and two z-steps away, so the computed distance is 3 ( 2 + 1 + 0) - that fact that the dwarf has to make 80 steps instead of 2 is just ignored.

Now that we have a target we do the following (again, simplified):
- Check all accessible tiles next to the dwarf and mark down for them how many steps it took to get there, how far away they are from the target (again calculating with the manhattan method) and the sums of both previous values. Also mark from which tile we found them.
- Now find the tiles with the lowest sum - these are tiles which brought us closer to the target and are the fewest steps away from our starting point - and check their neighbors. Ignore other tiles for now unless their sum is low.
- Stop when we found the target an check which way lead us there.

Have look at this picture:

You will see there are no grey tiles, we ignored every tile that didn't bring us closer to our target. Now this is much faster.

Our starting point will not always be the dwarf, it may be a log that has to be transported, our target will be the closest idle dwarf with hauling enabled then, the method stays the same.

A side note that might be important:
Spoiler (click to show/hide)

Toadys pathing implementation obviously deviates from the pure A*. First there are ways to set different pathing costs (the cost of a step to a tile will change depending on what traffic selection you make, high traffic will be preferred in the calculations, low will be avoided somewhat, restricted zones will avoided a lot). What other changes he might have made and which data structures he uses (which seriously impact the speed of calculations) is hard to say.

There is one other thing. When dwarfes have found their path they will merrily use that and only check tiles next to them to avoid other dwarfs or find out if the path is still walkable. If that path is closed by channeling, building walls, water, magma they will just cancel their current job next to the obstacle and look for something else to do. When an enemy shows up they will continue their path until they get close to them, then cancel what they were doing and run away. Otherwise the path would have to be calculated again and again, which would take just to much computing time.

2. What does that mean for fortress design
Lets have a look at a few scenarios.
First lets look again at the situation where a direct path is available:


Now we put something in the way:


As you see there are grey arrows now. We had to check several tiles as they might have produced a good path. So any blocked tile on the path will increase checked tiles and thus computing time. The most efficient fort design then would be one where there is always a direct path between two points. For 3d this means that every tile of your fort should be a stair, this does not only produce the shortest path between all two tiles (ignoring ramps for a moment), but it will also lead to the fastest pathfinding solutions. Of course this is not possible, but you can have a lot of stairs at least.
(Unless toady uses the traditional A* which has higher costs for diagonal steps, then this would be a less efficient decision, but I suppose he is too clever for that.)

If he used the Dijkstra method this would be a horrible design, as others have noted in other threads. But using Dijkstra would be a horrible decision in itself (and we can already rule that out).
So one thing to remember: Your craftsdwarf will chose a resource that is closest in x+y+z direction, ignoring the length of the path to get there. So just build stairs next to your workshops, this will decrease the length of the path and the computing cost of finding that path.

Another scenario, here a target is not accessible:


As you see every (damn) tile is checked. Toadys method will probably stop at some point before checking every tile of the map.
So you should never wall off resources, never restrict pathing to resources and not close your drawbridge. If you do you should forbid all unaccessible items. Forbidding items might also exclude them from the manhattan process of finding the closest resource, so forbidding is your friend, just in case forbid everything you don't need.

And another scenario, here we have two tunnels that are for the most part equally good at bringing us closer to our target. But one of them does not actually lead to the target:


As you see there are some tiles checked that don't actually lead to our target (you might also imagine that as two z-levels).
Lets have a look if we have more openings (i.e. a stair between z-levels):


Much better. So again, connect the parts of your fort and build more stairs, especially if there are several paths that get close to possible targets.
Another solution would be to set low or restricted traffic for sections that are rarely or never used. Remember to forbid items that are in inaccessible parts of the fort when forbidding traffic. Targets behind low traffic areas will be harder to find and cost more computing power, but if these areas are rarely used this might be worth it as it speeds up all other pathfinding.
Also mark areas that will often be the main passageways for your dwarfs as high traffic zones. This will speed up pathfinding by avoiding other (seemingly more direct) paths that don't lead to probable targets (but you already know that you should never build walls and have stairs everywhere :) ).

3. What you should do (for tldr folks)
If my assumptions above are correct:
- Have as many direct paths in your fortress as possible. Including lots of stairs.
- Have as few things in your fort as possible or forbid everything that is not needed.
- Use traffic restrictions to avoid path calculations that lead in the right directions but don't lead to probable targets.
- Have no things in areas that are walled of, are behind closed doors, behind rivers or magma, etc. Or at least forbid everything in those locations. Also forbid things that are in restricted traffic areas and are currently not needed.

If I'm wrong and toady uses pathing costs multiplied by 1.4 for diagonal steps:
This would change the situation quite a bit (and shame on toady if this is the case, it's unnecessary if I'm not mistaken). Having as many direct paths as possible might not speed up pathfinding, but instead slow it down.

- Create a minimal number of possible paths by assigning high and restricted traffic areas. If there are logs lying on the surface paint a high traffic path to them and paint restricted traffic areas around them. This will reduce pathfinding time.
- Again have as few things in your fort and forbid everything that is not needed.
- And again have no inaccessible things that are not forbidden.

4. Burrows
Depending on the implementation burrows might speed up pathfinding a lot.
If dwarfs look for items in their burrow first they will find the stone next to them instead of the one a few z-levels above (and 80 steps away) outside the burrow. This will also reduce pathinfinding time.
You could assign burrows for woodhaulers, that include just the location of logs, the path that leads there, the woodpile and some point with food and beds. If tiles outside of burrows are not checked before everything in the burrow has been checked this might give a huge speed increase.
You no longer have to forbid items that are currently not used if there are items of the same kind in the burrow.
I actually had not much time to play with the new version, and I'm scared away by all the hassle to get military dwarfs to train for now. But it might be interesting to check how much of an effect burrows have. But it depends a lot on the way toady has implemented this. If df has, for example, a list of all stones in a burrow, finding a stone in the burrow would be really fast. If all stones have flags to which burrow they belong and df would have to check all existing stones to find one that is in a burrow this would be horribly slow.

So, what fortress designs would you recommend, based on your experience and (hopefully) educated guesses? Was something in this text to obscure for you?
« Last Edit: May 03, 2010, 05:42:03 am by hermano »
Logged

Kuraudo

  • Bay Watcher
    • View Profile

Thanks for the incredibly informative and thought provoking post - after reading this, I will most certainly be making several changes to my standard layouts so as to better facilitate pathfinding!
Logged

Razzums

  • Bay Watcher
    • View Profile

A++ thread.
Logged
ey

hermano

  • Bay Watcher
    • View Profile

Thanks for the incredibly informative and thought provoking post - after reading this, I will most certainly be making several changes to my standard layouts so as to better facilitate pathfinding!

I'll have to add that, while I'm working in computer science, I'm not an expert on pathfinding. So some of my conclusions might not be quite right. It would be nice if somebody with more experience dropped by.
Logged

Marconius

  • Bay Watcher
    • View Profile

I hardly think I'm more of an expert, but I have studied basic pathfinding algorithms as well as more complex AI methods. The A* algorithm (or some variant of it) certainly seems like a likely candidate for pathfinding in the game.

A few things that may be present, as examples... it's possible when a workshop is constructed or a stockpile is designated, the shortest route between the two (if the two are relevant) are calculated. This would mean dwarves working in a Kitchen would always know where the nearest food stockpile is, and would thus be able to walk over there without need to map out a new path.

Such small tweaks -probably- improve performance when it comes to pathfinding, but it would require extensive testing to see if it really makes a difference.
Logged

Ethos

  • Escaped Lunatic
    • View Profile

One thing about the walling off resources bit. It seems (from my experience years of experience in dwarf fortressing) that inaccesible items don't have a huge effect fps. You will get a short stutter in fps from the dwarves finding new tasks and pathfinding all at once, but after that they seem to happily ignore the areas they can no longer go. This wasn't always the case. Back in the 2d version if you locked a door to something a dwarf wanted they would occasionally retry the pathing and spit out an error announcement. Now you'll only get that message if you block their path when they were already headed there. Whether there is still a small drain on the cpu from inaccesible items or not, I have no idea. I know next to nothing about programming, this is all based on observation.

One exception is animals, they will continue to attempt to path through a door over and over causing pretty significant fps issues at times. Again, it's better than it was back in the 2d days, but it's something to keep in mind with animals roaming free.

My theory (just a theory, like I said I have no programming experience to back this up with) is that all items do a routine pathfinding of the entire landscape. Updating when the landscape changes. It's probably more complicated then that but it seems possible.

Say you craft a statue and you go to build it on the other end of your fortress. The game tells you have many steps away the statue is from where you're trying to build it. Go somewhere the statue can't reach, the other side of a river for instance, and it'll simply say it's inaccesible. Build a thousand statues and it'll tell you the distance each one is from you chosen build site. The fact that the game can give you the distance to thousands and thousands of rocks in an instant when you build a wall suggests to me that it's not calculating on the fly but rather has the information on hand already.
Logged

BurnedToast

  • Bay Watcher
    • View Profile

This post is great and should be stickied

Using your tips I designated some traffic zones and added a few extra stairways and got a bit of a framerate increase! (not huge, but maybe 10% - 15% or so).
Logged
An ambush! curse all friends of nature!

Ivar360

  • Bay Watcher
    • View Profile

This post is great and should be stickied

Logged

Scribble

  • Bay Watcher
    • View Profile

Quote
This post is great and should be stickied

Seconded, at least posted on the wiki.
Logged

HammerDave

  • Bay Watcher
    • View Profile

Great article, but I think there might be another factor when there are large numbers of an item.

One thing I've noticed that throws a wrench in the works is that workshop tasks often seem to pick the newest item of that type, no matter where it is.  I've got a whole pile of some ore in veins right by the magma smelters, and then find another vein of the same ore all the way on the edge of the map, and they seem to consistently go for the freshly mined ore instead of the relatively nearby stuff.

This would imply that there might be a data structure with the most recent N objects of a type, and it tries to path to one of those first before it goes looking everywhere for one.  The paradox is that if you build something from the build menu, it seems to know the exact locations.  But looking at that further, the most it ever shows is 99 in the count.  I'd guess that the hypothetical data structure has 100 entries, and if the nearby stuff is more than 100 items of that type old, pathfinding won't find it.
Logged

Jurph

  • Bay Watcher
  • Minister of Belt-fed Weaponry
    • View Profile

Another addendum:  In large rooms with multiple small entrances and exits (like legendary dining halls) I have seen my FPS increase after designating high-traffic zones that connect all of the doors.  In dorms with lots of twisty zig-zags, it might be worthwhile designating a high-traffic path to a "common room" and then restricting the rest of the dorm.  Dorfs will still sleep there, but they won't path in looking for a way out of the tunnel complex.  If you think of a high-traffic zone as a rail or a notch in the floor that the dwarves tend to stay in (like lazy little marbles) it's easy to figure out where they'll need help.
Logged
Dreambrother has my original hammer-shaped Great Hall.  Towerweak has taken the idea to the next level.

hermano

  • Bay Watcher
    • View Profile

I hardly think I'm more of an expert, but I have studied basic pathfinding algorithms as well as more complex AI methods. The A* algorithm (or some variant of it) certainly seems like a likely candidate for pathfinding in the game.

A few things that may be present, as examples... it's possible when a workshop is constructed or a stockpile is designated, the shortest route between the two (if the two are relevant) are calculated. This would mean dwarves working in a Kitchen would always know where the nearest food stockpile is, and would thus be able to walk over there without need to map out a new path.

Such small tweaks -probably- improve performance when it comes to pathfinding, but it would require extensive testing to see if it really makes a difference.

Pregenerating paths is a great way to speed up pathfinding in many games, as you'll have to check just a few waypoints instead of possibly thousands of tiles. The problem with df is, that changing the landscape is a central game element. This means that pregenerated paths may become invalid or that new, shorter, paths open up. The game would have to check these paths all the time (unless it would be acceptable, that dwarfs would behave much more stupid then now), which is hardly better than finding paths for every dwarfs job.
In a way dwarfs are currently much more intelligent than humans in an always changing environment. When we once found a path we will remember it, when it is out of sight and being closed we will probably not know about it until we try that path again and find a wall in our way. When a dwarf choses his path he will already know about this change - they have a great traffic message channel, that keeps them up to date.

Another possible solution is what blue byte did with the older settlers games. Here the player had to build roads and waypoints that the haulers would use then. If you created bad paths and the hauling was inefficient it was your fault. I'm not sure if df players would accept all the administrative and boring tasks neccessary for that even if it sped up the game. And with high traffic zones we already have a tool that allows to speed up the game if we take the time to paint them. With the init settings we can even change the pathing costs for different traffic zones, and can for example increase the likelyhood that dwarf will take our high traffic zones by increasing the values for the other zones.


Quote
One thing about the walling off resources bit. It seems (from my experience years of experience in dwarf fortressing) that inaccesible items don't have a huge effect fps. You will get a short stutter in fps from the dwarves finding new tasks and pathfinding all at once, but after that they seem to happily ignore the areas they can no longer go. This wasn't always the case. Back in the 2d version if you locked a door to something a dwarf wanted they would occasionally retry the pathing and spit out an error announcement. Now you'll only get that message if you block their path when they were already headed there. Whether there is still a small drain on the cpu from inaccesible items or not, I have no idea. I know next to nothing about programming, this is all based on observation.

Toady has been working on the game for years and probably found some solutions that we will not find by thinking about the problems for a few moments. I really can not say what he might be doing there. A straightforward solution for inaccessible items would be to remove them from a list of the accessible items and check from time to time if their status has changed. But as soon as we wall off one dwarf we would get problems with that. For this dwarf all items are inaccessible, so when he tries to haul them they would be removed even though all other dwarfs can access them. If have not yet tested if forbidding unaccessible items speeds up the game, thats just what seemed reasonable looking at the pathfinding. It's great if he already solved that problem, it means less forbidding routines for us.

Quote
My theory (just a theory, like I said I have no programming experience to back this up with) is that all items do a routine pathfinding of the entire landscape. Updating when the landscape changes. It's probably more complicated then that but it seems possible.
This would mean then that building a wall in a large fortress with thousands of items would create a huge slowdown while the paths are being updated. Having more dwarfjobs would not slow down the game much, as all paths are already created. This does not match with my game experience, so I would think that is unlikely. However keeping a list of paths that are used often and check if they might lead the dwarf to his target might speed up the game and would be close to your idea of keeping pregenerated data.

Quote
Using your tips I designated some traffic zones and added a few extra stairways and got a bit of a framerate increase! (not huge, but maybe 10% - 15% or so).
Ha, it's great to hear that the ideas actually have an effect in the game :).

Quote
One thing I've noticed that throws a wrench in the works is that workshop tasks often seem to pick the newest item of that type, no matter where it is.  I've got a whole pile of some ore in veins right by the magma smelters, and then find another vein of the same ore all the way on the edge of the map, and they seem to consistently go for the freshly mined ore instead of the relatively nearby stuff.
Hmmm, if have not experienced that in the game yet. My stonemasons seem to grab the stone they think is closest, seemingly without caring how long ago it has been mined. Are you sure the vein they ignore is not a different metal (for example hematite and magnetite have the same color, are both iron ores - but with a hematite smelting job they will ignore magnetite; edit: wait, they don't have the same color, lets say galena and silver then)?

Quote
This would imply that there might be a data structure with the most recent N objects of a type, and it tries to path to one of those first before it goes looking everywhere for one.  The paradox is that if you build something from the build menu, it seems to know the exact locations.  But looking at that further, the most it ever shows is 99 in the count.  I'd guess that the hypothetical data structure has 100 entries, and if the nearby stuff is more than 100 items of that type old, pathfinding won't find it.
It's not unlikely that toady uses the Dijkstra algorithm to find the closest materials for constructions. Dwarfjobs, goblin victims, etc. are assigned many times per second in a large fortress, so speed is important there. The player will build constructions only every few seconds (and only when he constructs something at all) so wasting half a second then is not much of a problem. Also all dwarf action will be paused during that time, so there is computing power available.

Quote
Another addendum:  In large rooms with multiple small entrances and exits (like legendary dining halls) I have seen my FPS increase after designating high-traffic zones that connect all of the doors.  In dorms with lots of twisty zig-zags, it might be worthwhile designating a high-traffic path to a "common room" and then restricting the rest of the dorm.  Dorfs will still sleep there, but they won't path in looking for a way out of the tunnel complex.  If you think of a high-traffic zone as a rail or a notch in the floor that the dwarves tend to stay in (like lazy little marbles) it's easy to figure out where they'll need help.
Right, thats the way it should be done. I suppose careful traffic planning and zone designation is one important aspect of fortress design, one I neglected for the most part in my previous forts.

Actually I'm a bit slowish today, so what I wrote there might not be too insighful, sorry then.

Edit: Having a short look it seems there have been a few nice developments in pathfinding algorithms in recent years. For example an algorithm for 3d-pathfinding in changing environments that is claimed to be 10 times faster than optimized A* (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.7041&rep=rep1&type=pdf if anybody is interested). So when toady decides it is time to have another look at his pathfinding routines df could become a lot faster.
« Last Edit: May 01, 2010, 09:11:48 am by hermano »
Logged

Moleculor

  • Bay Watcher
    • View Profile

I think I do remember 'newest first' being something I saw in 40d. It's been a long time though, and I don't know if it's in v31, since I've hardly touched that.
Logged

se5a

  • Bay Watcher
    • View Profile

When a dwarf gets a job, say smelt ore for example - does he go for the closest ore to himself at the time the job gets assigned to him, or the ore that is closest to the building?




Somewhat OT: I loved the original settlers, making roads was fun! there's a good little (or not so little) open source clone called widelands that's quite good.
Logged

Lord Darkstar

  • Bay Watcher
    • View Profile

When a dwarf starts to work on a stone required crafts or mason work, he'll grab the nearest stone and take it with him to the workshop, rather than go to the workshop, then find the nearest stone. So the first stone in the workshop can be anythng in the fortress, but the rest will be taken normally from near the workshop--- so long as that dwarf is working in the workshop.

It may be a similar process for ores going to the smelter, but I haven't paid attention to those recently, so I can't say that is true for 31.
Logged
learn to give consolations to frustrated people
What is this, a therapy session? We don't need to console someone because they're upset about a fucking video game. Grow a beard, son, and take off those elf ears!
Pages: [1] 2 3 4