4

我有一个预定大小的二维数组和一个适合该空间的编号矩形列表。这些矩形中的每一个都具有已知的固定高度和宽度。保证 2D 阵列足够大以舒适地适应所有矩形。

我需要将这些矩形中的每一个随机放置到数组中，以便没有重叠并且全部放置。它们可以放置在任何方向。想象一下，将您的船只置于战舰游戏中，只是拥有更多不同的船只尺寸和更大的网格。

完成后的数组应该是这样的：（0代表一个空格，一个非零数字代表一个矩形数字）

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 2 0 0 0 0 0 0 0 0
0 0 0 2 2 2 2 0 0 0 0 0 0 0 0
0 0 0 2 2 2 2 2 0 5 5 0 0 0 0
0 3 3 3 3 3 0 0 0 0 5 5 0 0 0 0
0 3 3 3 3 3 0 7 7 7 5 5 6 6 0 0
0 0 0 0 0 0 0 7 7 7 5 5 6 6 0 0

我考虑过的一种方法是为每个矩形选择一个随机的位置和方向，尝试将其放置在矩阵中。如果检测到与先前放置的块发生冲突，请重试。这可能是最简单的实现，但它似乎不是很有效，并且它不会以明确确定的方式终止（列表末尾附近的矩形可能会在很长一段时间内与先前生成的块发生冲突）。

有没有更好的方法来解决这个问题，放置后面的矩形不会那么成问题？

4

4 回答 4

1

IMO 问题降级为问题 - “我们是否有足够的空间来容纳下一个矩形以及如何以有效的方式找到这个地方？” 所以：

  1. 初始条件 - 我们在“可用矩形列表”中有 1 个可用矩形（初始矩阵），基本上我们只需要存储空闲矩形的高度和重量以及初始矩阵的左上角位置
  2. 选择要添加的随机矩形 =“toAdd”，将其从“添加矩形列表”中删除
  3. 随机选择等于或大于“toAdd”=“available”的空闲可用矩形，将其从“可用矩形列表”中删除，如果没有可用矩形转到步骤2
  4. 选择“可用”上的随机位置以在其上添加“toAdd”矩形
  5. 剪切“可用”矩形以减去“toAdd”。此处可以应用不同的切割策略，但最后您最多可以获得 4 个新的可用矩形
  6. 将新的可用矩形添加到“可用矩形列表”
  7. 转到第 2 步

算法不是最优的，因为在理想世界中，我们应该在第 6 步连接 2 个可用的邻居。

于 2012-06-29T17:40:13.137 回答
1

以下方法：

  • 找出你的最小尺寸是多少。计算一个小于此尺寸但可多次放入您的盒子的尺寸。例如：最小尺寸为 7 厘米/英寸，盒子为 120 厘米/英寸。选择 120/20 = 6 厘米/英寸。我希望您的问题足够小，因为您会将所有可能的坐标存储在一个列表中。在这种情况下，我们有 20x20 = 400 个坐标。

  • 为保证不可能阻塞整个区域，请选择最小维度 (x,y) 大于或等于矩形最大维度的双四倍的矩阵（例如，矩形的最大长度 = 8，x 和 y必须至少有 32)，并且矩阵的整个区域至少有一个区域是所有插入元素的两倍。

  • 放置选择：使用随机数发生器随机选择一个坐标。将矩形放在给定坐标上，并选择随机方向。尝试将矩形设置到框中，如果它不适合首先，旋转它。如果仍然不合适，请尝试下一个坐标。

  • 如果它最终适合，请从列表中删除与矩形重叠的所有坐标。因此，您只为其他矩形选择有效坐标。

  • 随机化：不要使用线性同余生成器（不幸的是，它是大多数编程语言的任务标准）。它们具有不良的多维特征。使用安全随机、硬件生成器或已知良好的生成器，例如 MersenneTwister。

于 2012-06-29T17:21:15.393 回答
0

This problem is pretty much exactly the same as roguelike dungeon map generation. There are a ton of approaches to this with different looks.

I would suggest the BSP tree approach from here ( the steps are simple ): http://www.futuregadgetlab.com/proceduraldungeon/

于 2012-06-29T20:43:54.050 回答
0

您可以简化计算并从旋转的一些限制开始，然后您可以使用 kd-tree。一个很好的例子是 jquery masonry 插件或 jquery treemap 算法。这个想法是在某处放置一个矩形，并将 x 指向树的左侧，y 指向树的右侧。

于 2012-06-29T22:54:29.767 回答