How is 2D bin packing achieved programmatically?

I Googled “bin packing code” and this was my first hit:

Here’s a summary: build a binary tree. Each branch in the tree contains a sprite. Each leaf node represents available space. Initially the tree has just the root node, which represents all available space. To add a sprite to the tree, search the tree for an unoccupied (leaf) node big enough to hold the sprite. Turn that node from a leaf into a branch by setting the sprite as the node’s occupant and giving the node two children. One child represents the remaining space to the right of the sprite; the other represents the remaining space below the sprite and the first child.

The article I linked above explains this much more fully, with diagrams and JavaScript code. It also explains how to dynamically grow the sprite sheet rather than choosing a fixed size in advance.

Leave a Comment