algorithm - Packing problem revisited

Question

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 :)

Answer 1

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).