I tried to come up with an example showing why things go horribly wrong for pathfinding performance depending on a number of factors. The JS app only handles pathfinding on a 2d plane, so I needed to make things a little bit more complicated inside the fort than most players would (hopefully!) do.
The maze-like shape for the inner fort is there to simulate some sub-optimal connectivity both between z-levels and across floors. Also note the length for the shortest path (~88 tiles) is still pretty tiny when compared to the average distance a dorf might have to walk to go from deep inside the fort to the outside world.
Urist McHauler is sleeping in his room (the complex of 1x3 rooms is the sleeping area) and he wakes up with a strong urge to go grab a pair of socks outside the fort. He needs to walk through the majestic dining hall (dots are supposedly other dwarves blocking his way), a first workshops area, a large stockpile, another workshops area and then the dodge-me corridor leading to the outside world. Imagine these sequence of areas is layed out on multiple z-levels rather than a 2d plane: dormitory under dining, and so on (as counter-intuitive and dumb as this might seem, the pathfinding process wouldn't differ that much from what you're looking here).
Once outside though, trees and a river still are opposing Urist's desire for more socks. Damn you nature!
(You can click on images for a larger view)
This shows why Weight = 1 is so hugly. With that low a cost for traversing tiles, the amount of potential paths going away from the target grows by a lot. While this is the intended A* behaviour, we want to favor paths generally going along the direction to the target rather than the ones leading away from it.
Quite obviously, since the pathfinder can't predict where bumps will occur along the way, it will also check for alternative routes every time an obstruction is met. We do want to minimize the negative effect of checking lots and lots of different alternatives every time an insurmountable obstacle is met, and the only way to do that (at least within basic A*) is by upping the weights.
The fact the whole inner fort is being checked while trying to path towards the target is because of two important aspects. First is bad connectivity in the fort itself, like the fact only a single exit leads to the outside area (this is very, very common in most DF forts). Secondly, as the pathfinder walks into a wall, it will check for all paths which might still potentially end up being one instance of a shorter paths (i.e. by checking all the paths for which the already walked distance + the estimated distance to the target is minimal). The effect of this is that the pathfinder will backtrack, so to speak, checking paths which were previously put aside, every time an obstacle which needs walking around it is met.
Now I need to make an important observation here: as mentioned earlier, Toady uses a slightly modified implementation of A* for better performance.
I don't know how things are being handled specifically, but Toady did mention "connected components" (which is a way to know which sets of tiles can access other sets of tiles). These techniques might be used (or not) to speed things up by a lot. But I don't know to what extent Toady implemented these kind of optimizations into his code (i.e. you could store which specific tiles on the frontier between contiguous components will be pathed through by only knowing which components contain the 'start' and 'goal' tiles). This might have a very important impact on how the pathfinding works but, since I don't know, I'll just assume the dumbest version of A* is being used instead.
Weight = 2. This is what DF uses for Normal traffic designations by default. You can immediately see how this, although not world-changing, is noticeably better than what you would get with a cost of 1 for every tile instead. Lowering the normal default cost, in fact, means 46 more operations (~7%) are needed to find the shortest path.
An higher cost helps with cutting down the number of checked tiles, although you obviously can't make up for the awful fort design by tweaking numbers alone.
Let's now suppose we up the cost for Normal trafic designations to 5. We lowered the number of operations being executed by a whooping ~13%. The algorithm is putting aside candidate paths more often, finding the shortest path earlier as a result.
Now, that's a nice performance improvement if you ask me!
As I've shown in the earlier examples, you simply can't turn weights arbitrarily higher hoping for a miracle to happen (otherwise programmer would just set weights to infinity and beyond!!!). In this example, doubling the weight from 5 to 10, only bears minimum gain. At some point, the topology within the instance of the problem at hand just poses an hard limit onto the performance gain you can get by upping weights alone (you it the theoretical minimal number of checks needed to find a shortest path).
To further show this, I'll set the weight to something unreasonably high (1K).
Even by using a several times larger weight, the algorithm can't find the path in under 511 operations (note: we could go down to 468 by using Euclidean as the Heuristic, but this is irrelevant) .
I mentioned the insurmountable wall the pathfinding algorithm has hit is the map's topology. Let me show what I mean: since, at each step, the pathfinder is preferably trying to go
towards the goal (as this would minimize the estimated distance), it is in a sense 'forced' to check lots of tiles leading nowhere on the right track. A human would never do such a thing (as our mind is so powerful we can very quickly discard useless paths on a whim by simply looking at the entire picture), but the computer can only pick a promising tile as its next step by comparing numbers.
The JS app does visually show how the number of checked tiles slowly as the pathfinder slowly finds its way out of the maze-like map and slowly finds the (shortest!) way towards the goal. I would edit the picture to show how how potential paths are being checked for as the search goes on, but it's been a number of hours since I started writing this, so you'll have to play with the linked JS app and see for yourself (pathfinding is fun! you won't regret it).
The yellow line (as you likely figured out by a long time now!) indicates the shortest path. The light green and cyan colored tiles are tiles which where checked during the search process.
To speed up the pathfinding work we would like the algorithm to skip as many of those tiles which are unlikely to fall on the shortest path, and this is why people will generally advice you set tiles in rooms and dead ends as Low Traffic, while main hallways and paths connecting areas between each other as High Traffic.
In this last picture, I highlighted tiles which could be set as Low Traffic in a red-ish color, and areas which could be highlighted as High Traffic in a blue-ish color. I say 'could' because you don't really want to designate all those tiles, as I doubt going for this extreme of a detail would bear that significant a results to justify all the tedious work involved.
Tips to speed up pathfinding (to an extent) This are really guidelines for optimizing fort-design which the community at large is fairly well aware of already I guess. Tht nice thing about optimizing your fort's design is that shorter walking distances and more efficient pathfinding have a positive impact on each other: you strike for one and you get the other as an added benefit.
- Design your fort to be compact.
- Favor connectedness both between Z-floors (having multiple shafts all around the fort rather than in a central area only) and across floors (cut down walls and u-bends to a minimum. Corners are fine unless you build mazelike structures. Given building a maze-like structure is not your objective to begin with
). - Generally speaking, favor designs which allow short walking distances between an area of the fort and the other in place of forcing your dwarves to take long detours.
- Designate dead-ends (including rooms with a single point of entry) as Low Traffic areas. Your dorfs will path there if they really need to regardless.
- Designate larger main hallways as High Traffic areas (this might cause slightly longer paths in some instances, but should allow for faster pathfinding)
- Use burrows to restrict specialized workers to their own working area. This is to avoid the majority of your fort's population wastes time (and CPU!) with hauling stuff from one and of the fort to the other.
- Ideally, don't make dwarves path to the surface (or caves) unless strictly required, as going outside the fort means way longer (and resource-heavy) paths need to be searched for.
Author
Topic: Advanced A* pathfinding/FPS !!SCIENCE!! (Read 7922 times)