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).

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.)

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.