I couldn't find a pure Lua bin packing library, so here's Mike Popoloski's MIT-licensed BinPacker.cs from SharpFont ported to Lua.

**What's a bin packer?**

This is an implementation of one algorithm (MAXRECTS) used to solve rectangle bin packing in 2D.

Think of automatically creating an e.g. 2048x2048 spritesheet. If you know all the tiles you need to put in it are 16x16, maybe that's not a very hard problem to solve.

But what if your tiles aren't all the same size? What if they might not even all fit in one spritesheet (bin)?

You need a 2D bin packer, my friend.

Bin packing is an NP-complete problem. That is, mathematically, there is no efficient way to get a perfect solution. Instead you have to rely on algorithms that seem to do a decent job fast.

**How2use**

Code: Select all

```
local binpack_new = require('binpack')
local bp = binpack_new(2048, 2048)
local rect1 = bp:insert(32, 64)
-- (rect1 has .x, .y, .w, .h, :clone(), :contains(rect), .right, .bottom)
print('rect1:', rect1) -- rect1: {x=0,y=0,w=32,h=64}
local rect2 = bp:insert(100, 101)
print('rect2:', rect2) -- rect2: {x=0,y=64,w=100,h=101}
print('\n20 250x200 rects: '); for i = 1,20 do print(bp:insert(250, 200)) end
print('\nClearing; changing binpack instance to 1024x1024')
bp:clear(1024, 1024) -- you MUST provide w,h again
print('10 370x430 rects in 1024x1024:'); for i = 1,10 do print(bp:insert(370, 430)) end
-- you can call binpack_new(w, h) again if you want 2 binpackers simultaneously. it's not an issue.
```

**Example output**

Code: Select all

```
pink:utils leaf$ lua
Lua 5.3.4 Copyright (C) 1994-2017 Lua.org, PUC-Rio
> dofile('./binpack_example.lua')
rect1: {x=0,y=0,w=32,h=64}
rect2: {x=0,y=64,w=100,h=101}
20 250x200 rects:
{x=0,y=165,w=250,h=200}
{x=0,y=365,w=250,h=200}
{x=0,y=565,w=250,h=200}
{x=0,y=765,w=250,h=200}
{x=0,y=965,w=250,h=200}
{x=0,y=1165,w=250,h=200}
{x=0,y=1365,w=250,h=200}
{x=0,y=1565,w=250,h=200}
{x=0,y=1765,w=250,h=200}
{x=250,y=0,w=250,h=200}
{x=500,y=0,w=250,h=200}
{x=750,y=0,w=250,h=200}
{x=1000,y=0,w=250,h=200}
{x=1250,y=0,w=250,h=200}
{x=1500,y=0,w=250,h=200}
{x=1750,y=0,w=250,h=200}
{x=250,y=200,w=250,h=200}
{x=500,y=200,w=250,h=200}
{x=750,y=200,w=250,h=200}
{x=1000,y=200,w=250,h=200}
Clearing; changing binpack instance to 1024x1024
10 370x430 rects in 1024x1024:
{x=0,y=0,w=370,h=430}
{x=0,y=430,w=370,h=430}
{x=370,y=0,w=370,h=430}
{x=370,y=430,w=370,h=430}
nil
nil
nil
nil
nil
nil
> ^D
pink:utils leaf$ luajit
LuaJIT 2.1.0-beta3 -- Copyright (C) 2005-2017 Mike Pall. http://luajit.org/
JIT: ON SSE2 SSE3 SSE4.1 BMI2 fold cse dce fwd dse narrow loop abc sink fuse
> dofile('./binpack_example.lua')
rect1: {x=0,y=0,w=32,h=64}
rect2: {x=0,y=64,w=100,h=101}
20 250x200 rects:
{x=0,y=165,w=250,h=200}
{x=0,y=365,w=250,h=200}
{x=0,y=565,w=250,h=200}
{x=0,y=765,w=250,h=200}
{x=0,y=965,w=250,h=200}
{x=0,y=1165,w=250,h=200}
{x=0,y=1365,w=250,h=200}
{x=0,y=1565,w=250,h=200}
{x=0,y=1765,w=250,h=200}
{x=250,y=0,w=250,h=200}
{x=500,y=0,w=250,h=200}
{x=750,y=0,w=250,h=200}
{x=1000,y=0,w=250,h=200}
{x=1250,y=0,w=250,h=200}
{x=1500,y=0,w=250,h=200}
{x=1750,y=0,w=250,h=200}
{x=250,y=200,w=250,h=200}
{x=500,y=200,w=250,h=200}
{x=750,y=200,w=250,h=200}
{x=1000,y=200,w=250,h=200}
Clearing; changing binpack instance to 1024x1024
10 370x430 rects in 1024x1024:
{x=0,y=0,w=370,h=430}
{x=0,y=430,w=370,h=430}
{x=370,y=0,w=370,h=430}
{x=370,y=430,w=370,h=430}
nil
nil
nil
nil
nil
nil
> ^D
```

**The codez**

binpack.lua: https://gist.github.com/leafi/c39489b97 ... b3c476df40

It's pretty easy to use. Read the big ol' comment block at the start of binpack.lua; it has a usage example of the three main functions & details of what they return.

binpack.lua contains its own implementation of a 2D rectangle. Swap it out if you want, or just get the data you want from the .x, .y, .w, .h fields of the returned table from binpack_instance:insert(w,h).

*When the bin is full, bin:insert(w, h) returns nil instead of a rectangle.***Limitations**

Some bin packing algorithms support rotating the rectangles to make them fit better. This doesn't.

It doesn't support dynamically growing the 'spritesheet' either. You state the lengths up-front.

Don't pass in negative or 0 for any widths or heights. It doesn't make sense and something bad will happen.

If you pass in floating point numbers, they will be coerced into integers. You can change this if you really want.

If your Lua environment is Lua 5.3, you should be able to use up to 64-bit integers for widths and heights (but why??). If not (e.g. LuaJIT in LOVE), avoid going above about 52-bit integers (< QUITE BIG NUMBER). IIRC that's the max you can have an integer before the 64-bit floating point numbers Lua uses cannot guarantee precise representation.

**License**

Just like the file says, this is MIT licensed. It was based on Mike Popoloski's MIT-licensed https://github.com/MikePopoloski/SharpF ... nPacker.cs, and uses the MAXRECTS algorithm developed by Jukka Jylänki http://clb.demon.fi/files/RectangleBinPack.pdf.

**Now what?**

Any questions/mistakes here, please tell me. I'm going to be using this myself so it'd be nice if it was actually right.