Algorithm to minimize vertex distances - Dwarf Fortress

Question

I play Dwarf Fortress game. And the main challenge for me is to design layout of the fortress efficiently. Meaning, that each industry flow should be as dense as possible, to minimize the travel distances.

An example could be food industry . Each grey ellipse represents a single building. Each white rectangle represents product from the building.

My goal is to find algorithm which would distribute the buildings on 2D grid in such manner that distance between those building is minimal in the sense how they are connected. Meaning that fishery and loom can be far apart, but loom and farmer's should be as close as possible.

At the moment I have considered using some ready software, to simulate the layout, but some tips for algorithm would be fine.

Currently I'm considering some force-directed algorithm, but I'm not sure about the discrete grid requirement.

Formalization of question: Is there a Force Draw Graph algorithm which works in discrete coordinates?

UPDATE: I have found implementation of the Force draw algorithm in AS3 (the web contains JS version too). I will try to convert it to discrete version. But I have some doubts it will work...

UPDATE2: Some further restrictions were requested in comments. Here they are: Each building occupy single cell on virtual grid. Buildings can be on adjacent cells. Buildings cannot stack/overlap. (PS: In game, each building has deifned size, usually 3x3, but I want to keep the problem more general, to allow for more approaches).

Lubeck

Does each building only occupy a single square of the grid? Right now you've got no lower bound on any edge length, so the optimal solution is going to be everything stacked on top of eachother. – Hotblooded

Buildings occupy 3x3 square, several types has 5x5 size in-game grid units. But for sake of generality, let's say each building can occupy single grid cell and buildings cannot stack. – Lubeck

my guess is that the problem has too many facets to be wrangled into any existing algorithms. My gut instinct says some form of simulated annealing approach would work best here. – Compaction

Also; why restrict to a single 2d plane? That way, you will never get a competitive fortress. In 3d we have far more options for finding an efficient arrangement. – Compaction

Well my idea was that 2D means less degrees of freedom and thus simpler algorithm. Plus I'm used to build workshop on level z0 and stockpiles for them on level z+1/-1. Thus distribution on plane. – Lubeck

Answer 1

You are pretty much trying to solve an instance of a floor-planning problem where you are trying to minimize the total "connection" length. Most of these problems are instances of NP-hard problems, some of them have pseudo-polynomial run-time algorithms.

There is a special case you might be interested that is actually fully solvable in polynomial time: if the relative positions of the "boxes" or buildings you want to place are known ahead of time.

For full details on how to solve this particular case, please refer to this tutorial on geometric programming from Stanford, chapter 6, section 6.1 the first example entitled "Floor planning." Another website also includes matlab code that implements and solves the problem (under chapter 8 Geometric Programming.)

Scutellation

I've just quickly gone through the paper you've linked and I think it won't work. Because in my case A is connected to B, doesn't say anything their relative position and vice versa. – Lubeck

Yes, but I guess what I'm saying here is unless you assert relative positions of each with respect to the other you have an instance of general floor-planning, which is pretty much guaranteed to be NP-hard. The implied suggestion here is, find a reasonable algorithm to pre-impose the relative positions then do the strict optimization problem that falls out of it. Repeat and continue for N such configurations until you achieve a desired minimum total connection length. – Scutellation

This may be of interest to you: academics.smcvt.edu/jellis-monaghan/papers/papers/… – Scutellation

Thanks for the chip design link. It is a push in correct direction. Concerning the restricted floor planning suggested earlier, I got an idea of using topological sorting as heuristic. With topo sort it should be possible to recognize "which processes can run in parallel", e.g. determine up/down relation and which are serial e.g. left/right relation. – Lubeck

@Lubeck If you get this working and are amenable to sharing your code I would be very interested to take a look to see what ideas you came up with. – Scutellation

I've posted an answer with link to source code. At first I wasn't about to release the code, so it's not "pretty". Also no guarantees provided. – Lubeck

Answer 2

So I've managed to do some code which aproximates solution of this problem. It's not a top class product but it's working. I plan to do some updates over time, but I don't have any time frame set.

The source code is here: https://github.com/sutr90/DF-Layout

My code uses Simulated Annealing approach. Where cost function is based on total area, total length of edges and overlap. To measure distance, I use taxi-cab metric, but that is a subject to change.

Lubeck

Have you compared against any other approaches? This is a cool bit of research-- it would make a great blog post or even a research paper if you can improve on the state of the art! – Knudsen

No, not really. But I'm considering some future development in this topic. Just not at this moment. :) – Lubeck