Jump to content

Sprite packing algorithm explained (with example code)


a_bertrand
 Share

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

Link to comment
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.

Link to comment
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!

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...