Print

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

[csp256]

I heard that FPS-death puts a soft-cap on the number of dwarves you can have, so I thought it would be fun to design a CPU-friendly fortress without sacrificing dwarfpower (industrial efficiency). Obviously these are somewhat conflicting objectives. So far I've set invaders off and am solely exploring fortress-building, for now [I know, I know: that's not very dwarven of me].

I'm very new to DF and would like some help from more experienced players in refining this idea.

My idea relies primarily on trying to optimize pathfinding. I intend to try to do this by keeping the search horizon small (average number of nodes expanded/evaluated per search). I intend to do this by isolating functional elements of the fortress's industries. For example, imagine a fortress which was a series of disconnected cubes (or any connection between them had a very high travel cost). Each cube specialized in some aspect(s) of the economy. They would take some inputs from one or more cubes (nodes), and give outputs to one or more nodes. Automated minecarts would be used to do this, in hopes that the track simplifies their pathfinding (I'm still unsure of exactly how minecarts work).

Each cube would have self contained living quarters for the dwarves imprisoned living there, as well as other distractions they need (should they fall idle from bottlenecks above them in the supply-chain). Each one of these cubes would be highly self-connected (lots of stairs), and as compact as possible without causing the dwarves within to walk over each other [exploiting some of the standard tricks]. This is because backtracking causes the search horizon to grow by a significant amount. Use the default settings of this (which I believe reflects what DF uses) to see what I mean: http://qiao.github.io/PathFinding.js/visual/

It would probably be best if there was a path into each cube, but with traffic restrictions set (solely for migrants/justice/vampires/unforeseen emergencies/etc). This might cause migrants to search the entire map when first going to their cube, but that cost is heavily amortized. I understand that setting burrows helps dwarves pick jobs only within the burrow. Obviously each cube would be its own burrow.

How would I, say, evenly distribute food? Lets say I grew a bunch of plump helmets in one cube, and I had 8 cubes I wanted to split it between. Can I simply load a minecart full of plump helmets, and direct the cart down one of 8 tracks? (On a related note, how hard would building an XOR gate, or a 3bit counter be?) Or would using multiple carts be best? How do I prevent accidentally letting a cube starve?

I hear that having many small stockpiles can cause CPU problems. What is at the root of this, is there a way to fix it, and is there any science that can be done to more clearly identify the problems.

PS: being able to create a traffic designation group, then assign individual dwarves to that group, could help quite a lot in optimizing FPS without taking the plunge into parallelism.

PPS: The fractal bedroom designs I've seen have a tendency to be extremely pathfinding performance-unfriendly. http://dwarffortresswiki.org/index.php/File:Hactar1_Mandelbrot_Tree.png This design requires the expansion of almost every node on the floor in order to reach ANY room! It would be challenging to create a less CPU-efficient design.

[Catsup]

i also face a massive fps decrease when i have 100+ dwarves due to pathing calculations. Anyone know the optimal traffic designations for each type of room and space such that fps is kept to a max?

in previous forts where i never used such designations i've dropped to 5-20 fps and stayed there most of the time, in my current fort where i tried using traffic designations i have an average of 15-40 fps (which drops when i get sieged due to invader pathing calculation, or when i order mass tree-cutting in open areas without traffic designations).

i still think my designations arent the most efficient though.

[WealthyRadish]

Pathfinding is a major problem, but not the only one. Accumulation of items causes a massive drop if not controlled, so destroying unneeded items and not overproducing is very important. The number of revealed tiles is also a large factor, so embarking in a 3x3 or smaller site helps, as well as avoiding revealing the caverns (using DFhack to reveal the map and then plan staircases around them) and digging out too much space. Not having any animals, turning off temperature, and basic pathfinding reduction are other things that can be done.

I wouldn't be overly concerned with getting the best pathfinding layout evar, as the limiting factor will end up being something else if not also controlled. That said, this is a cool idea, so go ahead and dwarf your heart out. If you get a vampire, you should get his blood in a well vampurify everyone as well, so each block won't need farms.

[Victor6]

