Rectangle Packing

Currently I’m working to get our game framework ready to be fully productive. Build in haxe, behind the scenes it will be an entity system. I’m going to write more about it in an upcoming post sometime later. If you are curious, read more here: T=Machine and Tom Davies. These two posts are the main reason why I started building my own entity system in haxe.

But let’s get to the rectangles… One of the major problems when developing mobile games is asset management. There are so many different devices with different screen resolutions. So how to handle all the different graphics? Use high-res images and scale the whole game down? Use medium-res images and do upscaling? None of these methods seem to be perfect. Thats where Flash comes in! Flash’s vector capabilities are simply awesome. And since all our Graphics are 100% handdrawn in Flash this is the way to go.

The two biggest benefits:
-Small app filesize compared to apps storing whole bitmap spritesheets
-easy up- and downscaling of graphics

But using vectors in Flash is so damn slow, you think? That’s right. But the vectors are only the base. The framework has a Stage3D renderer which is pretty fast for mobile games. Maybe not 100% on par with native code, but almost. But when using Stage3D you have to work with Bitmaps. So creating bitmaps at runtime from vector graphics is the goal. For best performance we are creating one (or more) big Textures, also known as Texture Atlas, and upload them to the GPU.

So workflow is basically:
1. Calculate scaling
2. Scale all vector assets
3. Get a list of scaled sizes as rectangles
4. Pack all rectangles as tight as possible on the textures
5. Draw the assets at their target positions

Packing rectangles is not that easy ;) But Ville Koskela already wrote a decent rectangle packer in AS3. So before tinkering myself, i ported his packer to haxe. Usage ist simple:

First create an instance of the packer:

Afterwards you can add rectangles to the packer. All you need is the width and height of the rectangle and an id. You need this id to retrieve the coordinates of rectangle after packing.

After all rectangles are in, simply pack them:

Now you can get target coordinates of the packed rect with:

And that’s all. Happy creating Texture Atlasses!

When the whole Texture Atlas Creator is finished i’m going to write another blogpost and push the source to github. I hope to finish it in the next couple of days. Meanwhile you can download the Texture Packer Class (simple example included) RectanglePacker.

Tagged with: , ,
Posted in Programming, Sourcecode

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>