Print

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

[Col_Jessep]

Welcome fellow Overseers!

Once again one of my forts fell to the worst nemesis known to overseerkind: FPS death. It was a 2x2 emark and died after only 6 years. I'm obviously doing something horribly wrong. Ask and the holy collection of slabs (DF Wiki) shall provide! Let's talk about pathfinding in DF, specifically A*.

I found DF after watching a Youtube LP from Leigh "Deman" Smith a while back and I analyzed his fort design with the nice pathfinding tool on github linked on the DF Wiki: http://qiao.github.io/PathFinding.js/visual/

As it turns out the algorithm really doesn't like his long hallways with large rooms on each side. (The more teal/green you see the longer it takes the algorithm to find a path, slowing down your game.) Imagine a dwarf is at the dark green point and he wants to haul a rock from the red spot:

<- clicky for full size

A* basically flood-fills all the rooms before it can find a path: It takes 16ms and 1089 calculations. Oh dear!


Now we are trying to improve the room layout a bit:



We are down to 9ms and 350 calculations. That's one hell of an improvement for punching a couple of additional holes into the walls!


Further improvement:



We are now at 4ms and 220 calculation. Oi, 4 times as fast and we are saving 10 tiles of hauling a heavy stone!


The "ideal" solution: Knock out all the walls:



4ms, 176 calculations. Our second best result is very close.


I think we don't even have to discuss how the A* path would look for a favorite of mine, the Nautikus Blossom from Quickfort:



Yup, you are paying a price for prettiness, although it is not quite as bad as I feared:

 


So, how would a more optimized design look like? Probably like this:





4 12x12 workshop areas around a central staircase, framed by bedrooms and offices for your dwarfs with additional staircases if necessary.

I have no idea how DF calculates a path to staircases and other z-levels. That's a bit of a blank spot and I hope you can shed some light on this. Is it better to move bedrooms to their own z-level? More staircases? Do you have a prettier design in mind? My design really could use  some help in the aesthetics department... 

[Wooster]

That's a nice tool.

Yes, knowing about multilevelling would be very useful. I tend to build room-layers, which contain single rooms or small complexes (like four rooms with an atrium), and sandwich them with with highly open-plan layers for stockpiles and staircases. My assumption is that this is fairly quick for calculation but I could be completely wrong!

[Larix]

I took a look and it seems that the tool cannot handle diagonal-only connections. I.e. a chamber like this:

Code: [Select]

..#####
###...###
#A.123.B#
###...###
..#####

finds no path if an obstacle is placed at 1 or 3. It will path correctly if an obstacle is at 2 only. A dwarf, on the other hand, will find a path in any of the given cases.

This unfortunately makes the tool useless for evaluating a great many possible DF designs.

BTW, further reading, almost entirely based on observed in-game behaviour: http://www.bay12forums.com/smf/index.php?topic=128855.0

Of particular interest might be the zero- and negative-cost designations that can be generated by editing the d_init file.

[taptap]

PTW + I find it somewhat hard to wrap my mind around how this works in 3D. Does it mean more vertical connections are encouraged - just as more entrances / side connections to rooms on the side of the corridor? Why have people discouraged more vertical connections in the name of FPS before? Has anyone tested this? What would low priority designations do to pathing when put alongside the corridors to discourage pathing through rooms?

[Col_Jessep]

Oh, thank you! That is interesting, Larix!

Part of my goal is to get a basic idea for designs that work well in A* and look nice, too. I'm not a programmer and have never really looked into the math and methods so far. Lowering the value for designations, I didn't even think of that! I'll dig into that threat in a moment.

PS: I tested the diagonal thing and it doesn't work, just like you said. So I have take results from this A* tool with a grain of salt.

I'm not a fan of the negative values. While you can test ingame what paths the dwarfs take in the end it isn't possible to see how long the path calculation took and how "expensive" it was. I'm kind of worried that the negative values could lead down a path to HFS. (I mean: While the path might look more favorable the actual calculation time and cost might not!)

While I was playing around with designs I found that triangular shapes brings problems with A*:



The fun part is that the calculation time for the triangular rooms on the right side is shorter than the cheaper looking rectangular rooms though!




Furthermore, the pathing cost of rectangular rooms depends a lot on where the doors/openeings are placed!



Putting the door in the middle lowers the calculation time by a factor of 5! 0_o

[Col_Jessep]

PS: Yeah, forget about the time this tool displays. It's measuring the time your browser needs to run the calculation in js. You might as well roll some dice or read tea leaves!
The number of calculations is the relevant factor (and the distance your dwarf actually has to move).

[etgfrog]

