Print

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

[pokute]

Does vertical pathfinding cause more lag than horizontal pathfinding?

For example, when I dump all the stones on a newly dug out floor 10 z-levels down from the garbage zone, my fps drops to about 70 (in small fort with 30 dwarfs).

But when I dump all the stones in a newly dug out area 20 tiles away from the garbage zone, my fps still shoots by at around 200 (in the same small fort with 30 dwarfs).

Does anyone have similar experiences?  Are the number of z-levels your dwarfs have to regularly travel an FPS killer?

[Duke 2.0]

 Mind you that generally, thing that allow pathfinding horizontally(Floors) don't allow pathfinding vertically, whereas pathfinding vertically(Staircase) allows for horizontal pathfinding(Every level the staircase leads to).

 Thus horizontal pathfinding stays horizontal most of the time. Vertical pathfinding spills out horizontally on multiple levels.

[pokute]

I guess then I really need to design a fortress layout to minimize pathfinding bloom.

Also, does this mean that hermit designs might be the most efficient for pathfinding?

[LegacyCWAL]

Also, don't forget that virtually by definition, stairways will be smaller in terms of floor space than the hallways connecting them.  And a smaller area to pathfind through means more lag.

[Hydra]

Also, don't forget that virtually by definition, stairways will be smaller in terms of floor space than the hallways connecting them.  And a smaller area to pathfind through means more lag.

No. The more spaces a pathfinding can go into, and thus HAS to go into, the more time it takes to calculate. Basic example; to find a path through a 2 tile wide hallway is more work than finding a path through a 1 tile wide hallway. Ofcourse there are optimizations, but it's never so that giving the algorithm less options makes it slower.

[Neruz]

But wouldn't it be faster to pathfind through 6 squares that each have 3 options than 20 squares that each have 2 options?

[Hydra]

But wouldn't it be faster to pathfind through 6 squares that each have 3 options than 20 squares that each have 2 options?

6x3=18, 20x2 = 40. So definately

I don't know how the pathfinding is implemented exactly though. I assume it's some form of A* (because it tends to perform very well in both speed and quality), but how well A* performs (both in speed and how good the paths are) depends a lot on the heuristic used (A* is basicallt a "flood" algorithm that uses a quick precalc).

[Jurph]

I was experimenting with pathfinding optimization recently and discovered that I could get a nice speed boost by marking large dead-end rooms (e.g. stockpiles) as "restricted".  Take this one step further: if you have a floor of your fortress that is only used for large stockpiles, mark them restricted and mark the stairs as "high traffic".  Then draw a two- or three-tile wide high-traffic path to the center of the stockpile, so a Dorf trying to path to that stockpile won't try to find a Northwest Passage.

You might even put high-traffic "drop off" stockpiles right next to the stairway, with larger restricted stockpiles on the same floor linked by a two-to-three-tile wide normal traffic area.  The dwarf doing the pathfinding takes the item to the stockpile and finds it quickly; the haulers who move stuff from the staging area to the long-term storage should path between the two quickly because it's only a few tiles difference anyway.

This means most foot traffic won't bloom very far onto the storage floor, but storage tasks will find what they need to in short order.

[pushy]

Also, don't forget that virtually by definition, stairways will be smaller in terms of floor space than the hallways connecting them.  And a smaller area to pathfind through means more lag.

No. The more spaces a pathfinding can go into, and thus HAS to go into, the more time it takes to calculate. Basic example; to find a path through a 2 tile wide hallway is more work than finding a path through a 1 tile wide hallway. Ofcourse there are optimizations, but it's never so that giving the algorithm less options makes it slower.

Logically I'd agree with you...but for some reason in practice in DF it isn't the case - I've got a fort where there are two ways into the main area of the fort: Through a 1-tile-wide trap corridor, or through a 5-tile-wide corridor which is usually blocked by a bridge, and with 100+ dwarves I am now at a point where I instantly know when an ambush party is on the map because the game suffers ridiculous lag as the goblins try to path through the trap corridor. If I lower the bridge that blocks the 5-tile-wide corridor to my fort (which is only lowered for getting goods to/from the trade depot) I don't have this lag issue at all.

