Jump to content
  • Advertisement
Sign in to follow this  

Sprite packing algorithm explained (with example code)

This topic is 732 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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.
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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!