This is pretty interesting, it does explain alot regarding my fort design. The question I have is regarding using burrows to design a fort, just how modular should the fort be if your going to use the burrows and minecarts to solve the high fort population problem?

[Slogo]

Is Manhattan the heuristic that DF uses?

It seems a rather inefficient heuristic for a game where travelling diagonally seems to cost the same as going in a cardinal direction. It would also explain a lot of the inefficiencies in the first image shown I think. euclidean heuristic should produce better results I'd think.

EDIT: Nevermind, it backfills so much because the door is to the right of the target spot causing distance calculations to not be able to find the route easily.

Also this tool is great at showing how awesome it would be to have JPS in DF .

[Miuramir]

I took a look and it seems that the tool cannot handle diagonal-only connections. I.e. a chamber like this:

Code: [Select]

..#####
###...###
#A.123.B#
###...###
..#####

finds no path if an obstacle is placed at 1 or 3. It will path correctly if an obstacle is at 2 only. A dwarf, on the other hand, will find a path in any of the given cases.

I was poking about and it appears that is issue #63.  DF is unusual in that in most games an obstacle at 1 or 3 *would* block the path; DF walls in effect don't really fill their entire square except when Manhattan-adjacent. 

It appears that as of a few days ago, the underlying javascript library has been updated; you would use the new diagonalMovement: PF.DiagonalMovement.Always to simulate DF.  However, the very useful graphical demo and UI (which is what most if not all of us are using to play around with this) has not yet been updated.  If anyone is a Node.js expert, you could probably push the relevant fixes up to the main branch on GitHub and expedite things. 

Improving the demo (web version) to allow squares of different weight would be tremendously useful for DF, and a great project for someone with the rights skills and some spare time (or who could justify it as skill training). 

[Col_Jessep]

This is pretty interesting, it does explain alot regarding my fort design. The question I have is regarding using burrows to design a fort, just how modular should the fort be if your going to use the burrows and minecarts to solve the high fort population problem?

I honestly don't know. There are so many variables and the biggest problem is that I don't even know how dwarfs calculate moving to another z-level. The only thing I'm pretty sure of is that you want to have one large room per level. That is assuming Toady doesn't use another algorithm for moving between levels.

You probably want all your farmers, brewers, cooks and their workshops in one open area, all crafters in their own area, smiths... If those areas should be next to each other, above each other or far separated? I don't know. Smaller and closer is probably better.

The question is: How many workshops and stockpiles can you have in one room and how large is that room? With quantum stockpiles you can keep the room really small. And it's probably better to send minecarts to your magma forges deep down instead of having 20 dwarfs out on the surface cutting wood and hauling it back. Your goal should probably be to limit all your crafters, smiths... to their own large room with bedrooms and some food and drink close by. But in the end, idle dwarfs or training militia take their toll on the FPS and having 50 idle haulers won't help either.

I think a good strategy would be to have one quantum stockpile for almost all resources and only the workshops you really need. Trade for everything labor intensive that you can buy cheap like lye or food. All non-essential stocks and workshops could be moved to a different level and locked away until/if you need them.

And don't be stupid like I was and dig 10 levels of Nautikus Blossoms sprinkled across dozens of z-levels! =D

[TheHossofMoss]

That's freakin' sweet!

Nice work!

[utunnels]

My current fort has been running for 11 years. Now I have 140 dorfs and around 80 animals(most of them are pastured) and I have 8-9fps.

One of my workshop level has been completely mined out for stone/blocks industry. I don't know if it increases path finding cost between levels.

My fort extends from -29(HFS) to 148(tower/throne room), I guess sometimes they try to haul things from magma level to ground level and cause fps drop.

[Urist Da Vinci]

Is Manhattan the heuristic that DF uses?

It seems a rather inefficient heuristic for a game where travelling diagonally seems to cost the same as going in a cardinal direction.
...

It isn't, and it doesn't: http://www.bay12forums.com/smf/index.php?topic=72817.msg1794951#msg1794951 (and the whole 4th page of that thread)

[utunnels]

I tested my current fort by painting high/restricted areas and that didn't make a difference at all.
The game ran at 13 fps on my current computer (when all dorfs were moving to a burrow, it dropped to 10).

I guess maybe fps is affected by many things, simply optimizing an area doesn't make things much better.

My living area, according to your fist example, was a very bad design.

[Urist Da Vinci]

I tested my current fort by painting high/restricted areas and that didn't make a difference at all.
The game ran at 13 fps on my current computer (when all dorfs were moving to a burrow, it dropped to 10).

I guess maybe fps is affected by many things, simply optimizing an area doesn't make things much better.

My living area, according to your fist example, was a very bad design.

Many people see an FPS increase when painting the entire map as high traffic (or lowering the "normal" cost from 2 to 1).