Print

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

[Trollhammaren]

Sorry - accidentally posted this in the adv. mode forums first. Anyway, I heard DF uses A* pathfinding via an earlier thread.. I also understand pathfinding is one of the biggest causes of lag in .40 from recent threads, occasionally paralyzing fortresses completely. I don't understand the math, but apparently this is how A* works:



It tries to find the shortest route and then expands on it. Every possible node that branches from the direct path is stored in memory and gets a cost function. If the shortest route is not a working route then it starts evaluating those nodes in order. Is this correct?

I would like to ask smarter people how to design a fortress that's optimal for DF pathfinding, if this is how it works. Here's my guesses so far:

1. Corridors should be one tile wide only
2. Corridors should lead directly to the target with no angles or turns
3. Corridors should lead to one target only, to avoid congestion and ease design
4. There should be no alternative routes, including no dodge space in corridors, as those nodes in pathing all receive an utility function regardless of use
5. Intermediate stockpiles should be used at short intervals, to avoid long pathfinding calculations

is any of this correct? And furthermore would it cause huge issues with dwarves dodging one another?

[Mimodo]

I'm pretty clueless too, but I'd say that point 1 is incorrect. Dwarves seem to stop briefly when they bump into another dwarf without room to dodge around. Now multiply this by 50+ times in a main hallway where all your dwarves are going, and you may be slightly better off pathing wise, you lose a lot of valuable time, and maybe FPS cost too (not sure about that)

[smjjames]

One tile wide corridors work if there's only a few dwarves using it, however, once you get high traffic, you get a congested hallway with everybody climbing over each other and slowing each other down.

For high traffic or commonly used corridors, three tile wide or two tile wide is better.

[Slogo]

You can use traffic designations to possibly help the cost of some things like wide corridors, though the traffic designations may have a cost themselves so it's not entirely clear.

Either way the way A* works, in a general sense, is all of the unexpanded nodes (in this case the circles with no color) are ordered based on an estimated cost to reach the target.

That cost is made up of cost-to-reach-target + estimation-of-remaining-distance. The estimation here is setup to always be equal or lower than the actual remaining cost, otherwise the algorithm doesn't find the best path. Typically the estimation of remaining distance is simply the straight shot distance to the target. Some algorithms are more sophisticated and will break down areas and path find between those areas then do a finer grain breakdown of pathfinding the specific tiles in those rooms. I don't think DF uses this type of abstraction.


That said I believe...
Large open areas are problematic when the direct line to a target goes one way, but the actual path needs to go another.
Example:

Code: [Select]

