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

Previous topic - Next topic

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.

[attachment deleted by admin]

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:
Cheers,

Ian.

"It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration."
(E. W. Dijkstra)

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
Cheers,

Ian.

"It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration."
(E. W. Dijkstra)

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

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

bigsofty

Wow, that's an amazing generator, it takes the procedural idea to a whole new level.

Thanks for the links Wampus!  :booze:
Cheers,

Ian.

"It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration."
(E. W. Dijkstra)

Kitty Hello

True genius!
I once required such a thing for a program packing stone blocks onto a train. I ended up with heating up the CPU and random permutations.

erico

Qix came to my mind right away when I saw the pic.

Quote from: Wampus on 2012-Apr-05
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.

:O my god! I can´t believe it! take it away from me please, I will probably waste the rest of my life generating dungeons!
It is awesome!

Marmor


Wampus

Fixed a bug with Best Area Fit when rotation was on. Some rectangles that should have been returned as rotated came back normal. Download updated.

Quote from: erico on 2012-Apr-13
Quote from: Wampus on 2012-Apr-05
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.

:O my god! I can´t believe it! take it away from me please, I will probably waste the rest of my life generating dungeons!
It is awesome!

LOL yeah its fun to watch. Can also inspire all sorts of projects :)