Sprite packing algorithm explained (with example code)

For discussions about game development that does not fit in any of the other topics.
Post Reply
User avatar
a_bertrand
Posts: 1537
Joined: Mon Feb 25, 2013 1:46 pm

Sprite packing algorithm explained (with example code)

Post by a_bertrand »

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 ;)
Creator of Dot World Maker
Mad programmer and annoying composer
User avatar
Jackolantern
Posts: 10893
Joined: Wed Jul 01, 2009 11:00 pm

Re: Sprite packing algorithm explained (with example code)

Post by Jackolantern »

Nice! I honestly never gave this algorithm much of a thought and just used sprite sheet packing features of utilities. But this seems to be quite a clean, logic and efficient algorithm which always warms the corners of my heart. 8-)
The indelible lord of tl;dr
User avatar
a_bertrand
Posts: 1537
Joined: Mon Feb 25, 2013 1:46 pm

Re: Sprite packing algorithm explained (with example code)

Post by a_bertrand »

Hahaha Jacko, good one ;) Indeed you may not need it so much... But it could actually be useful. I mean till I had to make it for my sprite editor I never had the need for it and suddenly I was needing it without knowing how to solve the issue. Wanted just to share the knowledge ;)
Creator of Dot World Maker
Mad programmer and annoying composer
User avatar
Jackolantern
Posts: 10893
Joined: Wed Jul 01, 2009 11:00 pm

Re: Sprite packing algorithm explained (with example code)

Post by Jackolantern »

It is definitely a nice thing to have recorded here. That is the kind of thing that someone may find through Google and use, even if they don't ever register to say thanks.
The indelible lord of tl;dr
Post Reply

Return to “General Development”