C# - Separating Overlapping Rectangles

Question

I'm trying to separate an arbitrary number of randomly sized rectangles, while still keeping them snapped to the grid, and somewhat packed together nicely. The goal is to start with something like this...

And end with something like this..

I've managed to get initial generation of random rectangles drawn in, that's the easy part; I've also done some reading up on separation algorithms but I can never seem to get things just right. They always spread out a bit (slowly, meaning lots of iterations) then just jitter around with massive gaps between them.

My (simple) separation function can be seen here, but it's very possible I'm doing something terribly wrong, or going about it all wrong! Here's also the current code in action (click/anykey to run the separation function)

Is there perhaps a better way to achieve this desired result, or something? Any help or suggestions would be great!

Answer 1

Please note that I'm only giving a rough starting point for an algorithm here. I can't say for sure if it will work, and you'll have to do a bit of legwork to implement this.

First, a few quick things: What do you define as "lots of iterations"? The TinyKeep demo you linked does it in around 40-50. Also, given that you are working with something 2D grid based, you should probably be working with a pair of integers (X and Y axis), rather than a floating-point Vector3.

Looking at your Separate() method, you don't seem to be taking into account the size of the rooms. This seems to be the primary issue. Because you need to be considering the penetration distance between pairs of rooms (which requires the size).

You only need to consider each pair of rooms once, so use a loop like this:

for(int i = 0; i < count; i++)
    for(int j = i+1; j < count; j++) // <- note how it starts at i+1

---

Here's a rough outline of the algorithm:

For each pair of rectangles, see if they intersect. Pick the axis with the minimum amount of penetration (so: left edge to right edge, right edge to left edge, top edge to bottom edge, bottom edge to top edge). Only use a single axis! Your current algorithm is considering both axes at once, based only on position.

In other words, if you only had two rectangles, this would be the smallest amount you would need to shift them to separate them. This amount could be split between the two rectangles in any ratio (but in opposite directions). This is a directional quantity, so store it as a vector (again: not as a vector3, but as a pair of int).

(This is basically a constrained version of the "separating axis theorem".)

The tricky bit, then, is to make this work for multiple rectangles in a way that can be iterated to a final solution. Without trying to implement it myself, I can't say for sure what this would look like. Here's what I would start with:

For each rectangle, store the maximum (or minimum?) separation vector by magnitude. When iterating over each pair, determine the minimum separation vector for that pair as explained above. Divide that separation vector evenly (or randomly?) between the two rectangles and replace the stored value for that rectangle if it is greater (or smaller?) in magnitude.

(Note: when dividing the integers, be aware that you must divide (for example) 5 into 3 and 2. So divide for one value, and subtract that from the total for the other.)

And then, apply the stored separation vectors to each rectangle - similar to what you are already doing. Then iterate until all of the separation vectors are zero.

Answer 2

This is what works for me in 3D using flattened cubes for a "floor".

I make a cube prefab and attach this script:

using UnityEngine;
using System.Collections;

public class move : MonoBehaviour
{

  public int strength;
  private GameObject[] gO;

  // Use this for initialization
  void Start ()
  {
  }

  // Update is called once per frame
  void Update ()
  {
    gO = GameObject.FindGameObjectsWithTag ("Gen");
    foreach (GameObject a in gO) {
      if (a != this) {
        if (this.GetComponent<Renderer> ().bounds.Intersects (a.GetComponent<Renderer> ().bounds)) {
          Vector3 direction = transform.position - a.transform.position;
          direction.Normalize ();
          transform.position = new Vector3 (Mathf.Round (transform.position.x + (direction.x * strength)), transform.position.y, Mathf.Round (transform.position.z + (direction.z * strength)));

        }
      }
    }
  }
}

Then instantiate a bunch of them over a random range, but pretty close together. If they're all created at, say, (0,0,0) they won't organize.