Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  

Author Topic: Fortress design as graph optimization  (Read 3229 times)

fourthgeek

  • Escaped Lunatic
    • View Profile
Fortress design as graph optimization
« on: December 25, 2014, 01:41:24 am »

As a fun little project I decided to try creating a pipeline for procedural optimization of fortress design. That is, the goal is to minimize travel distance between different activities in the fort.

So I made a tiny little helper program (happy to share) that takes in a description of the dependencies in DF's game mechanics (pasture->butcher->soapmaker->hospital for example) and a description of the fort that should be generated (eg, large pasture, no hospital, etc). It generates a fortress description which can then be read in by BioLayout. That program generates an optimized 3D layout of the fort. In effect we are using scientific analysis software to design our fort.

I haven't messed with it very long. I was wondering if any similar work has been done elsewhere and if there might be better tools for doing this sort of work.

Here's an example result(1),(2),(3) that was generated. Some steps may be missing but it should get the idea across. Note how (1) and (3) have slightly different designs for the hospital. I used a slightly more expensive layout algorithm in 3. According to (1) we should design hospitals sandwiched between their resources. According to (3) we should design our hospitals like a cylinder with its materials at the core of the cylinder.
« Last Edit: December 25, 2014, 02:21:36 am by fourthgeek »
Logged

Dwarf4Explosives

  • Bay Watcher
  • Souls are tasty. Kinda like bacon.
    • View Profile
Re: Fortress design as graph optimization
« Reply #1 on: December 25, 2014, 09:47:59 am »

Interesting. I think the design for hospitals given in (3) would probably work best.
Logged
And yet another bit of proof that RNG is toying with us. We do 1984, it does animal farm
...why do your hydras have two more heads than mine? 
Does that mean male hydras... oh god dammit.

Miuramir

  • Bay Watcher
    • View Profile
Re: Fortress design as graph optimization
« Reply #2 on: December 25, 2014, 01:35:06 pm »

So I made a tiny little helper program (happy to share) that takes in a description of the dependencies in DF's game mechanics (pasture->butcher->soapmaker->hospital for example) and a description of the fort that should be generated (eg, large pasture, no hospital, etc). It generates a fortress description which can then be read in by BioLayout. That program generates an optimized 3D layout of the fort. In effect we are using scientific analysis software to design our fort.

I've just grabbed BioLayout 3.3, and hope to have a chance to play with it soon; I'm interested in your helper program. 
Logged

Chief10

  • Bay Watcher
  • since 31
    • View Profile
Re: Fortress design as graph optimization
« Reply #3 on: December 25, 2014, 10:33:24 pm »

Very interested in this, but do you have a way of converting the ball-and-stick model to a grid-based pattern?
Logged

Urist Da Vinci

  • Bay Watcher
  • [NATURAL_SKILL: ENGINEER:4]
    • View Profile
Re: Fortress design as graph optimization
« Reply #4 on: December 25, 2014, 11:20:14 pm »

http://mkv25.net/dfma/map-10123-castleshoot

If the meeting room is at the center, and you include all possible diagonal directions, there are 26 directions that can be traveled. There are 9 rooms above, 9 rooms below, and 8 rooms on the same level as the meeting room. Since most idlers will be found in the meeting room, this allows most dwarves to walk in a near-straight line to a destination. Diagonal ramp hallways are possible.

Outer rooms that share resources could be linked by direct paths to save dwarves from having to walk to the core and then back out again.

Itnetlolor

  • Bay Watcher
    • View Profile
    • Steam ID
Re: Fortress design as graph optimization
« Reply #5 on: December 26, 2014, 01:35:30 am »

That's very nifty. I like that trick.

tussock

  • Bay Watcher
    • View Profile
Re: Fortress design as graph optimization
« Reply #6 on: December 26, 2014, 02:46:03 am »

So, it looks like you're making a lot of "cloth" balls to allow for how much of it is carried around, but only one "clothier" ball because there's only one place it's take. But only a very small amount of cloth is ever carried to the hospital, almost all of it goes through the weaver-dyer-clothier cycle. One hospital ball and many clothiers would better represent traffic (which is mostly per-job).

Also, it's more important for production rates that workshop inputs are close, outputs barely matter as the time to reach a stockpile barely matters (assuming your stockpiles are working), so to some extent you can treat the input stockpiles as part of the workshop. That may or may not make things tidier, it varies when I mess around with Graphviz. I've seriously hit the limit with 2D representation though.

As Da Vinci noted, walking time to start jobs from idle also matters for the one-offs and short-run jobs, like Butcher/Tanner and it's accompanying mass stockpiling. I never worry for the busy stuff like repeat crafting, dyeing, or big clothes or furniture making runs.
Logged

fourthgeek

  • Escaped Lunatic
    • View Profile
Re: Fortress design as graph optimization
« Reply #7 on: December 26, 2014, 07:23:06 pm »

I'm interested in your helper program. 
Source (C++) and executable (win32) are here: http://s000.tinyupload.com/?file_id=00734057641410667840

I've whipped it together very quickly so it's fairly ... dwarvenly.

nodes.txt describes the fortress "schema" which is a list of rooms and relationships between rooms. In the example file, room 1 is a wood stockpile of size 25, linked to the carpenter, craftsdwarf, siege_ws, woodfurnace, and bowyer. The format of each room entry is name:size|dependents,... and you can add as many new rooms as you like. Room numbers start at 1 so you can use line numbers to set up dependent rooms easily. The default schema that I've provided is very limited and probably inaccurate but it gives some idea of usage. You can have multiple rooms of the same type; just give rooms the same name and biolayout will consider them to be of the same 'class' (color, etc).

After setting up nodes.txt: run the program and it will save outedges.layout in the same directory. That file can be opened by biolayout.


Very interested in this, but do you have a way of converting the ball-and-stick model to a grid-based pattern?

Biolayout can render the balls as cubes, but I don't think theres a way to hide the edges (sticks) or to force a quantized positioning. If there are better tools that can do this I'd love to try them. Gephi did not work well at all in 3D.

So, it looks like you're making a lot of "cloth" balls to allow for how much of it is carried around, but only one "clothier" ball because there's only one place it's take.
...
to some extent you can treat the input stockpiles as part of the workshop.

Every node in this graph represents a physical location, so all of those cloth nodes are representing a cloth stockpile. If production and consumption of cloth are well synchronized then you may not need a stockpile at all, or you may be able to assume that the stockpiles can be small enough to fit in the gaps between spaces. It would be perfectly valid to simplify by removing all stockpiles from the model.

Also, it's more important for production rates that workshop inputs are close, outputs barely matter
...
walking time to start jobs from idle also matters

Agreed. A robust solution needs to be able to weight these edges to make clear how some relationships are more important than others.  If we assume that idlers are spending their time in the dining area, then weak relationships between the dining area and all workshops could allow us to model that relationship.
Logged

RandomizedThinker

  • Bay Watcher
    • View Profile
    • my tumblr
Re: Fortress design as graph optimization
« Reply #8 on: August 04, 2015, 02:59:47 am »

may you reupload your program again? preferably not in a website that does "exceeded maximum storage time (100 days from last download)."
Logged