#####
#.B.#######
#.........#
#...#####.#
#########.#
#......##.#
#......##.#
#..A...##.#
##.######.#
##........#
##########
Urist is going from A->B. # are walls . are floors.
Here the most likely thing that will happen is the algorithm will expand North first and expand out every floor in the large room hall. Each of those tiles will appear to be closer to the target than the hallway leading south. As a result a lot of path finding (well not a lot it's a small example) will take place as the dining room is explored before the target hallway is dug out.

My general rule of Pathfinding would be:

Large Rooms exist at the "ends" of the fortress (up, down, left, right, top, bottom) and your entrances/exits would count as large rooms.
Allow for mostly direct lines from point A->B. The more hallway curves a unit has to path through the more nodes will have to be expanded out.
Objects that are near in a straight line calculation should, as much as possible, also be near when considering the dwarves' path. Dwarves determine item target proximity based on straight lines, if the actual path to the closest item is all curvy and funky it means they'll expand more nodes.

The last thing would be play around with traffic designations, you can possibly Low/Restrict traffic for some dead-end areas so the dwarves are more likely to ignore those tiles when pathfinding.

[Trollhammaren]

I'm pretty clueless too, but I'd say that point 1 is incorrect. Dwarves seem to stop briefly when they bump into another dwarf without room to dodge around. Now multiply this by 50+ times in a main hallway where all your dwarves are going, and you may be slightly better off pathing wise, you lose a lot of valuable time, and maybe FPS cost too (not sure about that)

Yes, in principle. But... if you walk through a 1x3 corridor, you take 3 memory and perform 3 functions. If you walk through a 2x3 corridor, you take 6 memory and perform at least 19 functions (store every square, evaluate every square, path through 3 squares). If you walk through a 3x3 corridor you take from 19, walking on one edge, to 25 or more functions. If I understand this correctly. Meanwhile a dwarf kneeling and standing up is just 2. Of course you'd need to design your fortress specifically to avoid congestion... maybe? I've never had really tight main hallways so I don't know if dwarves pumping into each other really costs a lot of time.

[Trollhammaren]

The last thing would be play around with traffic designations, you can possibly Low/Restrict traffic for some dead-end areas so the dwarves are more likely to ignore those tiles when pathfinding.

However, doesn't the square still get evaluated even if it has low priority, since that's what's required to know it's low priority? Does the pathfinding floodfill next step start elsewhere if a square is low priority or how does this work?

[Trollhammaren]

Sorry for the triple post but one thought also comes to mind, do dwarves need to re-pathfind if they step off their path to avoid another dwarf, or calcualte pathfinding around the dwarf? Because then dwarves dodging each other instead of just crawling on top of each other might actually be slower.

[acetech09]

In terms of reducing pathfinding costs, I wrote a thing a while ago. I believe it's still accurate.

In terms of designing your fort to be A* efficient, straight shots everywhere. Little to no walls.

In terms of item handling: Be efficient with what you kill or produce. Atom-smash (does that still work?) refuse instead of just dumping it.

In terms of reducing the calculations DF makes: You can turn of weather, temperature, and similar processes in the init. That definitely speeds things up.

There are also some optimization mods out there.

[Slogo]

The last thing would be play around with traffic designations, you can possibly Low/Restrict traffic for some dead-end areas so the dwarves are more likely to ignore those tiles when pathfinding.

However, doesn't the square still get evaluated even if it has low priority, since that's what's required to know it's low priority? Does the pathfinding floodfill next step start elsewhere if a square is low priority or how does this work?

Every neighboring tile gets evaluated to some extent anyways, even walls. The difference between walls and say a restricted floor tile is the latter will end up in the queue of tiles to expand later. Adding tiles to the queue takes some processor time as they need to be placed in the proper order, but if those tiles aren't expanded it's a much lower cost.

What traffic designations does, most likely, is modify the estimated distance to target by the traffic amount. So by default 1 for High Traffic, 2 for Normal and so on. The algorithm always expands the lowest cost nodes first (cost being estimated distance + real distance to reach that node).

Take my previous example. If you put a 90 cost restricted traffic designation across the entire large room that would mean to expand one of those nodes before the hallway node to the south the algorithm would have to believe that the pathfinding cost to get from that hallway tile to the workshop is over the cost to get to that tile + distance in a straight line + 90.

So in this case it would explore out that hallway up to 75-80ish times before it considers looking even a single tile into the dining room. Of course note if you're looking for something in the dining room suddenly the pathfinding is going to be extremely inefficient.

----
Chances are when dwarves dodge they simply just recalculate their next node/target only and not the entire path.

@acetech one thing about that article, you say walling and flooding with restricted is the same, but I think walling is more efficient in the case where a dwarf may be looking for something in that area. By just walling with restricted traffic, once the algorithm decides it has to expand through the wall it will be free to efficiently path through it rather than keep hitting 100-cost nodes that may cause it to keep looking for alternate routes.

[Button]

An idea I had in a previous thread is to remember that dwarves are not humans. They have no aversion to climbing or descending staircases. Scattered stairwells are heaven for your fps, and the human-intuitive "central staircase" design can be a major bottleneck.

The ideal fortress setup for fps is a giant cube of up/down staircases.

[Trollhammaren]

Hm. Is it known how dwarves evaluate staircases on the path? Do they estimate the shortest path in full 3d, or xy and z separately? Because I could see DF thinking either is reasonable.

Also wrt stockpiles, is there a benefit to intermediate feeding stockpiles for shorter paths, or do those do more harm with dwarves looking for items in more places?

----

Edit: A concrete example. Let's say dwarf U starts in the meeting hall on the bottom floor. He wants to pick up a block and construct a wall at z+3, x+15, y+15. Z+0, z+1, z+2 and z+3 are levels without any walls. There are blocks in stockpiles at z+1, x-8, y-8 and at z+2, x+8, y+8. There are two usable up stairs, one at x-5 and one at x-5, y-5. At z+1 there is only one upward stairway, at z+1, x-5, y-5. At z+2 there is only one upward stairway, at z+2, x+10, y+10.

The stairways that are nearer to the dwarf lead to a shorter path to a stairway in two dimensions, but to a longer path to the pile of bricks in three dimensions. The nearest stockpile is the one that is further away from the construction target. The path to the stockpile is minimized by picking the nearer stockpile and the further stairway. The entire path is maximized by picking the nearest stairway and the nearest stockpile and minimized by picking the further stairway and the further stockpile. What will U do?

[grody311]

I eschew large stockpiles in favor of small stockpiles surrounding my workshops, with the workshops set to 'take' from the stockpiles.  This eliminates the amount of pathing for materials greatly.  (Not every shop uses inputs that can be manipulated in this way, but enough do.)

However, no matter how many tricks you use, a 2+ year old fort in 40.xx will always slow to a crawl.  I don't believe that pathfinding is the real culprit here, as pathfinding is largely the same as it was 34.xx, and fps is vastly better in the old version.

[rhoxa]

However, no matter how many tricks you use, a 2+ year old fort in 40.xx will always slow to a crawl.

Sadly, this has been my experience as well. 

[shlorf]

I managed to get some 20 year long forts going in 40.13 actually.
I had to take some drastic measures and only got 50-70ish fps, however.
Off the top of my head:
-generate a thinner world or a world with thin embarks at least; my embark has like 30 levels soil/stone from ground to magmasea
-generate that world with only 1 cavern layer, and size that down, too, so i have a few levels to build
-make the world small pocket is best smaller and small region seem to be ok
-make the embark small (2x2 and 3x3 work for me)
-keep typical pathways simple (basically a vertical layout, i'm not so great at that, tho)
-no more than 120 dwarfs
-all the usual stuff (atomsmash or trade away clutter items, dfhack's cleanowned to help keep itemcount down, don't strip mine or at least wall it off, etc.)

i can upload a save if anyone wants to check it out

[rhoxa]

I managed to get some 20 year long forts going in 40.13 actually.
I had to take some drastic measures and only got 50-70ish fps, however.
Off the top of my head:
-generate a thinner world or a world with thin embarks at least; my embark has like 30 levels soil/stone from ground to magmasea
-generate that world with only 1 cavern layer, and size that down, too, so i have a few levels to build
-make the world small pocket is best smaller and small region seem to be ok
-make the embark small (2x2 and 3x3 work for me)
-keep typical pathways simple (basically a vertical layout, i'm not so great at that, tho)
-no more than 120 dwarfs
-all the usual stuff (atomsmash or trade away clutter items, dfhack's cleanowned to help keep itemcount down, don't strip mine or at least wall it off, etc.)

i can upload a save if anyone wants to check it out

Thanks for this info.  I'm going to use these parameters and see what happens.  If I hit lag at the usual time then I'll compare to your save.  I've never done such a small world so it will be new for me.