Separation steering algorithm for separationg set of Rectangles

Question

In few last days trying to implement TinyKeep's dungeon generation algorithm myself.

Link to TinyKeep's dungeon generation algorithm

I don't understand it perfectly by 100%, because of it here am I :)

Firstly I generated set of rooms in circle Going for each room in set. Pick it and going with another for loop again in set to compare every room intersection.

If room intersects, I added force, in which I will be apply separation. After that nested loop ended, I move current room, from first loop, according to that force vector. And so on. It happening until every room is not overlapped with others.

Also I picked center(Middle) point of rects ( x+width/2f, y+height/2f) to calculate that force vector

If vector is normalized, then rooms tighly packed, but if no - rooms have much space between them...

I wanna just recreate and understand TinyKeep's algorithm, but results not the same...

Also I getting weird results, then tall/wide rooms or always going in corners, tall go upper-left corner of map, wide - bottom-right corner. And all sometimes have overall diagonal separate direction

// Main method
private void Separate()
        {
            do
            {
                for (int i = 0; i < rooms.Count; i++)
                {
                    Vector2 force = Vector2.zero;
                    int overlapCounter = 0;

                    for (int j = 0; j < rooms.Count; j++)
                    {
                        if (i == j) continue;

                        if (!rooms[i].IsOverlapped(rooms[j])) continue;

                        force += rooms[j].Middle - rooms[i].Middle;
                        overlapCounter++;
                    }

                    if (overlapCounter == 0) continue;

                    force /= overlapCounter;
                    force.Normalize();
                    force *= -1f;

                    rooms[i].Move(force);
                }

            } while (IsAnyRoomOverlapped());

            StopTimer(true);
        }

// Room.Move()
public void Move(Vector2 move)
        {
            x += Mathf.CeilToInt(move.x)* TILE_SIZE;
            y += Mathf.CeilToInt(move.y)* TILE_SIZE;
        }

// Constructor
public Dungeon(int roomAmount, int seed,float radius)
        {
            StartTimer();

            this.roomAmount = roomAmount;
            this.radius = radius;
            Seed = seed;

            InitializeRandom();
            PopulateDungeonWithRooms();
        }

Answer 1

While trying to figure out how solve this problem I read some questions and look their source code. I find that they not only move room after every overlapped neighbour found but also move neighbour in other direction!

What about directional behaviour of separation? It's my mistake or misunderstanding of rounding to integer

What about perfomance? Generating 512 rooms inside circle with radius of 128 units using normal distribution give 1100 ms

Now, code looks like:

private void SeparateRooms()
        {
            do
            {
                for (int current = 0; current < rooms.Count; current++)
                {
                    for (int other = 0; other < rooms.Count; other++)
                    {
                        if (current == other || !rooms[current].IsOverlapping(rooms[other])) continue;

                        var direction = (rooms[other].Middle - rooms[current].Middle).normalized;

                        rooms[current].Move(-direction, TILE_SIZE);
                        rooms[other].Move(direction, TILE_SIZE);
                    }
                }
            }
            while (IsAnyRoomOverlapped());

            StopTimer(true);
        }

And Room's Move() method:

public void Move(Vector2 move,int tileSize=1)
        {
            x += Mathf.RoundToInt(move.x)*tileSize;
            y += Mathf.RoundToInt(move.y)*tileSize;
        }