Sign in to follow this  
bertrand_a

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.
 
 
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

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