algorithm - 如何在二维数组上随机生成布局？

Question

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

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

完成后的数组应该是这样的:(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 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 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

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

有没有更好的方法来解决这个问题，不会对放置后面的矩形产生如此大的问题？

Answer 1

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

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

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