1
DF Gameplay Questions / Increasing framerates... without money - fortress design for fast pathfinding
« on: April 30, 2010, 10:46:05 am »
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:
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?
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?
