Алгоритм минимизации расстояний вершин - Крепость гномов

Я играю в игра Dwarf Fortress. И главная задача для меня - эффективно проектировать расположение крепости. Это означает, что каждый поток промышленности должен быть как можно более плотным, чтобы минимизировать расстояния перемещения.

Примером может служить пищевая промышленность Food Industry. Каждый серый эллипс представляет собой одно здание. Каждый белый прямоугольник представляет собой продукт из здания.

Моя цель - найти алгоритм, который будет распределять здания на 2D сетке таким образом, чтобы расстояние между этими зданиями было минимальным в том смысле, в каком они связаны. Значение fishery и loom может быть далеко друг от друга, но loom и farmer's должны быть как можно ближе.

В настоящий момент я рассмотрел использование некоторого готового программного обеспечения для имитации макета, но некоторые подсказки для алгоритма будут в порядке.

В настоящее время я рассматриваю некоторый алгоритм с принудительной ориентацией, но я не уверен в требовании дискретной сетки.

Формализация вопроса: существует ли алгоритм диаграммы Force Draw, который работает в дискретных координатах?

UPDATE: я нашел реализацию алгоритма принудительной вытяжки в AS3 (в Интернете также есть версия JS). Я попытаюсь преобразовать его в дискретную версию. Но у меня есть некоторые сомнения, что это сработает...

UPDATE2: В комментариях были запрошены дополнительные ограничения. Вот они: Каждое здание занимает одну ячейку виртуальной сетки. Здания могут находиться на смежных ячейках. Здания не могут складываться/перекрываться. (PS: В игре каждое здание имеет размер, обычно 3x3, но я хочу, чтобы проблема была более общей, чтобы было больше подходов).

Ответы

Ответ 1

Вы в значительной степени пытаетесь решить экземпляр проблемы планирования пола, когда вы пытаетесь свести к минимуму общую длину соединения. Большинство из этих проблем - примеры NP-жестких задач, некоторые из которых имеют псевдополиномиальные алгоритмы времени выполнения.

Существует особый случай, который может вас заинтересовать, который фактически полностью разрешимо в полиномиальное время: если относительные позиции "ящиков" или зданий, которые вы хотите разместить, известны заранее.

Подробные сведения о том, как решить этот конкретный случай, см. в tutorial по геометрическому программированию из Стэнфордского, глава 6, раздел 6.1, первый пример под названием "Планирование этажей". Другой веб-сайт также включает в себя код Matlab, который реализует и решает проблему (в главе 8 "Геометрическое программирование" ).

Ответ 2

Поэтому мне удалось сделать код, который аппроксимирует решение этой проблемы. Это не продукт высшего класса, но он работает. Я планирую делать некоторые обновления с течением времени, но у меня нет никаких временных рамок.

Исходный код здесь: https://github.com/sutr90/DF-Layout

В моем коде используется метод Simulated Annealing. Где функция затрат основана на общей площади, общей длине ребер и перекрытия. Чтобы измерить расстояние, я использую метку такси, но это может быть изменено.