Hello everyone. I have a problem and after hours of research on the internet I haven’t been able to solve it satisfactorily.
Situation:
I have a random number of rectangles of different sizes (2D). These should now be distributed randomly but not overlap.
Randomly searching for a position and seeing if it overlaps is not an option, there should be no cases where you unluckly spend hours searching for a position.
Is there any effective solution for this?
I’ve already searched for rectangle packing on Google, but the examples sorting the rectangles after size.
Here is an example image of what I mean
I don’t have a good solution, but I came up with three approaches to the problem.
- Place the rectangles neatly in a grid and move them around to make the placement appear more random. This method guarantees that you can fit a given number of rectangles in the area.
- Place the rectangles randomly and let them overlap. Then push the rectangles apart to prevent overlap. This method can make the rectangles clumped up and it doesn’t guarantee that they can all fit within the area.
- Keep track of the free area (empty rectangles) and place the colored rectangles randomly inside the empty rectangles. Every time a colored rectangle is placed, it divides the empty rectangle into 4 new empty rectangles that have some overlap. This method doesn’t guarantee that a given number of colored rectangles can fit within the area, and it’s probably difficult to get an even distribution.
What about this, Basic BSP Dungeon generation - RogueBasin, just stop before the connections are made.
2 Likes
fun fact, i already found this hours ago…
after hours of trying, I’ve now managed to get it to work in godot.
I don’t know why, but most of the time the objects stick to each other and/or to the edges
but maybe thats because of the small test area…
anyway, thanks for your time!
1 Like
Nice.
I think after you do the BPS, get the partitions and use those as like ‘containers’ for a potential rectangle within each, but you wouldn’t want to make the rectangle that size exactly. You’ll want to make a smaller rectangle by reducing the extents of each side of the partition to some random value to define the new shape.
I would make sure when you split each partition that you choose a different axis, x or y, each time and let the split happen at a wider range, and then even if you end up with some smaller or thinner partitions, you just ignore those when deciding which partitions to allow a rectangle to be drawn in, leaving some nice gaps.
This is what I did.
The split with each room is always done randomly on the x or y axis.
At the moment it only splits as long as there is at least one room in the resulting rooms with space for the largest room and one room for the smallest room. Then he randomly selects one with the minimum size that the big room should have, keeps it and is no longer split, all others continue to be split with the next smaller room size. This also return rooms of different sizes
2 Likes
Ah ok, looked like each colored rectangle place fit exactly to the size of the BPS region.