If you don't want to avoid the caverns as UrbanGiraffe suggested, consider creating a world with advanced parameters and messing with the cavern settings;
http://dwarffortresswiki.org/index.php/Advanced_World_Generation#Cavern_Parameters.
Those default swiss-cheese caverns are a nightmare for pathing.

[csp256]

@Catsup

Play around with that pathfinding visualizer I linked. http://qiao.github.io/PathFinding.js/visual/ Place start and goal on same y, different x. Place a big wall running up and down halfway between them, with a single hole right between them. Run the simulation (nodes expanded is linear with the path distance).

Add a second wall running parallel to the first, also with a single hole. Run the simulation multiple times with this hole in various places. (moving up one each simulation). You'll notice the further the path goes in between these two walls the more the search horizon (light green squares) extend past the start point in the wrong way. Therefore the worst case search horizon is roughly proportional to path length times the square of the inaccuracy of the heuristic... when on a simple 2d plane. Things get FUN in 3d if you set them up like this, as you get memory usage/running time proportional to the cube of the inaccuracy. This is a strong argument for highly connected fortresses.
 
Try moving the start and/or goal up and down. You'll see this only increases the inefficiency, even though this is a simple and fairly realistic example.

I found an interview with Toady which said that the dorfs use a "streetcar distance" (which I take to mean Manhattan/taxicab metric), but isn't that an inadmissible heuristic for A* with diagonal movement due to overestimation? Perhaps he misspoke and meant Chebyshev metric. Try playing around with them, they are similar enough for the experiment I outlined above. Oh, and the wiki states that diagonal motion takes 1.4 as long as straight. Since dorfs prefer diagonal movement and 1.4 < sqrt(2), we can't rule out that they use the Euclidean metric either.

But he also hints that he is doing some sneaky stuff in the background (validating that paths from A to B exist before checking them) and gives almost no details. Probably not HPA*, but probably similar. (HPA* uses a pre-processed graph abstraction layer that can rapidly find if a path exists, and a path, though perhaps not the best) A bug tracker post by him seems to indicate that locking a door causes this abstraction to be rebuilt, albeit inefficiently.

--

@UrbanGiraffe

Are we sure that items have a significant CPU impact? I though I had read that the current suspect for this was actually stockpiles, and that one of the quantum methods seemingly prevented a significant framerate decrease even with tens of thousands of items.

I have a small number of animals (caged), I embarked on 16x16 for testing purposes, aquifer/weather/temperature turned off, have the entire map revealed but no cavern access (those are uncontrolled variables).

