How to do optimal rectange placement? (Changed to circles) [Complex]

[GamEditoPro]

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:

1. Players have islands:
   
2. Converting this islands to rectangles:
   
3. Optimally packing them
   

Is it possible to do such alghorithm, assuming that:

1. Islands and placement have not strict grid.
2. Islands are threated as 2D
3. There should be as little free space as possible
4. No strict limit on how many islands are there
5. Islands can be rotated, and not only by 90 degrees.

[treebee63]

Converting the shapes to rectangles:
You can take advantage of Roblox’s bounding box system.

1. Convert your island to a model (or spawn a bunch of parts to cover it then group it as a model)
2. Get the size and CFrame using Model:GetBoundingBox()

local CF, size = model:GetBoundingBox()
print("CFrame is", CF)
print("Size is", size)

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.

1. 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:

1. have the islands populate one corner of a giant box and run a 2d box packing algorithm on it.
   (Survey for 2-D packing algorithms)
   

2. 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)
   

Good luck!

[GamEditoPro]

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).

[GamEditoPro]

I think I have succed with making my own circle packing:


^{What it looks like when not sorted by size}

^{(Edit: 2 first circles wasn’t shown on video)}
But, it has some flaws:

1. If circles formed “triangle”, island can’t be spawned between them, even if it can theoretically fit.
2. There’s no defined bounds for placement.
   But result is good for my use case. Big thanks for idea!
   ^{(Also, if you want code, I can give you it in PM)}

[treebee63]

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.

@GamEditoPro

(Also, if you want code, I can give you it in PM)

Sure, if you’re willing to do so.

[GamEditoPro]

@treebee63

Simply create an invisible “ghost 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.