Алгоритм минимизации расстояний между вершинами - Dwarf Fortress
Я играю в игру Dwarf Fortress. И главная задача для меня - это эффективно спланировать крепость. Это означает, что каждый отраслевой поток должен быть максимально плотным, чтобы минимизировать расстояния перемещения.
Примером может служить пищевая промышленность. 
, Каждый серый эллипс представляет собой одно здание. Каждый белый прямоугольник представляет изделие из здания.
Моя цель - найти алгоритм, который бы распределял здания по двумерной сетке таким образом, чтобы расстояние между этими зданиями было минимальным в том смысле, как они связаны. Означающий, что fishery а также loom может быть далеко друг от друга, но loom а также farmer's должно быть как можно ближе.
На данный момент я подумал об использовании некоторого готового программного обеспечения для имитации макета, но некоторые советы по алгоритму были бы хороши.
В настоящее время я рассматриваю некоторый алгоритм направленной силы, но я не уверен насчет требования к дискретной сетке.
Формализация вопроса: существует ли алгоритм Force Draw Graph, который работает в дискретных координатах?
ОБНОВЛЕНИЕ: Я нашел реализацию алгоритма отрисовки Force в AS3 (в Интернете также есть версия JS). Я постараюсь преобразовать его в дискретную версию. Но у меня есть некоторые сомнения, что это сработает...
ОБНОВЛЕНИЕ 2: Некоторые дополнительные ограничения были запрошены в комментариях. Вот они: Каждое здание занимает одну ячейку на виртуальной сетке. Здания могут быть на соседних клетках. Здания не могут складываться / перекрываться. (PS: В игре каждое здание имеет определенный размер, обычно 3х3, но я хочу, чтобы проблема была более общей, чтобы было больше подходов).
2 ответа
Вы в значительной степени пытаетесь решить проблему планирования пола, при которой вы пытаетесь минимизировать общую длину "соединения". Большинство из этих проблем являются примерами NP-сложных задач, некоторые из них имеют псевдополиномиальные алгоритмы времени выполнения.
Вас может заинтересовать особый случай, который на самом деле полностью решаем за полиномиальное время: если относительные положения "ящиков" или зданий, которые вы хотите разместить, известны заранее.
Для получения полной информации о том, как решить этот конкретный случай, обратитесь к этому руководству по геометрическому программированию из Стэнфорда, глава 6, раздел 6.1, первого примера, озаглавленного "Планирование этажей". Другой веб-сайт также содержит код matlab, который реализует и решает проблему (в главе 8 "Геометрическое программирование").
Таким образом, мне удалось сделать некоторый код, который приближает решение этой проблемы. Это не продукт высшего класса, но он работает. Я планирую сделать некоторые обновления с течением времени, но у меня нет установленных временных рамок.
Исходный код находится здесь: https://github.com/sutr90/DF-Layout
Мой код использует метод имитации отжига. Где функция стоимости основана на общей площади, общей длине ребер и перекрытии. Для измерения расстояния я использую метрику такси, но это может быть изменено.