13

我玩矮人要塞游戏。对我来说主要的挑战是有效地设计堡垒的布局。这意味着，每个行业的流动都应该尽可能密集，以尽量减少旅行距离。

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

我的目标是找到一种算法，它将建筑物分布在 2D 网格上，使得这些建筑物之间的距离在它们如何连接的意义上是最小的。这意味着fisheryandloom可以相距很远，但loomandfarmer's应该尽可能近。

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

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

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

更新：我在 AS3 中找到了Force draw 算法的实现（网络也包含 JS 版本）。我将尝试将其转换为离散版本。但我怀疑它会起作用......

UPDATE2：在评论中要求进行一些进一步的限制。它们在这里：每栋建筑都占据虚拟网格上的单个单元格。建筑物可以在相邻的单元格上。建筑物不能堆叠/重叠。（PS：在游戏中，每个建筑物都有定义的大小，通常是 3x3，但我想让这个问题更笼统，以允许更多的方法）。

4

2 回答 2

9

您几乎是在尝试解决平面规划问题的一个实例，在该实例中您试图最小化总“连接”长度。这些问题中的大多数是 NP-hard 问题的实例，其中一些具有伪多项式运行时算法。

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

有关如何解决此特殊情况的详细信息，请参阅斯坦福的几何规划教程，第 6 章，第 6.1 节第一个示例，标题为“平面设计”。另一个网站还包含实现和解决问题的 matlab 代码（在第 8 章几何编程下。）

于 2014-01-23T21:31:31.543 回答
2

所以我设法做了一些代码来解决这个问题。它不是一流的产品，但它正在发挥作用。我计划随着时间的推移进行一些更新，但我没有设置任何时间框架。

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

我的代码使用模拟退火方法。其中成本函数基于总面积、边缘总长度和重叠。为了测量距离，我使用出租车公制，但这可能会发生变化。

于 2014-01-30T19:26:08.130 回答