Print

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

[Jurph]

I'm hoping the A* pathfinding efficiency nerds will be out in full force -- and I love you guys! -- so I'll make this question pretty direct:  Do any of you zealously place traffic zones for your dorfs to follow?  Do you see any framerate improvement from it?  I have a pretty awesome fortress that just cracked 100 population and is chugging along at about 30FPS.  I'm keeping all of my animals caged but the framerate (esp. with goblins or elves attacking) is still sluggish.  Can you share your best traffic zone strategies with me?

For what it's worth, the fort I'm trying to fix is comprised of many medium and large circular chambers linked with typically single-wide doorways that blossom onto 5-wide hallways.  Should I be designating the left and right edges of each hallway?  A stripe down the middle?  Should I make the effort to paint each doorway as high-traffic so they'll treat it as a local goal (and therefore use fewer Dijkstra loops searching cavernous rooms)?

[Puck]

single-wide doorways that blossom onto 5-wide hallways. 

I didnt understand half the stuff you asked, but this one caught my attention... I assume it looks like this

Code: [Select]

W=wall F=floor D=door

WFFFFFW
WWWDWWW
While I think it's probably better to do it like this

Code: [Select]

WFFFFFW
WDWDWDW
I think when two dwarves try to path through the same tile, they look for another path, and only if they dont find one they use the same tile. And this can be a cause for slowdown. Even if the gain is small, the effort is minimal, so it doesnt hurt to try, now, does it?

maybe let the circular rooms be connected to the hallways without any walls/doors in between, if possible.

[Sowelu]

You might not get as much performance boost as you think for this reason:  Each time you keep ten dwarves from searching a bedroom, you might make one dwarf take ten times as long.  Make sure it's worth it.

Remember that in A*/Dijkstra, if you designate the middle of a hallway as low-cost (high traffic), and the edges as high-cost, it won't change much in a long distance search because each tile adds its cost instead of multiplying the total cost.  It'll still search out most of the local stuff before it goes very far.  Also, worst-case is that dwarves prefer crawling past someone instead of going around and that's bad.  So designate hallways the same all the way across IMO.

Restricted is almost always a bad idea...except that I sometimes like tagging my front doorway with some restricted tiles, to keep pathing inside the fort where it belongs most of the time.

The most important paths are to the food stockpile, drink stockpile, and dining rooms.  Aside from that, make sure you're not screwing over craftsdwarves that need lots of stones, and remember that the path cost only says "how do I get the stone", not "which stone do I get".

If you REALLY, REALLY have nothing but interconnecting big rooms...not branches off of corridors...then I could see "restrict the doorways" as actually working, as long as you make it deep enough to matter.  Let me know how it works out, I'm curious.

[Jurph]

I was actually looking at tagging the doors with high traffic, not restricted, but the explanation about local search being additive makes sense and seems to argue against any single-tile designations as largely ineffective.  Seems like I should be drawing efficient highways through each room, so that a dwarf passing into a large circular chamber will find the exits before searching the entire room's volume.

[Tcei]

I've been experimenting with traffic designations lately, I've found that what seems most efficient seems to be something like this

Code: [Select]

HLHL
LHLH
HLHLH=High traffic and L is Low traffic. This causes less dwarves laying down so others can get over them. Than placing along the edges of a hallway.  Intersections and places in front of important stockpiles (I.E. food) will get all High traffic.  I've also witnessed Champions nad Legendaries occasionally zooming by thru the Low areas if you set them to normal, while the rest of the populace uses the high.

[Jurph]

So I laid in high-traffic pathways in my main three floors (along with low-traffic edges to discourage Dijkstra searching into large cavernous spaces) and then the caravan left... so the framerate jumped to 45, but I don't really have a good feel for how much of that to credit to my traffic zoning.

[NeedsDF2GetThruWorkingDay]

So I laid in high-traffic pathways in my main three floors (along with low-traffic edges to discourage Dijkstra searching into large cavernous spaces) and then the caravan left... so the framerate jumped to 45, but I don't really have a good feel for how much of that to credit to my traffic zoning.

Another caravan will show up soon enough, giving you a slightly better idea. Please let us know how it goes.

[Jurph]

