Я играю в игра Dwarf Fortress. И главная задача для меня - эффективно проектировать расположение крепости. Это означает, что каждый поток промышленности должен быть как можно более плотным, чтобы минимизировать расстояния перемещения.
Примером может служить пищевая промышленность 
. Каждый серый эллипс представляет собой одно здание. Каждый белый прямоугольник представляет собой продукт из здания.
Моя цель - найти алгоритм, который будет распределять здания на 2D сетке таким образом, чтобы расстояние между этими зданиями было минимальным в том смысле, в каком они связаны. Значение fishery и loom может быть далеко друг от друга, но loom и farmer's должны быть как можно ближе.
В настоящий момент я рассмотрел использование некоторого готового программного обеспечения для имитации макета, но некоторые подсказки для алгоритма будут в порядке.
В настоящее время я рассматриваю некоторый алгоритм с принудительной ориентацией, но я не уверен в требовании дискретной сетки.
Формализация вопроса: существует ли алгоритм диаграммы Force Draw, который работает в дискретных координатах?
UPDATE: я нашел реализацию алгоритма принудительной вытяжки в AS3 (в Интернете также есть версия JS). Я попытаюсь преобразовать его в дискретную версию. Но у меня есть некоторые сомнения, что это сработает...
UPDATE2: В комментариях были запрошены дополнительные ограничения. Вот они: Каждое здание занимает одну ячейку виртуальной сетки. Здания могут находиться на смежных ячейках. Здания не могут складываться/перекрываться. (PS: В игре каждое здание имеет размер, обычно 3x3, но я хочу, чтобы проблема была более общей, чтобы было больше подходов).
