Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Earthquake Damage]

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 not be checked). What other changes he might have made and which data structures he uses (which seriously impact the speed of calculations) is hard to say.

Actually, restricted zones are checked.  They just have a very high path cost.  The low/normal/high/restricted path costs default to 1/2/5/25.  It's explained in data\init\init.txt.

[hermano]

Edit:
According to Rafal99s post later in this thread (http://www.bay12forums.com/smf/index.php?topic=56041.msg1224791#msg1224791) an improved A* ist used, so the following examples are not important for fortress planning.

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.

Do you maybe mean best first? That is a pretty old method from the late seventies. A* is a mixture of Dijsktra and best first (which is also called B*).
I dismissed the thought that he might be using such an inefficient method, assuming that he wrote the pathfinding some time in the last decade. But on the other hand it might not be that improbable, maybe he uses the pathfinding code from an older game and never had another look at it. It is of course more fun enabling more content, like 1000 year old puke monsters from the depths, than working on pathfinding...

So, lets have a look at B* (even if your post was not about it and I got that wrong) and what this would mean for fortress layout then:
I currently don't have the time to read up on the details of the algorithm, it's hard to find something on the net and visiting the library might be the better approach. But lets have a look at some examples, as the website linked in the op has that implemented, too.

Finding the path to a target in open space:

This is worse than Dijsktra, and much worse than A*. All surrounding tiles are checked iteratively until the target is found. So obviously open spaces are definitely not our friend then. High pathing costs would not stop the method from checking all those tiles, they would just influence which path is chosen afterwards, afaik. So setting traffic zones would probably not improve pathfinding speed.

Finding a path inside:

Much better, as there are less tiles that have to be checked...

And some obstacles:

Even better, as we have more walls there are even less tiles that have to be checked.

With unreachable items the situation doesn't change, it's just as bad:


So if this method is used I think your best fortress design would be quite different:
- Mine as little space as possible.
- Build as many walls and other obstacles as possible.
- Keep all ways short.
- Don't spend too much time on setting traffic zones.

If toady is using this method there are good news: Changing the algorithm should not take him too much time, a few hours in the best case or probably a few days in the worst. The speed improvements would be immense. Of course he has a lot on his hands for now, but if the method is this outdated he might have a look at it much sooner.

Actually, restricted zones are checked.  They just have a very high path cost.  The low/normal/high/restricted path costs default to 1/2/5/25.  It's explained in data\init\init.txt.

Yes, you are right, what I wrote is misleading (so let me change that). What I meant with that was that the high pathing costs of restricted tiles should result in many other tiles being checked first. So if there is another way (thats not too long) it will probably be found before a row of resticted tiles has even been looked at.

Edit:
I had a short look at the kobold quest source code, and to my understanding he is using a variant of B* there. But the existence of traffic zones in df shows that he did change his method and having different pathing costs would point towards A* (ruling out Dijkstra due to target selection). So the examples and conclusions in this post should be of little importance.

[se5a]

Traffic zones don't affect which stone he goes for though right? only how get gets to that particular stone.
Have I understood this correctly?

[hermano]

Traffic zones don't affect which stone he goes for though right? only how get gets to that particular stone.
Have I understood this correctly?

Right. Burrows will probably help when its about which stone will be selected.

[illarion]

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.

Very interesting paper, thanks for that!  It does seem like this method could potentially really help DF, should Toady get a chance to work on the pathfinding.

[Rafal99]

Toady has said some time ago that he uses a modified A*. The modification is that he divides a map into accesible areas, so if point A is in another area than point B, it means that there is no access from A to B, and no path in actually calculated. It saves a lot of performance in such situations, because otherwise the pathfinding will have to fill the whole area before deciding that there is no path.


As for my advice about fortress design:
-try to have as much straight paths as possible
-mark hallways which are frequently the best path as High Traffic
-mark dead-ends and areas your dwarves do not need to visit as Low Traffic

[hermano]

Toady has said some time ago that he uses a modified A*. The modification is that he divides a map into accesible areas, so if point A is in another area than point B, it means that there is no access from A to B, and no path in actually calculated. It saves a lot of performance in such situations, because otherwise the pathfinding will have to fill the whole area before deciding that there is no path.


As for my advice about fortress design:
-try to have as much straight paths as possible
-mark hallways which are frequently the best path as High Traffic
-mark dead-ends and areas your dwarves do not need to visit as Low Traffic

Thanks, thats great to know.
Further improving the method will probably be much harder for him then.

[Werdna]

I always see a lot of discussion about workshop streamlining, but to me that's just a small aspect of the life of a dwarf.  Its just the most visible to us, so we tend to place undue importance on it.  For FPS purposes, we ought to also streamline what they do when they're not working - eating, drinking, sleeping, socializing. 

Meeting areas to me are a way of setting a rough "starting spot" for your dwarves.  Think about it, out of a 100 idle dwarves, the vast majority will be at the meeting hall when you issue that mass-smoothing/mining/goblin-looting/whatever order, so if you've spent time optimizing the paths around that hall, all those sudden pathfinding jobs are much simpler.  That's similarly true every time a dwarf needs to sleep, eat, drink, or wander off for a break - you rarely pay attention to these 'jobs', but they're happening much more frequently than your work orders.  So I tend to place meeting areas in extremely central fort locations, usually a dining room to make eating occur at the same spot, and with booze and food (prepared, to avoid refuse pathing) stored a z-level up or down, and plenty of stairwells from it. 

To me the meeting area (the legendary dining hall) is the central core that a fort is built around.  As an aside, its also the place to throw all your masterwork stuff to maximize happy thought generation.  Happy dwarves can even help decrease pathfinding - in a FPS pinch, they'll easily get over your pet-killing measures!   

In the reverse, once dwarves are tasked with a job they can spend lengthy time at it, and will proceed to menial tasks from their work spot.  So that's the other node I optimize from - in a workshop zone I'll take an area that might normally contain a shop and instead place booze/food/beds/chair+table for fast access by the workers.  Ditto near farming fields, etc.

[Bronzebeard]

Unabashedly, most of this escapes my meager understanding, but I have to say I'm utterly blown away: all I've done is designated my central hallways as high-traffic areas and the increase in framerate was phenomenal! Suddenly, 200 dwarves felt like 50 again! I've done a little experimenting with low-traffic areas in some of the dead-end rooms with questionable result but, again, laying down high-traffic regions alone helped my framerate immensely; everyone should become more cognizant of traffic areas.

[Silverite]

What I found that appeared to be bogging down my framerate the most in my current fortress, with respect to pathing, was having too many alternate paths to everywhere - every large room had four or five exits per wall.

Designating high/low traffic zones didn't appear to change the framerate much, but walling/dooring off a bunch of paths, so that there were only a few exits from any given room, moved the framerate from low 30s to mid-high 40s. Making it all walls so that the pet population stop trying to path through the doors might improve it yet further?

I was working on the assumption that "many ways to get anywhere=less steps for any given job", but I think I'd prefer a better framerate. I suppose I could get both if I designed the fortress well, but just having come back to DF after having merely dabbled in the past I'm still climbing the learning cliff.

[Bronzebeard]

I think what has to happen is for creature pathing to be more intelligent. It finds a path, it saves and remembers it and it uses it instead of calculating a new one each and every time. That's arbitrarily accomplished when you lay down traffic zones since you make one given set of tiles more desirable to travel across than others. If dwarves could figure this out without your intervention, however...

[mnjiman]

I think what has to happen is for creature pathing to be more intelligent. It finds a path, it saves and remembers it and it uses it instead of calculating a new one each and every time. That's arbitrarily accomplished when you lay down traffic zones since you make one given set of tiles more desirable to travel across than others. If dwarves could figure this out without your intervention, however...

Dwarf learning new paths and saving those paths depending on locations of objects and tasks. That is ingenious.

For objects or dwarfs they are moving out of the way for: then a path finder is used for the area around the dwarf.

[moki]

Only one problem... when should the paths be calculated?
Just imagine you have one very long U-shaped path and dwarves have to get from one end to the other. Now you dig a shorter way (directly between both "ends" of the "U") - your dwarves would still take the much longer way, because that's the one they know.
Ok, so the game should calculate a new, shorter path at this time, but how does it know, if something relevant changed? There's no way to know, if there's a more effective path, unless new paths are calculated all the time (or at least everytime something is dug out or build) - it would bring a minor speed gain in forts, where you don't build anything anymore, but how often does that happen? I say, that system wouldn't help at all unless there'd be a very complex method of determining, what is relevant for the current paths and what isn't.
Also, dwarves don't use the same path several times... one of the most common would be the path from the boozepile/dining room to a specific workshop and there are still hundreds of paths for every tile of the starting room. You'd start saving paths from every tile to every other tile. More than 5 Million paths for 48x48 tiles and one z-level, more than a few trillion for a reasonably sized map. I don't want my computer to save a few gigabytes of paths and search through all of them for the right one everytime someone needs to path somewhere.

Always remember, what looks so easy for the human brain like "just go from this room to that room and remember it for the next time" can be hard for a computer. Computers are very, very dumb, if you don't tell them exactly what to do and how to do it.

The only practical possibility, I can think of, is only saving major traffic routes that are frequently used. The dwarves would still need to use regular pathing from their current location to the beginning of the main route (that goes wherever they need to go) and once they'd reach that route, they would just follow the predefined path until the end point from where the regular pathing would kick in again. It's still not easy to let them know, which main route is the best for their current purpose, but maybe it's a tiny bit more practical than saving everything.

Please correct me, if there's something fundamentally wrong with my negative thinking.

[Bronzebeard]

Only one problem... when should the paths be calculated?
Just imagine you have one very long U-shaped path and dwarves have to get from one end to the other. Now you dig a shorter way (directly between both "ends" of the "U") - your dwarves would still take the much longer way, because that's the one they know.
Ok, so the game should calculate a new, shorter path at this time, but how does it know, if something relevant changed? There's no way to know, if there's a more effective path, unless new paths are calculated all the time (or at least everytime something is dug out or build) - it would bring a minor speed gain in forts, where you don't build anything anymore, but how often does that happen? I say, that system wouldn't help at all unless there'd be a very complex method of determining, what is relevant for the current paths and what isn't.
Also, dwarves don't use the same path several times... one of the most common would be the path from the boozepile/dining room to a specific workshop and there are still hundreds of paths for every tile of the starting room. You'd start saving paths from every tile to every other tile. More than 5 Million paths for 48x48 tiles and one z-level, more than a few trillion for a reasonably sized map. I don't want my computer to save a few gigabytes of paths and search through all of them for the right one everytime someone needs to path somewhere.

Always remember, what looks so easy for the human brain like "just go from this room to that room and remember it for the next time" can be hard for a computer. Computers are very, very dumb, if you don't tell them exactly what to do and how to do it.

The only practical possibility, I can think of, is only saving major traffic routes that are frequently used. The dwarves would still need to use regular pathing from their current location to the beginning of the main route (that goes wherever they need to go) and once they'd reach that route, they would just follow the predefined path until the end point from where the regular pathing would kick in again. It's still not easy to let them know, which main route is the best for their current purpose, but maybe it's a tiny bit more practical than saving everything.

Please correct me, if there's something fundamentally wrong with my negative thinking.

Aye, I gathered that would be a problem. I'm just throwing things out. How about a mix of the two? The dwarves stick to a learned path wherever they need to be but once every so often they calculate the surroundings to refresh and re-optimize their pathing (as opposed to doing that every single time, hundreds of dwarves doing it every single second). Again, this would be a problem in that routes have to be saved and that they -- according to you -- take up so much memory. I can't muse about any remedy to that since I'm both oblivious to how the game encodes/would save pathing and a drooling ogre when it comes to math. :3

[UnLimiTeD]

I think to improve "Dwarf intelligence", it would be useful to have some pathfinding numbers in the ini, like whether a Z-level is worth more.
Recalculating ideal paths between "accessibility areas" every season change would probably not take up much.
But wouldn't the best speed improvement be good multi-core support?^^
I think having pathfinding as a separate thread would speed stuff up.