FPS has been driving me crazy lately, so I've been doing a lot of thinking and research on pathfinding to see if there's room for improvement. I've made a couple of interesting discoveries. I'm assuming a familiarity with A* in the post, but the conclusions and suggestions should be useful even if you don't understand the math.
Most of the discussions on A* pathfinding seem to be incorrect in a small but important way. A* performs best when the actual path distance is close to the estimated distance ("manhattan" distance in our case). With the default traffic weight of 2, that proves not to be the case. Short, unimpeded straight-line paths in a large open space are actually surprisingly expensive--but I think there are ways to fix this.
I ran a series of experiments. I used two 1-tile wood stockpiles with just a single log between them, set to take from links only. I keep reversing the give/take settings on the stockpiles to get the dwarves to haul the log back and forth between them, and I watch the path they take. For the experiments below, use the following key:
S/D - source/destination
. - floor, normal traffic
H/L/R - high/low/restricted traffic
= - for a few experiments, used to mark the path taken by the dwarf.
Experiment 1 - demonstrate that default settings search too widely for a potential path.
Here's the setup:
.....HHHHHHHHHHHHHHH.....
....H...............H....
...H.................H...
..H...................H..
.H.....................H.
.........................
..S...................D..
.........................
The high-traffic path starts behind the straight-line path between source and destination, but the dwarves take it anyway. The high-traffic path is indeed the "shortest" path under traffic rules, so it's what we want A* to find, but searching for it proves to be wasteful. The reasoning for this is fairly straightforward. The manhattan metric tells us that the path from source to destination is at least 20 steps. By the time you've moved 3 tiles directly towards the destination, you've taken 6 steps, and the manhattan metric tells us we have at least 17 to go (for a total of 23). This makes Urist McPathfinder say "shucks, I'm already 3 steps behind, maybe I should try some of those other paths." So he ends up looking up, down, and backwards for a better path. He gives slight preference to the arcs of the path that are closer to the destination, but not enough for it to really matter at a large scale.
This could be really problematic. In a fortress with no traffic designations, essentially every path ever plotted is going to be calculated like a "flood fill" path. It's examining all kinds of alternatives that are never used. In CS terms, we're examining O(N^2) tiles for a path of length N. If you set your normal traffic pattern to cost 1 (or paint your whole fortress as high traffic), straight-line paths become O(N). Summary: if you have a fairly open fort that's well-designed for compatibility with A*, setting the "normal" traffic cost to 1 could have a pretty significant impact on your FPS--and it's probably good for your fort whether or not you've paid attention to A* in your fort design.
Since 1 is the lowest traffic cost you can set, you might think we've hit a wall here, and that there's no way to set higher-priority paths than this. That's only half true. Although the game doesn't let you set lower traffic costs, d_init.txt will let you set a traffic weight of 0--or even a negative number (!)--for your next embark. (I can't see how to set this manually once your fort has started; it's clearly in the save files somewhere, though. If someone can figure it out, it'd be a great contribution to science, as it would let you use the techniques below to test FPS impact on a mature fort.)
This opens up all sorts of interesting possibilities. For all the experiments below, I use the following weights: High traffic: 0. Normal: 1. Low: 2. Restricted: -1.
Aside: how this "breaks" A*.
When we start doing this, A* stops being a "shortest path" algorithm. A* is only a real shortest-path algorithm when the heuristic (the manhattan metric) is "admissible", which means that it never over-estimates the distance to the goal. When we introduce the possibility for a tile that costs 0 steps to walk over, this stops being the case. A* doesn't cease to function--it just ceases to be a "shortest path" algorithm. It's just a generic "path" algorithm. This is actually good, because for FPS purposes we don't necessarily care about finding the "shortest" path--we want the "quickest" (to compute) path, so long as it isn't too much longer than the shortest one.
Experiment 2: unfindable 0-cost paths
The setup:
.....HHHHHHHHHHHHHHH.....
....H...............H....
...H.................H...
..H...................H..
.H.....................H.
.........................
..S===================D..
.........................
This is the exact same setup as experiment #1, except that we've altered the traffic weights. Now, the dwarves take the straight-line path. The high-traffic path is a shorter path, but the dwarves never find it because they're being too efficient in their pathfinding. The manhattan metric tells them the target is 20 tiles away, and they find a perfect path to it that exactly hits that 20-tile target. They never have any reason to look any further than the narrow corridor between S and D, which means this is an extremely efficient path to compute.
Experiment 3: 0-cost paths aren't followed if they take you backwards.
The setup:
...........................
...S===================D...
..H.....................H..
.H.......................H.
H.........................H
.HHHHHHHHHHHHHHHHHHHHHHHHH.
Here, we have a 0-cost path that's immediately visible from the start tile, but it doesn't get followed--the dwarves follow a straight-line instead. This is because the 0-cost path isn't heading in the right direction. The 0-cost tile is 22 tiles away from the destination, and costs 0 steps to reach--for a total score of 22. The first step in the straight-line path is 19 steps away from the destination, and takes 1 step to reach--a score of 20. A* prioritizes searching on the tile with score 20, and finds the destination quickly.
Experiment 4: 0-cost paths are abandoned when they stop heading in the right direction.
.......................
.S...................D.
..H.................H..
...H...............H...
....H.............H....
.....H.=========.H.....
......H.........H......
......H.........H......
......H.........H......
......H.........H......
......HHHHHHHHHHH......
In this one, we have a 0-cost path that's heading in roughly the right direction. This is enough that the dwarves follow it--at first. Once the path starts getting them further from their goal, they instead take a straight-line path across the 'gap' to the 0-cost path on the other side.
Together, I think these show that 0-cost paths could be incredibly useful in speeding up pathing. You might expect that dwarves would always use them, but that's not the case, because A* uses two numbers: the path cost, plus the distance to the destination. Even if you can follow the path for free, A* won't follow it if it takes you further from your goal. Dwarves don't follow these paths mindlessly if they're going in the wrong direction, which makes them pretty safe to use throughout the fort. It's a good way to make them prioritize a search along a certain path--to help them quickly find the hallway that exits your tree farm, for example.
Negative paths are a lot more interesting. I was worried that they might lead to a game crash--for example, if you make a loop of negative tiles, the dwarf might try to follow the loop in circles forever, to get an infinitely cheap path. This doesn't appear to be the case; it seems like the code never re-examines a tile when doing pathing, so you'll never make a complete loop. However, negative paths are so attractive that dwarves can be "pulled" to them from far away, and can follow them a lot further than might be advisable. Also, large blocks of negative tiles are a bad idea--I've found dwarves zig-zagging across the blocks to pick up bonus points. In short: use a little caution in playing with negative cost tiles.
Experiment 5: negative paths will be followed even if they lead away from the destination.
...........................
...S...................D...
..R.....................R..
.R.......................R.
R.........................R
.RRRRRRRRRRRRRRRRRRRRRRRRR.
This is the same setup as experiment #3, only this time, the dwarves actually follow the path. This one I actually have a little difficulty explaining. The first step on the negative path is 2 points further away by the manhattan metric, but costs -1 step to take--which should give total cost of 21 vs. a cost of 20 for the straight-line path. Nevertheless, the dwarves reliably choose the negative-cost path (sometimes in bizarre ways--I've observed them first walking across the room to the destination, then following the negative path back to the source before carrying the object to the destination).
Experiment 6: dwarves do not appear to maximize usage of negative paths.
.....R.R...................
....R...R..................
...S.....RRRRRRRRRRRRRRD...
....R...R..................
.....R.R...................
......R....................
Another interesting one, and difficult to explain. The path forks right before the destination (or source, I ran it both directions repeatedly). One of the forks is fully connected with negative tiles, one requires the dwarves to walk on a tile of cost 1. Surprisingly, I've observed the dwarves taking both paths. I have no idea why.
One theory I have is that the total cost of a path can never go negative. It seems that in some cases when the dwarves have to walk through normal tiles, they also walk through just enough negative tiles to "offset" the work they have already done.
Negative paths definitely need more research. I'd love to hear if anyone else is able to get them to do something interesting. Since they don't seem to follow the normal rules, it's not yet possible to just "do the math" on them to figure out what would happen in a given scenario--if we can figure out the rules, we'll be able to harness them.
To put everything together, how would you use this to do efficient, fort-wide pathing? I think you want several things. First, straight-line paths should be very fast. That's easy: just set normal traffic to size 1. That should make any straight-line (or mostly-straight-line) paths compute pretty quickly. Then, you just want to get your dwarves quickly to the point where they only have straight lines to compute. Imagine one of the worst cases for pathing today: a stone on a fully excavated level needs to be moved to a stockpile above it. The stockpile lies west of the stone (on a higher level), but the staircase is to the east. Current techniques will find their way quickly to the point directly beneath the stockpile, then will essentially start a "flood fill" looking for stairs. My hope is that you could insert a negative path through the excavated chamber that leads to the stairs. Dwarves will quickly catch the negative path, which they will follow with high priority towards the stairs. Once they hit the stairs, a straight-line search should get them fairly quickly to the stockpile. If this works, I'm imagining a network of negative paths designed to connect all the major chambers of your fort, with some "nets" in large chambers to grab dwarves who end up pathing through the large rooms on accident. This network is very tightly connected; any dwarf who touches a part of it in their path can effectively path very efficiently to any other piece of it. So you'd design the network so that it only halts in locations where you have nothing but a straight path left to your destination. Possibly you could tie it together with 0-cost paths as well, to help get around some tricky corners, or to reduce the size of this tight network.
I'm going to start a new embark today with these traffic costs set, and see what I can get to develop. I won't be able to say for sure what impact it has on FPS until I get big enough to see some lag, and then I can do some road painting and see what happens. If someone figures out how to get 0/negative traffic costs post-embark, it'd be a huge step forward.
Author
Topic: Advanced A* pathfinding/FPS !!SCIENCE!! (Read 7851 times)