重新审视包装问题
我正在开发一个游戏，我发现了一个必须解决的问题，以处理类似于包装问题的组件的布局。
总结一下我需要做的事情，假设我有一个类似于以下空间的空间：
+------------+---------+------------+
| 0 | 1 | 2 |
| | | |
| | | |
| | | |
+------------+---------+------------+
| 3 | 4 | 5 |
| | | |
| | | |
+------------+---------+------------+
| 6 | 7 | 8 |
| | | |
| | | |
| | | |
+------------+---------+------------+
其中每个角单元为 4x4，而中心单元为 3x3（因此其余单元为 3x4 和 4x3）。然后，我将一组元素放置在这些块内，这些块的尺寸可以从 1x1 到 3x3 不等（我认为还不需要任何 4x4，但它不应该改变任何东西）。当然，这些元素不能跨越界限，必须完全位于一个街区内。
哪一种是分配它们的最佳方式？假设如果没有必要，我不希望将它们全部粘在一起（例如，如果周围有足够的空间将它们分开，则不要将两个元素放置在一起）。我正在寻找一个简单的算法，也是因为情况非常有限。
额外问题：假设除了这 9 个（也许其他 3-4 个）之外还有其他块，与新块相比，我如何优先考虑这些块？ （我的意思是在达到填充阈值之前不使用附加块）..
当然我正在寻找总体思路，没有实现:)
I'm developing a game and I found a problem that I have to solve to handle the layout of a component which resembles me a packing problem.
To summarize what I need to do suppose I've got a space similar to the following one:
+------------+---------+------------+
| 0 | 1 | 2 |
| | | |
| | | |
| | | |
+------------+---------+------------+
| 3 | 4 | 5 |
| | | |
| | | |
+------------+---------+------------+
| 6 | 7 | 8 |
| | | |
| | | |
| | | |
+------------+---------+------------+
in which every corner cell is 4x4 while central one is 3x3 (so that remaining ones are 3x4 and 4x3). Then I have a set of elements to place inside these blocks that can vary from 1x1 to 3x3 (I don't think any 4x4 is needed yet but it shouldn't change anything). Of course these elements cannot cross the lines and must lay entirely within one single block.
Which could be the best way to allocate them? Assuming that I prefer not to have them all stickied together if is not necessary (eg. do not place two elements together if there's enough room around to place them apart). I'm looking for a simple algorithm, also because the situation is quite limited..
Bonus question: assuming other blocks in addition to these 9 (maybe other 3-4) how could I prioritize these compared to the new ones? (I mean just doesn't use the additional block until a fill threshold has been reached)..
Of course I'm looking for the general idea, no implementation :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这个 2D Bin Packing 问题看起来像是 NP 硬。
以下是您的几个选择：
暴力或更好的分支绑定。无法扩展（根本！），但会为您找到最佳解决方案（也许在我们有生之年找不到）。
确定性算法：对最大尺寸或最大边上的块进行排序，并逐一遍历该列表，并为其分配最佳的剩余位置。这将很快完成，但解决方案可能远非最佳（或可行）。 这是一张很好的图片，展示了可能出错的示例。但是如果您想保持简单，那就是正确的方法。
元启发式，从确定性算法的结果开始。这将在合理的时间内给你一个非常好的结果，比人类想出的更好。根据您投入的时间和问题的难度，它可能是也可能不是最佳解决方案。有几个库，例如 Drools Planner（开源 java）。
This 2D Bin Packing problem looks like it's NP hard.
Here are a couple of your options:
Brute force or better yet branch and bound. Doesn't scale (at all!), but will find you the optimal solution (not in our lifetime maybe).
Deterministic algorithm: sort the blocks on largest size or largest side and go through that list one by one and assign it the best remaining spot. That will finish very fast, but the solution can be far from optimal (or feasible). Here's a nice picture showing an example what can go wrong. But if you want to keep it simple, that's the way to go.
Meta-heuristics, starting from the result of a deterministic algorithm. This will give you a very good result in reasonable time, better than what humans come up with. Depending on how much time you give it and the difficulty of the problem it might or might not be the optimal solution. There are a couple of libraries out there, such as Drools Planner (open source java).