Sprite packing algorithm explained (with example code)

[a_bertrand]

While working on my engine ( https://www.dotworldmaker.com ) I was looking for some way to pack sprites together on a single image. Ideally while saving as much space as possible, without overlap of course and with maybe a little space between the sprites. I was needing this code in Javascript due to the pixel editor included in the engine and this is what I came with. Feel free to use it / share it.

This algorithm can be used to pack sprites into a sprite sheet or to move boxes around to try to minimize the space needed for them. The boxes are not all the same size (otherwise clearly a grid would be the smartest),
and we don't know the resulting space. Between the sprite a little space is kept to avoid to let them touch.

https://jsfiddle.net/jLchftot/

To see how it works I made it so that you can run the code step by step by pressing the "Next Step" button and you will see the algorithm pack the sprites once by one.

For how the logic works:
1) Sort all the boxes based on their height
2) Place a first box on the top left corner
3) We store a max width and max height
4) We pick up the next box and try to pack it somewhere within the max width / max height boundaries
5) If we cannot let's try to pack it on the same current row (the rule state that if the width is smaller than the height then we can. If we cannot then we move on the next row and therefore increase the total resulting height.
6) Re-calculate the max width / max height
7) Go back to step 4 till we placed all the boxes

There is multiple algorithms to pack things together without overlapping them. I just picked one way which is not all that complex and as I don't have too many boxes to pack it is still fast enough.

The code is commented so you should be able to understand what each piece is doing.

Comments / discussions are of course welcome

[mattstyles]

I normally use spritesheet-js, not sure if yours differs in functionality, but its always good to have alternatives/competition.

I think I've heard of a couple of peeps using shoebox as well.

[a_bertrand]

Thanks mattstyle, I'm not talking about pre-made tools, but more to have an algorithm which can do it for you and you can include in your project. Of course I could extract the needed pieces from spritesheet-js but... it seems to use way too many dependencies for this usage of mine.

[stay]

This is cool.  Simple and effective.  You're right - sometimes you need to do this on the fly in your project, not in a separate tool.  I recently ran into the case where I wanted the benefits of a packed spritesheet with images I was generating algorithmically, so a traditional standalone spritesheet tool (TexturePacker is my favorite) was not going to help.  Thanks for sharing this!

[a_bertrand]

No problem  Hope to have soon more relatively simple things I can share with you guys.