Separating overlapping rectangles

I am currently working on a dungeon game.

Right now I have to generate the rooms of the dunegon. The first step is easy, as it is the placement of the rooms. Now I have to move them, as they are overlapping with each other. I have written a small script in c# that should do the work:
Before

![alt text][1]

and after:

![alt text][2]

Unfortunately the script isn’t doing what I wanted it to do, as it keeps moving the rooms without stopping.
I have read some informations about the [Separating Axis Theorem][3] that I used in the code:

(this is the class for the room)

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class Stanza {
	
	public Vector2 centro;
	public Vector2 max, min, dimensione;
	
	public Stanza (Vector2 c, Vector2 dim) {
		
		centro = c;
		
		dimensione = dim;
		
		max.x = centro.x + dim.x / 2;
		max.y = centro.y + dim.y / 2;
		
		min.x = centro.x - dim.x / 2;
		min.y = centro.y - dim.y / 2;
		
	}

	public void spostaStanza(Vector2 dir) {

		centro.x += dir.x;
		centro.y += dir.y;

		max.x += dir.x;
		max.y += dir.y;

		min.x += dir.x;
		min.y += dir.y;

	}
	
}

then this is the real script that does the work:

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class Stanze : MonoBehaviour {

	public List<Stanza> stanze = new List<Stanza> ();

	public List<GameObject> rects = new List<GameObject> ();

	public GameObject piano;

	public int numStanze = 5;

	// Use this for initialization
	void Start () {

		for (int i=0; i<numStanze; i++) {

			stanze.Add(new Stanza(new Vector2(Random.Range(-50,50), Random.Range(-50,50)), new Vector2(Random.Range(3,8),Random.Range(3,8))));

		}
		Time.timeScale = 0.01f;
	}

	void Update() {
		for (int i=0; i<numStanze; i++) {
			Vector2 l1;
			l1.x = Mathf.Abs (stanze_.centro.x - stanze*.max.x);*_

l1.y = Mathf.Abs (stanze_.centro.y - stanze*.max.y);*_

* for(int j=1; j<numStanze; j++) {*

* Vector2 d;*
_ d.x = Mathf.Abs (stanze*.centro.x - stanze[j].centro.x);
d.y = Mathf.Abs (stanze.centro.y - stanze[j].centro.y);*_

* Vector2 l2;*
* l2.x = Mathf.Abs (stanze[j].centro.x - stanze[j].max.x);*
* l2.y = Mathf.Abs (stanze[j].centro.y - stanze[j].max.y);*

* Vector2 ltot;*
* ltot.x = l1.x + l2.x;*
* ltot.y = l1.y + l2.y;*

* if(ltot.x > d.x || ltot.y > d.y) {*

* print(“Sovvraposizione!”);*

* Vector2 move;*
* move.x = ltot.x - d.x;*
* move.y = ltot.y - d.y;*

* if(move.x >= move.y) {*

* move.y = 0;*

_ stanze*.spostaStanza(move);*_

* } else {*

* move.x = 0;*

_ stanze*.spostaStanza(move);*_

* }*

* }*

* }*

* }*

* display ();*
* }*

* void display() {*

* if (rects.Count > 0) {*
* for(int i=0; i<numStanze; i++) {*
_ Destroy(rects*);
}*_

* rects.Clear();*
* }*

* for(int i=0; i<numStanze; i++) {*
_ rects.Add(Instantiate (piano, stanze*.centro, Quaternion.Euler(90,0,0)) as GameObject);*_

rects.transform.localScale = new Vector3(stanze_.dimensione.x,1,stanze*.dimensione.y);
}
}*_

}
The public GameObject piano must have a plane (default unity one).
Eventually what I want to end up with should be like [this][4].
Thanks in advice for any help!
*[1]: http://i.imgur.com/5JgbhWY.png*_
[2]: http://i.imgur.com/iK2yy3V.png*_
_[3]: N Tutorial A - Collision Detection and Response

_*[4]: http://tinykeep.com/dungen/*_

You have several logic errors in your code:

  • In line 32 you should start your inner loop at “i + 1” instead of “1”. Otherwise when i is greater than 0 each outer iteration you always get one pair where i and j are equal. So you intersect the rectangle with itself.

  • In line 46 you have an || (logical “or”) where you need an && (logical “and”) because you only have an intersection when they intersect on both axis.

  • In line 54 you have the condition the other way round. The idea is that you seperate the rectangles in the direction with the smallest overlap.

  • In line 58 and 64 you only move one of the colliding rectangles. This could lead to situations where get stuck in a certain permutation. You should move both, each in the opposite direction by half the amount. Your move vector is actually always positive. So you don’t really take into account on which side the rects intersect. You should use the actual distance vector without Mathf.Abs.

Further more you should define a minimum seperation distance. Do you actually work on a grid? In that case you should apply a rounding scheme. If you want to use float values, make sure you seperate a little bit more than necessary, or it will take a very long time until the seperation is finished. (Actually it would never finish since the seperation distance will just get smaller and smaller each iteration. It just might finish after some time because the float eventually runs out of precision).

ps: It seems you use your “dimensione” variable directly as scale for the plane, however the default plane has a size of 10x10 units (or 5 units from the center). A “3D Quad” has a size of 1x1 unit (so it’s 0.5 from the center). If you want to use a quad instead, keep in mind that it has a different rotation than the plane mesh. You shouldn’t need to rotate the Quad. The Quad mesh is in the x-y-plane while the Plane mesh is in the x-z-plane. Keep that in mind when assigning the scale ^^.