Algorithm to minimize vertex distances – Dwarf Fortress
January 23, 2014  Posted by forumadmin under TechQns 
Comments off

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 forcedirected 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 3×3, but I want to keep the problem more general, to allow for more approaches).
Asked By – jnovacho  Read Answers 