Block layout algorithm

Question

I'm looking for help with improving an algorithm for placing blocks of odd shapes. My problem domain is odd, but the best analogy for my blocks is Tetris pieces, except that they can have more than four pieces. The blocks still are composed of only right angles, but they can be long and winding, they can branch, etc.

I'm trying to arrange multiple large arbitrarily shaped blocks in minimal space (I know, a bin-packing problem) but my current solution looks ugly. I'm basically placing one, then brute forcing the rest by trying to place them at the origin of my grid and then slowly pushing them in different directions until they don't collide anymore. It's not slow, but it doesn't make any attempt to fit pieces nicely so they don't waste overall space.

The only thing I can think of trying is ordering the blocks by size, placing the largest first, then fitting the smallest in at the end into any holes remaining. But there are certainly ways that can backfire.

Are there any heuristics or approximation algorithms that can help me here?

The results would look something like the following:

Also, perhaps my gravatar gives away that this is Mega Man related...

Dosh

Your image seems to imply that you want space between the blocks. Is that true? – Forgo

@Andrew Yes I will, but I have a gut feeling that it won't affect the algorithm. I could just pretend the blocks are thicker by 1 unit on all sides. – Dosh

Answer 1

This (polyomino shape-packing) generally seems to be a nontrivial math problem, and I'll point you to the expertise of some others who have worked on it. This guy has a bunch of polyomino examples on his website where others can submit solutions. He also has solver software in Java:

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html.

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

There are also some algorithms written for this by Stephen Montgomery-Smith, which seem to be more comprehensive than the above (it solved some problems that weren't solvable with that) eventually made it into an xscreensaver (solves in real-time and cool to watch!). The following screenshot, from the screensaver, only shows shapes up to pentominoes, but it works on general shapes with general containers.

http://www.math.missouri.edu/~stephen/software/

I am unsure if either of these software approximates the best fit of polyominoes allowing for holes. But it's definitely 'decidable' this way, in the sense that you could certainly insert extra 1x1 polyominoes into your solution and see if it can find a particular result that fits, then remove the 1x1 pieces to get the result.

For your application, it might be more efficient to work backwards. All of these algorithms have complexity in the number of unit cells in each block. A good way to lay out your blocks would be to think of them as "subdivisions" in larger cells, so that a 3x3 square in your block corresponds to a 1x1 square in a rescaled version. Then, pad the blocks with empty space so they all consist of the larger blocks, run the algorithm, and strip away the extra space. Not only will this be much faster to execute, but it will also generate the space between blocks that you require.

Forgo

Answer 2

Interesting problem.

Define a potential field, so every unit cell has gravitational attraction for every other cell. Plus there's a hard constraint on rigid relationship between neighbor cells. Optionally tack on a repulsive force, perhaps based on distance cubed. That way distant blocks will be attracted to one another until they encounter a region that prevents them from touching each other.

Having defined such a field, it is straightforward to let each block find its local gradient and slide smoothly down it.

Local optima are possible. Re-run several times with different starting positions. You'll want to define an objective function which can rank order the competing proposed solutions.

You can also momentarily insert a repulsive field at some random location, to shake blocks out of a local optimum.

Spillar

This is an interesting idea, especially since it's applicable to shapes more general than polyominos – Spinoff