Codesnippets > Math

Bin Packing with MaxRects - very useful for texture packing in your apps

(1/2) > >>

Wampus:
MaxRects function - optimally pack many sprites/rectangles into an area

Attached is source code that demonstrates an implementation of the MaxRects algorithm in GLBasic. You'll find an example of its use to play with and the function itself in the file MaxRects.gbas. I used the study 'A Thousand Ways To Pack The Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing' by Jukka Jylänki as reference material.

The purpose of the MaxRects algorithm is to find an optimum way to pack many rectangles into another larger rectangle. Other algorithms exist but MaxRects is the best to use in most scenarios. I've also included the three most effective known heuristics for MaxRects in the code. I could add more but others are unlikely to find better solutions 99% of the time so I'm leaving them for now.

A well known use for MaxRects is packing sprites into an OpenGL sprite sheet for use in games. So, if you use Polyvector sprites this might be very handy. If all you need is a pre-packed sheet I recommend commerical tools like Texture Packer. They can use the same packing algorithm as MaxRects. They also tend to come with a ton of useful options for other aspects of sprite management. However, if you need your apps to pack sprites sheets on the fly, e.g. to adjust to different resolutions before running, then use this GLBasic code.

My code is a little crazy (just one large function) but its very fast. Below is a screenshot of the demonstration example. Red rectangles have been rotated and blue rectangles are in their original form.

How to use the MaxRects function

ok = MaxRects ( BinWidth, BinHeight, Textures[], rotate )

The array you put for Textures[] will contain the dimensions of the sprites/rectangles you want to pack together. The array should use this type:-

TYPE reclist
w      // width of rectangle
h      // height of rectangle
x      // x position
y      // y position
r      // 0 = normal, 1 = rotated 90 degrees
ENDTYPE

Before you send the array to be sorted you only need to define the width and height. Any information in x, y and r will be overwritten if a solution is found.

The rotate variable can be either FALSE = no rotation, or TRUE = rotation is allowed. If you use MaxRects to pack sprites into a sprite sheet for use with Polyvector commands then it makes sense to make use of rotation. If you're planning on using commands like DRAWANIM then it shouldn't be used.

BinWidth and BinHeight are the dimensions of the space you want to put the sprites/rectangles in. If you're creating sprite sheets for polyvector use make sure these are set to powers of 2 and keep in mind the maximum texture size for the platforms you're targeting, e.g. 1024x1024, 64x128, 2048x2048 are good - 36x1002 is bad.

The value returned to ok will be -1 if no solution could be found or, if the attempt was successful, ok will contain the amount of pixel area space that could be potentially cropped without losing anything. In practice cropping is rarely worth bothering with, so long as the sprites fit.

If successful every element in the Textures[] array will have x and y coordinates and rotation r values if rotation was allowed.

Hope someone finds this helpful.

bigsofty:
Haven't tried it yet but this is something I was wanting a while back but never got around to giving it a go.

One for the keeping!  :good:

Ruidesco:
Great work Wampus.

Am I the only one who got reminded of Qix upon seeing that screenshot? :P

bigsofty:
Actually I thought, hmmm, must be a way to use this to generate maps in a roguelike!  :S

Wampus:

--- Quote from: bigsofty on 2012-Apr-02 ---Actually I thought, hmmm, must be a way to use this to generate maps in a roguelike!  :S

--- End quote ---

MaxRects might come in handy as part of a larger map building routine. Could result in some odd map builds though, since the routine is only interested in fitting in the maximum number of rectangles into a space regardless of what the rectangles might represent.

Have you seen this dungeon map generator? http://donjon.bin.sh/d20/dungeon/ The PHP source code is available on the page. I adapted a similar approach and extended it for a game I'm working on called Robot Ninja Assassin.

I highly recommend you check out RogueBasin. It is a very useful resource indeed. Here are links to articles on map creation: http://roguebasin.roguelikedevelopment.org/index.php/Articles#Map

Navigation

[#] Next page

Go to full version