# Random Positions with margin

Hi
How to add margin to random positions.
I don’t want objects to cover each other. It’s 2D so only x and y meters.

private Vector3 getPosition()
{
float PosX = Random.Range(-10,10);
float PosX = Random.Range(-10,10);
Vector3 objPos = new Vector3(PosX,PosY, 0.0f);
return objPos;
}

I’m assuming the objects are rectangles.

Update: Anywhere I mention using Rect, use Bounds instead since that’s what has the required intersection methods.

Brute Force

A brute force approach would be to keep a list of the rectangles you’ve generated, and each time you generate a new one you make sure it doesn’t overlap anything in the list. If it does overlap then generate new coordinates.

foreach object to generate
{
while (true)
{
rect = new Rect(random_x, random_y, width, height);
if (!rect_overlaps_existing(rect)) break;
}

}

The rect_overlaps_existing function loops through the rect list and checks for overlaps.

This is a bit ugly, and can have some looping while searching for free random coordinates, but would probably work fine if you just have a few objects that are relatively small compared to the random area where you’re placing them. If you have too many objects, or they’re large, you have the potential of an infinite loop if it can’t find a non-overlapping area. This can be partially remedied by limiting the max iterations. I’ve used this approach in similar situations and it works fine (again, keeping in mind the size and quantity limitations).

Packing Algorithm

A better approach would be some sort of packing algorithm. One that comes to mind is to keep track of a “free rect list”, which is a list of unused rectangles. The list starts with a single rectangle that encompasses the entire area, and it gets split into multiple rects as you use up space.

foreach object to generate
{
free_rect = find_free_rect();
rect = generate random rect from within free_rect
split_rect(free_rect, rect);
}

The find_free_rect function just grabs a random rectangle from the list of free ones. The first time this will just grab the entire screen area.

Then you generate a random rectangle that lies within the free rectangle you just found.

Finally, you split that free rectangle into multiple rectangles that are leftover after you use up part of the space, and add those new free rectangles to the list. This is the most difficult part, and I leave it as an exercise for the reader. Basically, envision a rectangle (the free area) with another rectangle carved out of the center. You end up with sort of a room with odd shaped walls, and the center empty. Those odd shaped walls have to be turned into new rectangles that go into the free list. And of course you have interesting edge cases (no pun intended) if the carved out area is along one or more borders.

Grid Approach

A potential variation (and vast simplification) on the packing algorithm method is if keeping the random objects in a grid is possible. Envision a grid of rectangles on the screen. Pre-generate a free rectangle list that contains a rectangle for each cell in the grid. When you need a random rectangle, pull pick one randomly from the list and remove it. Generating the list is easy because none of them will ever overlap.

There are likely other approaches as well, but I imagine they would all fall close to the packing algorithm in complexity. That, or I’m way overanalyzing the problem :). Do some searching on packing algorithms and maybe you’ll find something simpler, though many of them are dealing with trying to optimally pack rectangles into a minimum amount of space.

The Actual Intersection Test

Each of the methods will require testing for intersection. Unity has a Bounds struct for dealing with this (as opposed to Rect, which other libraries sometimes use for these types of tests).

Bounds sprite1 = new Bounds(new Vector3(random_x, random_y, 0), new Vector3(20, 20, 0));
Bounds sprite2 = new Bounds(new Vector3(random_x, random_y, 0), new Vector3(20, 20, 0));

if (sprite1.Intersects(sprite2))
{
// act on the overlap
}