Jan 1, 2014 2d, Np-Hard, Heuristic

Two-Dimensional Bin Packing

Two-dimensional bin packing turns out to be quite a pickle.

I was introduced to the problem as a 13 year old. My Dad’s friend, Keith, noticed I was taking a knack to programming, and wanted to see if I could help him. Keith was (and still is) a carpenter.

Keith wanted me to write a program where he could input a list of shapes, and the program would figure out the best way to cut a board of wood into those shapes, while minimizing scrap wood. Seems reasonable.

My 13 year old mind quickly exploded… I couldn’t figure out one simple, obvious way to do it. Eventually I gave up, to my ego’s dismay (and Keith’s disappointment!).

Seventeen years later, and I still struggle with the problem. This time though, I want to arrange sprites on a spritesheet in an optimal way. This is useful for game programming, but also web development.

Spritesheet Example

Luckily, I have many decades of computer science to back me up: the problem is NP-hard! This means that there is no clever solution that works quickly and finds the best answer. If you want the best answer, expect to wait a long time. Otherwise, you’ll have to come up with a good enough solution (i.e., a heuristic).

There are plenty of examples on the web, in different languages – but what fun is that? Let’s build our own, in JavaScript.

Requirements

First, let’s simplify things a bit, since we know we’re doing this for game/web programming.

Don’t worry about rotation
Don’t worry about shapes other than rectangles
Don’t worry about fitting the sprites into a bin of a known size (we’ll just do our best, then calculate the resulting bin after we’re done)
Don’t worry about multiple bins to choose from
Try to make the bin a square (due to graphics cards liking square images)
Make the algorithm adjustable, based on how much time we want to search the universe for good solutions (i.e., something quick-but-messy during development, and slow-but-optimial for production)

So, the input should be a list of rectangle dimensions, how much time we’re willing to spend on searching, and the output should be a way to arrange the rectangles nicely.

Basic Algorithm

There is no right way – I came up with the following algorithm by thinking through how I would solve the problem physically.

Sort the rectangles from biggest to smallest
Take the biggest rectangle, and put it in the center – this is where we’ll start
Take the next couple biggest rectangle and move them around the edges until they seem to fit snuggly
Repeat step 3 until we run out of rectangles

Why move from biggest to smallest? I figure the big rectangles are the hardest to place, since they take up the most room. Might as well get them out of the way first. Also, placing big rectangles means creating big wasteful areas – that small rectangles can fit in later.

Ok – so how do we move rectangles around the edges? I don’t want to go pixel by pixel, that seems really slow. Well, the way I figure it, the best spots are when edges line up. How can we quickly figure out locations where edges will match up? By thinking about it in terms of corners.

When placing a rectangle down, we can enumerate through touching corners of the rectangle with the corners of the shape on the table. If one rectangle is on the table (dark red), that means we’ll have twelve positions:

When we attempt to place a rectangle on the table, we need to try each of the four corners of the rectangle against each available corner on the table.

After we find a good location, we just need to add the new corners to the list of corners to try, so the next rectangle can try more spots.

Quite a Tree We’ve Built

And, just like that, we’ve built a tree space. Since most rectangles will have multiple options, we could (in theory) try each option. After each decision, we’ll have a list of further decisions. If we explore the entire decision tree, and we have some sort of “scoring” function that can tell what solutions are better than others (by, say, favoring squares, and favoring smaller total areas), then we could exhaustively find the best answer!

Sounds great! Until the NP-hardness punches you in the face. Even with a few rectangles, the program becomes very slow. Over seven rectangles and you’ll be waiting forever. However, if you’ve ever built a heuristic, you know the next answer. Breadth-first searching with branch pruning.

Just like with Chess, it is too hard to exhaustively search for the best solution. Instead, we need to figure out a way to trim branches off the tree.

Well, that isn’t so hard either – if we already have a scoring function, then we can just score partial solutions, and choose to search down branches that look promising.

Scoring

What is a good scoring function? Well, we want small bins, so smaller area is good. Also, we need to favor squares. In the end, I settled on this:

score = pow(max(width, height), 2) * 10000 + width * height;

Basically, we calculate the area of the containing square. Smaller area is better. Tie-breakers go to placements with less actual area (via heavily weighting the square-area, and adding the actual-area).

As we walk the tree, we just need to keep in mind that lower scores are better.

Getting an Answer

One difference between Chess and this algorithm is that, for this, we need to finish! In Chess, we don’t have to run the simulation until checkmate for every move – we can end our search early, and just assume that checkmate is further down the tree. Not so with this algorithm.

We need to find complete solutions. One way to force this to happen is to basically have checkpoints. Search the tree for a little bit, find the best intermediate answer, then only look down that path going forward.

In the demo code, I do this by only adding three rectangles at a time. I grab the best solution I could find in the allotted time, and then ignore alternatives, and move forward, until all rectangles have been placed.

Demo

Click here to launch the demo!

Demo Screenshot

The buttons on the bottom left will generate different rectangles to play with. The “Next” button in the bottom right will place the next three rectangles. Click “Next” over and over until all the rectangles are placed.