Hi guys. Today I finally finished biggest part of my building game, and now I need to do the rest one.
But while doing some game modifiers, I run into a problem where I need to pack player’s islands optimally and compact, like this:
Players have islands:
Converting this islands to rectangles:
Optimally packing them
Is it possible to do such alghorithm, assuming that:
Islands and placement have not strict grid.
Islands are threated as 2D
There should be as little free space as possible
No strict limit on how many islands are there
Islands can be rotated, and not only by 90 degrees.
Packing your shapes:
This is very complicated and niched. I don’t think anyone has implemented the an algorithm for it on Roblox so you’ll have to get creative and write your own.
Some pointers I could give:
I recommend to have constraints into the problem to simplify it a lot or you’re going to be stuck with very complicated math.
bounding boxes are snapped in 90 degree increments at first and cannot rotate after
Once you’ve simplified it you can use a couple of documented algorithms:
you can alternatively treat the rectangles as “circles” and run a circle packing algorithm (this special algorithm packs objects around a center point so it might be more useful)
(2D Circle Packing Algorithm Ported to C# - CodeProject)
Thanks for answer. I think it really will be more wise to use circle packing instead of rectangles, bc this allows more flexibility and easier. I’ll try to find some info about them, cuz link you provided makes smth like dynamic collissions between circles (if I understood code right).
Yes unfortunately I believe the packing problem is NP-Hard. You cannot get a perfect solution without brute forcing the values. In most applications the problem is solved through approximation, which isn’t always perfect, but can be very good.
I think your implementation is fine. The island COULD be squeezed closer but given how better solutions are much more complicated/computationally expensive this is a good approach.
Lastly, I forgot to include this in the solution, but you might run into a scenario with 3d islands where your bounding boxes don’t line up.
Simply create an invisible “ghost part” with no rotation and set it as the primary part of the model. Roblox will redraw the bounding box with its rotation aligned to the part.
I have already took care about that =) Setting Model pivot to smth removes need for that. And cuz players build islands themselves, I did it so islands are always aligned to CFrame.identity.