Is there a simple way to separate randomly spawned squares?

Question

What I am currently doing is spawning some rooms which are basically just rectangles. What I want to do now is just to separate them so that they are not overlapping. I'm working on a small SDL based framework.

What I'm looking for is some simple algorithm or way that I can achieve this.

What I currently have is the following:

    static void SeparateRooms(Room& r1, Room& r2)
    {
        if ( utils::IsOverlapping(r1.GetRect(), r2.GetRect()) )
        {
            constexpr int moveIncrement{ 3 };

            if (r1.GetArea() > r2.GetArea())
            {
                const Vector2f smallToBigVector{ r1.GetPosition() - r2.GetPosition() };
                const Vector2f smallToBigNormalized{ smallToBigVector.Normalized() };

                r1.m_Rect.left += moveIncrement * smallToBigNormalized.x;
                r1.m_Rect.bottom += moveIncrement * smallToBigNormalized.y;
            }
            else
            {
                const Vector2f smallToBigVector{ r2.GetPosition() - r1.GetPosition() };
                const Vector2f smallToBigNormalized{ smallToBigVector.Normalized() };

                r2.m_Rect.left += moveIncrement * smallToBigNormalized.x;
                r2.m_Rect.bottom += moveIncrement * smallToBigNormalized.y;
            }
        }
    }

This works, but only when the rectangles are not surrounding another rectangle. Is there some tweak that I can do to make this work or another way I can approach the problem?

one of these may help [rectangle_overlap](https://stackoverflow.com/questions/9613123/random-placement-of-rectangles-with-no-overlaps) [game_dev rectangle_overlap](https://gamedev.stackexchange.com/questions/6730/how-to-randomly-place-rectangle-inside-a-larger-bounding-rectangle-without-inter) — White Wizard, Dec 31 '22 at 14:18
You could just not spawn them if they overlap previously spawned rooms. Repeat until you have enough rooms (of course make sure your map is big enough to fit them all, or you will loop forever). — Thomas, Dec 31 '22 at 14:57
@Thomas I could add a check that after 10 unsuccessful spawning attempts or more..they would not spawn. But that approach seems a bit "forceful" to me. I feel like there are better ways to do it, I just have to find them. — Alex, Dec 31 '22 at 14:59
I agree that it's not pretty, but it's by far the simplest way. Another approach is to start with one room that spans the entire map, then repeatedly split oversized rooms in two until you have enough rooms, and finally shrink each room by a random amount on each side. I've never tried this and it might create less random-looking maps, but you could give it a shot. — Thomas, Dec 31 '22 at 15:08
@Thomas I have something working right now. I just updated the above function a little and it does work. I'll update the answer when I'm sure it works properly or when I find a better way to do it. — Alex, Dec 31 '22 at 15:24
I assume you're calling the above function in a loop for each pair of rooms, until all overlaps are gone. But what if there's a large room squeezed in between two small ones? Won't it keep hopping back and forth forever? It seems hard to prove that this will always terminate. — Thomas, Dec 31 '22 at 15:27
@Thomas I just made it so that both rooms move. If it doesn't work I'll try implementing a small evade movement behavior for the rooms. That should be able to do the trick. So far I haven't seen any cases where it doesn't work, but I'm working on a little debug system now to make sure I'm not missing anything. — Alex, Dec 31 '22 at 15:50
Can you provide the number of rectangles you need to spawn and the limits on the coordinates? Are the coordinates integers or real numbers, and do you need the rectangles to be at least, say, `x` meters far apart from each other? — JamieNguyen, Dec 31 '22 at 17:52
@JamieNguyen well the number of rectangles and the bounding box are placeholders for now. They might change in the future and they might not but I don't see how that would affect the issue. To least provide you with some answers; right now I am using around 100 rectangles and a bounding box of around 1700 x 1000 pixels in an 850 x 500 window. — Alex, Dec 31 '22 at 20:18

Dave · Accepted Answer · 2023-01-01T11:53:31.093

Here's a different approach:

Start with a single rectangle the size of your bounding box.
To add a rectangle, take the largest rectangle, find its longest axis, and split it into 2 rectangles along that axis.
Rinse & repeat

If asymmetry is desirable, then when making the split you can pick a random point along the access (possibly avoiding some area near the endpoints to avoid very tiny rooms.

If you want rooms that aren't adjacent, shrink the rectangles towards their centers by some percentage.

If you want more empty space and asymmetry, generate extra rectangles but don't make them rooms.

If you want even more asymmetry, after shrinking the rooms, move them to a random location inside their pre-shrinkage boundaries.

If you wan't more variability in room size, in the second bullet, take a random room instead of the largest room.

Is there a simple way to separate randomly spawned squares?

1 Answers1