装箱问题再探讨

3

我正在开发一个游戏,遇到了一个问题需要解决,这个问题涉及到处理类似于装箱问题的组件布局。

简要概括我需要做的是,假设我有一个类似以下空间的空间:

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

这是一个每个角落单元格为4x4而中心单元格为3x3的方格(所以其余单元格为3x4或4x3)。然后我有一组要放置在这些块内的元素,这些元素的大小可以从1x1到3x3不等(我认为还不需要任何4x4,但这不应该改变任何事情)。当然,这些元素不能跨越线条,必须完全位于一个单独的块内。

哪种方式最好分配它们?假设我不想让它们都黏在一起,如果没有必要的话(例如,如果周围有足够的空间将它们分开,则不要将两个元素放在一起)。我正在寻找一个简单的算法,也因为情况相当有限..

附加问题:假设除了这9个块之外还有其他块(可能还有其他3-4个),如何将它们与新块进行优先排序?(我的意思是,在填充阈值达到之前,不使用其他块)。

当然,我只是寻找一般想法,不需要具体实现 :)


如果旋转元素可以产生更好的结果,那么是否允许/可取? - Jon
不行,实际上是不允许的。如果要放置的元素是2x3,则必须按照这种方式放置,而不是3x2。 - Jack
方块类型(1x1,2x2,3x3,以及可能的4x4)的概率分布是什么样子?最优解取决于此。因此,是否需要考虑4x4方块确实会影响最优解。 - Flinsch
我有一组固定的元素,但并不是所有元素都会放置在布局中。为了让您理解:它们是城市的建筑物,而这个布局是城市的布局。当然,我知道每个可用建筑物的清单,但不知道哪些建筑物将位于特定的城市中(因为这取决于玩家在那里建造什么)。 - Jack
1个回答

7

这个二维装箱问题看起来像是NP难问题

以下是几种解决方案:

  • 暴力搜索或分支定界。这种方法不可扩展(完全不行!),但可以找到最优解(也许在我们的有生之年内无法找到)。

  • 确定性算法:按照块的最大尺寸或最大边排序,然后逐个遍历该列表并为其分配最佳剩余空间。 这将非常快速地完成,但解决方案可能远非最优(或可行)。这里有一张很好的图片,展示了可能出现的问题。 但如果您想保持简单,那就这样做。

  • 元启发式算法,从确定性算法的结果开始。这将在合理的时间内给出非常好的结果,比人类提出的更好。 根据您给它的时间和问题的难度,它可能是最优解,也可能不是。 有一些库可供使用,例如Drools Planner(开源Java)。


在奖励问题中:将基本块建模为“硬约束”,将奖励块建模为“软约束”。 - Geoffrey De Smet
你能更新链接到“这里有一张漂亮的图片展示了一个可能出错的例子”吗? - tommy.carstensen
这对我正在解决的乐高组装问题非常相关。我正在用更大的砖块和板条替换1x1的砖块和板条,以降低成本。感谢这个很好的例子! - tommy.carstensen

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接