[LegacyCWAL]

Also, don't forget that virtually by definition, stairways will be smaller in terms of floor space than the hallways connecting them.  And a smaller area to pathfind through means more lag.

No. The more spaces a pathfinding can go into, and thus HAS to go into, the more time it takes to calculate. Basic example; to find a path through a 2 tile wide hallway is more work than finding a path through a 1 tile wide hallway. Ofcourse there are optimizations, but it's never so that giving the algorithm less options makes it slower.

My reasoning is this:

People say that you can reduce lag by making halls wider.
Stairways are not going to be as wide as halls.
Thus stairways would cause more pathfinding lag than halls.

[Hydra]

Logically I'd agree with you...but for some reason in practice in DF it isn't the case - I've got a fort where there are two ways into the main area of the fort: Through a 1-tile-wide trap corridor, or through a 5-tile-wide corridor which is usually blocked by a bridge, and with 100+ dwarves I am now at a point where I instantly know when an ambush party is on the map because the game suffers ridiculous lag as the goblins try to path through the trap corridor. If I lower the bridge that blocks the 5-tile-wide corridor to my fort (which is only lowered for getting goods to/from the trade depot) I don't have this lag issue at all.

Is that 1-tile wide trap corridor a winding path instead of a straight one by any chance?

Again, I don't know exactly how the pathfinding works in DF, but I do know that in typical applications it depends on how many spots it has to visit.

[pushy]

Is that 1-tile wide trap corridor a winding path instead of a straight one by any chance?

In that particular case, yes. In other examples I've experienced (there's usually somewhere at the entrance of my fort that is one tile wide for protection from kobolds) it may be about four tiles across. I can think of one example from an old fort, so I'll draw it up for you...

WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W..............W...W.......W
W..............W.W.W.......W
W...............SW.........W
W..............W.W.W.......W
W..............W...W.......W
W.....WWWWWWWWWWWWWWWW.....W
W.....W..............W.....W
W.....W..............W.....W
W..............WWWWWWW.....W
W..............WDDDDDW.....W
W.....W........WDDDDD......W
W.....W........WDDDDD......W
W.....W........WDDDDD......W
W.....W........WDDDDDW.....W
W.....WWWWWWWWWWWWWWWW.....W


I've colour-coded this just to help me explain things. The main fort is down the left-hand side, the fort entrance is down the right-hand side. Up top you can see a green S and a few red dots - the green S represents my kobold detection method - a restraint with a mule or other pointless animal chained to it, and the only way into my fort was through that, with the red dots indicating possible squares where kobolds could be detected by that restrained animal. If I had lots of goods that needed to be taken from the trade depot (highlighted in yellow), the dwarves went right around, including having to go through the little kobold trap, and when I had quite a few dwarves, I experienced a lot of lag.
However, if I were to remove the pink walls of my kobold trap, or the orange walls beside my trade depot, THEN get my dwarves to gather lots of goods from the depot or from outside, no lag is experienced.

Like I said, logically what you said makes sense and as a budding programmer myself I whole-heartedly acknowledge that, but for some reason logic is tossed out the window here

[Jurph]

If you added pathing constraints to this layout (I've substituted "h" for high-traffic, "r" for restricted traffic in your example) I think you'd significantly speed up the pathfinding through this bottleneck.  I'm not 100% sure, though, because I'm used to using path constraints for much wider halls.

WWWWWWWWWWWWWWWWWWWWWWWWWWWW
W.............rWhhhWr......W
W.............rWhWhWr......W
W...........hhhhSWhhh......W
W.............rWhWhWr......W
W.............rWhhhWr......W
W.....WWWWWWWWWWWWWWWW.....W
W.....W..............W.....W
W.....W..............W.....W
W..............WWWWWWW.....W
W..............WDDDDDW.....W
W.....W........WDDDDD......W
W.....W........WDDDDD......W
W.....W........WDDDDD......W
W.....W........WDDDDDW.....W
W.....WWWWWWWWWWWWWWWW.....W