Sign in to follow this  
a_bertrand

Sprite packing algorithm explained (with example code)

Recommended Posts

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 ;)

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.