Moreover, temperature would seem to be a constant CPU load. Pathfinding would seem to be roughly proportional to the number of actors moving around. Therefore if you half the amount of work it takes for the dorfs to go from A to B then you might not double framerate, but you could double the amount of dorfs [assuming pathfinding is the majority of a dorf's CPU impact].

--

@Victor6

So would just walling off the caverns with locked doors/hatches prevent that problem? Or molding the caverns into a more dwarven shape?

--

I've been looking at mechanical logic for controlling minecarts, but don't want to have to rely on waterwheels to power them (fluid sims being an unnecessary and uncontrolled variable in my experiment). How would I mod the game so either these things require 0 power, or a single water wheel / windmill provides an incredible amount of power?

[Victor6]

Even if you block off large sections of the caverns, monsters can still spawn and move around outside (and thus clog the pathfinding). It's been hit and miss for me, so if you're dead set on your current game world\fort then give it a shot, if not then just go with open caverns.

[Catsup]

@Catsup

Play around with that pathfinding visualizer I linked. http://qiao.github.io/PathFinding.js/visual/ Place start and goal on same y, different x. Place a big wall running up and down halfway between them, with a single hole right between them. Run the simulation (nodes expanded is linear with the path distance).
...
But he also hints that he is doing some sneaky stuff in the background (validating that paths from A to B exist before checking them) and gives almost no details. Probably not HPA*, but probably similar. (HPA* uses a pre-processed graph abstraction layer that can rapidly find if a path exists, and a path, though perhaps not the best) A bug tracker post by him seems to indicate that locking a door causes this abstraction to be rebuilt, albeit inefficiently.

does this mean we have to set open spaces on the other side of a wall to be all restricted traffic if there is ANY way to access it? i noticed that if i placed a single wall between the 2 points the path finding AI fucked up really badly spreading out randomly behind the wall before finally going around it:
                       W                           B
                       W
                       W
                       W
                       W   
A                     W

[WealthyRadish]

It would seem that item count itself is indeed not necessarily the cause of FPS drop, at least from this thread. Incidentally, the guy did actually quit the forum after that second post. Hardcore.

Temperature's load comes from checks forced by change and differences, IIRC, so having tons of stuff and entities forces frequent checks (and is why moving magma kills FPS so much). If it's off, there isn't anything to worry about, though.

Keep in mind that unlike other items, clothing will become a major problem, as periodic checks are needed on each piece to determine wear. You can minimize this by forcing minimalist or armor-only uniforms and destroying the heaps of crap dwarves wear, or by adding [ARMORLEVEL:1] to all clothing entries in the raws.

[Catsup]

It would seem that item count itself is indeed not necessarily the cause of FPS drop, at least from this thread. Incidentally, the guy

i didnt really understand that thread, but i use minecart stops to stockpile items automatically. Did the other thread mean you lose fps if you use normal stockpiles?

[csp256]

@Catsup

You cut out the interesting part of my post in your reply. Reread it. Run the experiment. Watch the horizon expand as the heuristic is increasingly inaccurate. What it means is that your path from A to B must be as direct as possible with as little as possible backtracking. Distance of the path is only a secondary concern.

Of course we don't really know what Toady does for pathfinding. His saying it is A* is likely inaccurate. It is likely a HPA* variant. We can't draw firm conclusions without that knowledge. But we can run experiments.

@UrbanGirrage

Hardcore might not be the word, but I'm definitely not sure what is.

I was planning on "recycling" (atom smashing) all the non-masterwork/legendary gear my dwarves make. Armor-only uniforms seem the more dwarven route.

@Victor6

Current fortress is actually already built around the caves [but this one is focused on trying to build a dwarfputer while I procrastinate studying for finals]. 200 fps with 190 dwarves (50 idle) and ~100 animals. Of course I have a lot of the fun stuff turned off, but I do have an aquifer.

[DWC]

I'm also trying to figure out the most optimal fortress layout to reduce pathing and keep up a lot of production. I came to a similar conclusion, with all workshops, stockpiles the whole supply chain of a particular industry should be 'vertically integrated' (pun). Because travel between z-levels on stairs is the same speed as x/y travel, it's extremely important to basically stack everything associated with an industry on top of one another and keep x/y space as compact as possible. That said, minecarts are meant for long distance hauling on the same level, they are much less valuable hauling between z-levels and they also take up a lot of space themselves.

The pathfinding in DF apparently looks at objects on different z-levels as if they were on the same z-level. A mason looking for a stone will travel across half the fortress to your central staircase, down 40 levels and back to a stone that happened to be directly under his workshop 40 levels above, while bypassing other stones.

The main problem I have is figuring out how to achieve efficiency with a standard repeatable blueprint or layout that is flexible enough to handle modifications well. My best idea is a central 5x5 room, with staircases in each corner, with 6 workshop rooms connected to it, so it has doors that can be locked. It's simple but not as flexible or efficient as I'd like.

Thing is, the space requirements, production rates and supply chains for each industry are not the same, each 'cube' would have to be basically custom-built for maximum efficiency. Compare a complex industry like clothing to something simple like gem cutting/ setting. Then you'd also have areas where industries overlap, you'd want those cubes integrated as well.

[csp256]

I've procrastinated enough to force myself to study for tomorrow's finals, so I won't be able to reply properly for a couple days. Until then:

Are minecarts that bad at up/down movement? This post seems to indicate that they can be used effectively across many z levels: http://www.bay12forums.com/smf/index.php?topic=109460.msg3361523#msg3361523 Of course they require power, which either does cruel things to your fps (heh) or use windmills. The wiki makes it sound like windmills just stop producing power some times (does wind level change over time?).

I was unaware of the behavior of dorfs ignoring z for job selection (well, I hear that jobs chose the dwarves, not the other way around, but all the same for this purpose). That certainly complicates makes things more fun.

Yes, you might want to have an overflow stockpile which goes to an atom smasher for industries which overproduce. I was thinking about a semi-automatic way to have a magma forge/smelter combo that only exported masterwork menacing spikes (or what not) for their ridiculous value in weapon traps. It'll take experimentation which I can't do just now.

We'll have to figure out something for the dorfs which are only infrequently used so they don't stay idle too long. Perhaps they can each have their own garden/still (farms are absurdly space efficient).

Also, how would you get supplies to a dwarf who has a mood?

[DWC]

I sketched up a layout that I think is pretty much ideal for creating these efficient, self-sustaining 'cubes.

Basically, it's 3x7 rooms with two workshops or stockpiles, with a up/down staircase in the middle, stacked above one another.

 At it's basic level, you have the raw materials on the top, stockpiles and workshops in the middle, finished goods and bedrooms/ breakrooms at the bottom. If you take the convoluted supply chain for clothing, with full vertical integration (meaning all parts of the supply chain are produced in the cube, from farm plots to dyed, decorated clothing) I doubled them up, because you'd need at least 14 levels of 3x7 rooms to do it, so instead 7x7 rooms over 7 z-levels, like an actual cube, all one burrow.
example:
level 1 (soil)- 3x3 pigtail farm, 3x3 dimple cup farm, 3x7 plump helmet farm
level 2- plant stockpile
level 3- farmer's workshop (x2) and some querns or a mill.
level 4- thread stockpile, dyer's shop x 2
level 5- thread stockpile, loom x 2
level 6- 3x7 cloth stockpile, clothier's shop x2
level 7- finished goods stockpile

WWW+WWW
WWWXWWW
WWW+WWW

Then you can put in about 3 levels of bedrooms, you can squeeze 8 2x2 bedrooms in a 7x7 space, or 4 4x4 rooms if you prefer. Could use another level for a dining room/ food/ booze stockpile, or more efficiently, just stick tables and chairs in the empty spaces on the industrial levels in lieu of a 'real' dining room.

This is just what I sketched up and it could use some experimentation I figure this set up will take about 12 dwarves, with no specialized haulers, bottlenecked workers can do hauling while they wait for work and because the shops are so close to one another, a craftsman can just walk upstairs and take what they need from the cluttered workshop. More efficiency/ less levels could be possible with quantum dumps or 'undump engines' and things to replace conventional stockpiles.

Problems with this layout, it's not very secure, you could stick hatches and doors on the levels with moodable workshops, but that'd shut down the entire factory if you had a worker seize one of the shops for an shell artifact or somesuch. You could run a wall between the two 3x7 sections to create a bypass so workers can reach their rooms and do other work in the meantime.

I'm really quite busy myself so I'm not sure how much time I'll get to try this out.

[fractalman]

I'm running some experiments in passyrups-never creating more than 20 piles, trying to stockpile as few things as possible...

I think my best idea, though, is to clean up a mine once it's more than 100 tiles away from the central staircase with dbd...
and then seal it up to keep the pathing algorithm from wasting time in a labyrinth, or worse, a quarry.

cleaning it out first is a must-otherwise, cycles may be wasted in an effort to prove that an item is, in fact, inaccessible. 

[DWC]

I'm running some experiments in passyrups-never creating more than 20 piles, trying to stockpile as few things as possible...

I think my best idea, though, is to clean up a mine once it's more than 100 tiles away from the central staircase with dbd...
and then seal it up to keep the pathing algorithm from wasting time in a labyrinth, or worse, a quarry.

cleaning it out first is a must-otherwise, cycles may be wasted in an effort to prove that an item is, in fact, inaccessible.

I've thought about this too. I really hope dwarves don't find any reason to path into an empty mine after they are walled up. Magnetite mines especially. My policy will be to work one vein at a time, make sure it's empty, forbid the whole area and any items that might be invisible, then wall it up before moving to the next one. I wonder if a locked door or drawbridge would suffice in case I decide to poke around there in adventure mode and if anything could go wrong by smoothing and engraving the mine just for fortress value purposes.