Rectangle filling puzzle

[Firestryke31]

Here's the situation: I have a large rectangle/square (say, 128px by 128px) and a bunch of little rectangles of semi-random dimensions (approx 16px by 14px, +/- a few). I need to fit these little ones into the big one as compactly as possible, maybe with some padding if I need it. I've seen this somewhere, but can't for the life of me remember what it was called.

For those that care, I'm rendering a font to a texture to use for the UI in a game using Freetype. Eventually for the release version I might pre-generate this info, but I will still need the algorithm for that...

I don't need spoonfeeding of the code, I'm more wanting something that describes the theory and what it's called.

[Combuster]

It's a difficult problem - http://en.wikipedia.org/wiki/Bin_packing_problem - one that can only be truly solved by trying all combinations as it is NP-hard.

I use a heuristical solution for one of my games where I pack 30 spritesheets into (currently) 6 by eliminating the transparent parts of the borders. The trick I use is to sort all sprites by decreasing (height, width) and then fill out the space left-to-right, and start a new row the moment you cant fit something on the right side. It works pretty fast (its n·log·n instead of the theoretical n!) and gives a decent approximation to the best solution (especially with a lot of similar-sized sprites), but it is not the best possible option.

If you just want to get the job done, you can always PM me. For the trolls among you: Visual Basic warning

[Firestryke31]

That sorting idea sounds good. It doesn't need to be perfect, I really only need the standard ASCII for now and I'd guess that 128x128 will be plenty for that (and if not nothing's stopping me from going with 256x256).

[JamesM]

Interactive 2D bin-packing algorithm in Javascript and <canvas>. This was linked on reddit a while back - is this what you saw?

It uses the n.log(n) algorithm as Combuster mentioned as far as I can tell from the alignment in each column.

[Combuster]

It's not nearly the same. I sort them and then put them in from left-to-right (since the heights are mostly the same you have little loss there) and when its full I start with the next row. Its a ton simpler than the java demo as it keeps track of all leftover holes, which gives you some headache over the data structures you need for that to do it efficiently: http://www.cs.uu.nl/docs/vakken/ga/slides5.pdf (if this is new for you, make sure you're stocked on coffee, cola, mate, or your own favourite source of caffeine )

[Firestryke31]

Well, since I decided to do it offline from the beginning I figure the texture generation speed isn't all that important to me right now. These are interesting, I love getting to try out these new things, especially when they'll actually be useful to me.