Will do.  Unfortunately, I'm on a Tuesday/Friday/Sunday DF regimen, with the remaining four days & nights reserved for work on my Masters' thesis and my (increasingly tiny) social life.  I should be able to resurrect this thread with better data sometime on Friday. 

NeedsDF, love the nick.

[NeedsDF2GetThruWorkingDay]

Thanks. When the name occurred to me, I found it both hilarious, and entirely too accurate, but I digress...

I am hoping, for the sake of having only one variable in your experiment, that neither the most recent caravan NOR the upcoming one is an elven caravan? They have a much easier time pathing, and also seem to have fewer total traders and pack animals.

[Jurph]

Heh... no.  In this particular world my civilization started out At War with the elves.  Last caravan was Dwarven (fall), and the next one should be human (summer).  The only danger is that my population will grow in the interim, but I think I'm near the pop cap.  I've been thinking over the problem during my commute, and I'm pretty sure that traffic zones will provide the greatest advantage when

1) They help the algorithm rule out large searchable spaces (so that you save large numbers of clock-cycles for each pathfinding creature)
2) They are used to connect two frequently-traveled points (so the most dwarves will benefit)
3) They are drawn along the best route between those points (so the algorithm won't fight you)
4) Placing a high-traffic "valley" in between a pair of low-traffic "walls" (so that the algorithm will quickly realize the high cost of routes that go off the path)

That's the method I'm going to use, and I think it's a winner.  I'm open to additional suggestions though.

[Randominality]

I cant remember where I saw it, but someone managed to make 2 one way lanes in his corridors so dwarves going one way would go on one and dwarves going the other way would go down the other side. Not sure if it helped framerate but I'd assume it would.

[Duke 2.0]

 Lock down the mines with door, lock the tombs with locked doors and set the main entrance to restricted traffic.

 That should restrict pathfinding to only the parts of your fortress that are used often.
 Taaadaaaaaaa!

[Jurph]

I cant remember where I saw it, but someone managed to make 2 one way lanes in his corridors so dwarves going one way would go on one and dwarves going the other way would go down the other side. Not sure if it helped framerate but I'd assume it would.

I'm certainly not the first to try it, but at Whiteoak -- the same fort I'm doing these traffic zoning experiments! -- I have placed a few diagonal traffic control devices in the hilt of the Sword Hall, where I expect lots of traffic.  I'm torn on whether it will work, though.  On the one hand, there doesn't seem to be any reason for a dwarf to choose a different route from A to B than from B to A.  On the other hand, when dwarves cross large open spaces to get to a water zone, I routinely see them taking two distinct paths to and from the water source, so something must be causing that behavior.

[TettyNullus]

I cant remember where I saw it, but someone managed to make 2 one way lanes in his corridors so dwarves going one way would go on one and dwarves going the other way would go down the other side. Not sure if it helped framerate but I'd assume it would.

I'm certainly not the first to try it, but at Whiteoak -- the same fort I'm doing these traffic zoning experiments! -- I have placed a few diagonal traffic control devices in the hilt of the Sword Hall, where I expect lots of traffic.  I'm torn on whether it will work, though.  On the one hand, there doesn't seem to be any reason for a dwarf to choose a different route from A to B than from B to A.  On the other hand, when dwarves cross large open spaces to get to a water zone, I routinely see them taking two distinct paths to and from the water source, so something must be causing that behavior.

I see the two path thing pretty often when building and working outside, or even in large, empty space inside. I think it's just the pathfinding working one way, then forgetting the original path and working it's way the other way, and seemingly taking different paths to same entry/exit points (which in my case is often a single staircase)

[Sowelu]

If your destination is, say...south-southeast from you, you have a question of "Do I search southeast, or straigh east, first?".  In a wide open area, going SE then E will have the same cost as E then SE.  So in a simple A* implementation, whichever you search first will be the way you go first.

In this case, if E is searched before SE, and W is searched before NW, your dwarves will leave their watering hole going east, then go southeast to make their way to your fortress entrance.  On the way back out to it though, they'll start going west, and then go northwest to finish it.  So you end up with two paths.

I think the normal way to prevent this happening is to make NSEW all be searched first before NE SE SW NW.  You don't change the cost, just the search-order tiebreaker.  Whether this is desirable at all is questionable.