最小化顶点距离的算法 - 矮人要塞

Question

我玩Dwarf Fortress游戏。我面临的主要挑战是有效设计堡垒的布局。这意味着，每个工业流程应尽可能密集，以尽量减少行驶距离。

一个例子可以是食品工业。每个灰色椭圆代表一栋建筑物。每个白色矩形代表建筑物的产品。

我的目标是要找到算法，将分布在二维网格中的建筑物为，使得这些建筑之间的距离是在这个意义上，他们是如何连接的最小。这意味着fishery和loom可以相距很远，但loom和farmer's应尽可能接近。

目前我已经考虑使用一些现成的软件来模拟布局，但是算法的一些提示会很好。

目前我正在考虑一些力导向算法，但我不确定离散电网的要求。

问题的形式化：是否有一个Force Draw Graph算法在离散坐标系下工作？

UPDATE：我发现在执行AS3的Force draw algorithm的（网页包含JS版本太多）。我会尝试将其转换为离散版本。但我有一些怀疑它会起作用...

UPDATE2：在评论中请求了一些进一步的限制。它们是： 每个建筑物都占用虚拟网格上的单个单元格。建筑物可以在相邻的单元格上。建筑物不能堆叠/重叠。 （PS：在游戏中，每座建筑物的尺寸都是一定的，通常是3x3，但我想保持这个问题更一般，以便采取更多方法）。

Answer 1

你几乎试图解决一个布局规划问题，在您试图最小化总“连接”长度的一个实例。大多数这些问题都是NP难题的例子，其中一些问题有伪多项式运行时算法。

有一种特殊情况下，您可能会感兴趣的是，实际上可以在多项式时间内完全解决：如果要提前知道要放置的“盒子”或建筑物的相对位置。

有关如何解决此特定情况的完整详细信息，请参阅此tutorial关于斯坦福大学的第6章第6.1节中的第几个编程，标题为“楼层规划”。另一个website还包括实现和解决问题的MATLAB代码（在第8章几何编程下）。

Answer 2

所以我设法做了一些代码，它解决了这个问题。这不是顶级产品，但它的工作。我计划随着时间的推移进行一些更新，但我没有设定任何时间框架。

的源代码是在这里：https://github.com/sutr90/DF-Layout

我的代码使用模拟退火方法。成本函数基于总面积，边的总长度和重叠。为了测量距离，我使用出租车司机的度量标准，但这是一个可以改变的主题。