Bin Packing

roaminggamer · August 19, 2017, 2:41am

Hey folks. I’m working on this right now, but I thought it might be worth asking.

Has anyone here written a bin-packing algorithm in Corona before and if so, do you mind sharing.

Alternately, do you know of a bin packing algorithm that might work well in Corona?

For those who don’t know what this is, here is one of many examples:

http://codeincomplete.com/posts/bin-packing/

I’ll post back if I find a ready made solution out there.

roaminggamer · August 19, 2017, 2:46am

Because I know the size of my blocks I’m probably going to solve this using a heuristic-scan-line algorithm which is really a bit of a hack. However, I’m holding out hope that I will find or someone here knows of a new clean solution.

StarCrunch · August 19, 2017, 3:19am

I encourage you to find a non-hack. There’s a nice prize. :P (See also the bit on “Jurassics” here, e.g. “If any one of the Jurassics is tractable, wonder of wonders, all of them are. Better still: a cure for any one of them could easily be used to heal any of the others.”)

A couple in Löve2D: packer and Fudge (And yes, I’m sure those are deliberate.)

I have stb_truetype bound (and, uh, should eventually un-hide the plugin… gotta write docs!), which does use a rect packer… I guess I could expose that as well, but it’d be a pretty roundabout way to go and might be a long wait besides.

Is your data a tight fit, or could you use other means like Devil Squid’s quadtrees?

roaminggamer · August 19, 2017, 3:33am

Too late, I used a super-hack based on knowledge of bin sizes and some basic rules.

This is what I came up with (using SSK2of course):

-- ============================================================= -- Copyright Roaming Gamer, LLC. 2008-2017 (All Rights Reserved) -- ============================================================= -- main.lua -- ============================================================= -- ============================================================= io.output():setvbuf("no") display.setStatusBar(display.HiddenStatusBar) -- ============================================================= require "ssk2.loadSSK" \_G.ssk.init() -- ============================================================= -- Localizations -- ============================================================= -- Lua local mRand = math.random -- -- Common SSK Display Object Builders local newCircle = ssk.display.newCircle;local newRect = ssk.display.newRect local newImageRect = ssk.display.newImageRect;local newSprite = ssk.display.newSprite local quickLayers = ssk.display.quickLayers -- ============================================================= -- Find local stories -- ============================================================= local sizes = {} sizes[1] = { w = 425, h = 625 } sizes[2] = { w = 210, h = 310 } local blocks = { { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, { type = mRand(1,2) }, } local function algo() local curX = 0 local curY = 0 local col = 0 local row = 0 local lastType local bin = display.newGroup() bin.x = left bin.y = top for i = 1, #blocks do local fill = { mRand(), mRand(), mRand() } fill[mRand(1,3)] = 1 if( col == 0 ) then local bType = blocks[i].type local size = table.shallowCopy(sizes[bType]) local obj = newRect( bin, 0, 0, { w = size.w, h = size.h, fill = fill } ) obj.myType = bType obj.x = curX + obj.contentWidth/2 obj.y = curY + obj.contentHeight/2 col = col + 1 curX = obj.x + obj.contentWidth/2 + 5 if( bType == 1 ) then curY = curY else curY = obj.y end elseif( col == 1 ) then local last = bin[bin.numChildren] local bType = 2 local size = table.shallowCopy(sizes[bType]) if( last.myType == 1 ) then local obj = newRect( bin, 0, 0, { w = size.w, h = size.h, fill = fill } ) obj.myType = bType obj.x = curX + size.w/2 obj.y = curY + size.h/2 curY = obj.y + 5 + size.h row = 1 elseif( row == 0 ) then local obj = newRect( bin, 0, 0, { w = size.w, h = size.h, fill = fill } ) obj.myType = bType obj.x = curX + size.w/2 obj.y = curY curY = obj.y curX = obj.x + 5 + size.w/2 col = 2 row = 0 else local obj = newRect( bin, 0, 0, { w = size.w, h = size.h, fill = fill } ) obj.myType = bType obj.x = curX + size.w/2 obj.y = curY curY = obj.y + size.h/2 + 5 curX = 0 col = 0 row = 0 end elseif( col == 2 ) then local bType = 2 local size = table.shallowCopy(sizes[bType]) local obj = newRect( bin, 0, 0, { w = size.w, h = size.h, fill = fill } ) obj.myType = bType obj.x = curX + size.w/2 obj.y = curY curX = 0 curY = obj.y + 5 + size.h/2 col = 0 row = 0 end lastType = blocks[i].type end end algo()

Michael_Flad · August 19, 2017, 10:28am

For my sprite/font packer script I use this one http://blackpawn.com/texts/lightmaps/

I first collect all my images in a list and sort them by their area - not perfect and in theory with special rects with tiny width and huge heights and vice versa, there’s a chance it won’t find a rect even though a huge area is still unused, but in reality I never had such a situation. If required I just use additional pages and optionally grow the pages up to a limit (using the dumbest possible solution,i.e. a brute force grow + try again loop until the rects fit :)).

Edit: Just noticed the page linked above already had a link to the blackpawn page too

roaminggamer · August 19, 2017, 2:46am