How can I randomly place several non-colliding rects?

Question

I'm working on some 2D games with Pygame. I need to place several objects at the same time randomly without them intersecting. I have tried a few obvious methods but they didn't work.

Obvious methods follow (in pseudo):

create list of objects
for object in list:
    for other object in list:
        if object collides with other object:
            create new list of objects

That method took forever.

Other method I tried:

create list of objects
for object in list:
    for other object in list:
        if object collides with other object:
             remove object from list

That method returned near empty lists.

I'm dealing with a list that is anywhere from 2 - 20 objects large. Any suggestions?

EDIT: The rectangles are all random different sizes.

Answer 1

I've changed my answer a bit to address your follow-up question about whether it could be modified to instead generate random non-colliding squares rather than arbitrarily rectangles. I did this in the simplest way I could that would work, which was to post-process the rectangular output of my original answer and turn its contents into square sub-regions. I also updated the optional visualization code to show both kinds of output. Obviously this sort of filtering could be extended to do other things like insetting each rectangle or square slightly to prevent them from touching one another.

My answer avoids doing what many of the answers already posted do -- namely randomly generate rectangles while rejecting any that collide with those already created -- because it sounds inherently somewhat slow and computationally wasteful. Instead it concentrates on only generating ones that don't overlap in the first place.

That makes what needs to be done relatively simple by turning it into a area subdivision problem which can be done very quickly. Below is one implementation of how this could be done. It starts with a rectangle defining the outer boundary which it divides into four smaller non-overlapping rectangles. That is accomplished by choosing a semi-random interior point and using it along with the four existing corner points of the outer rectangle to form the four subsections.

Most of the action take place in thequadsect()function. The choice of the interior point is crucial in determining what the output looks like. You can constrain it any way you wish, such as only selecting one that would result in sub-rectangles of at least a certain minimum width or height or no bigger than some amount. In the sample code in my answer, it's defined as the center point ±¹/₃ of the width and height of the outer rectangle, but basically any interior point would work to some degree.

Since this algorithm generates sub-rectangles very rapidly, it's OK to spend some computational time determining the interior division point.

To help visualize the results of this approach, there's some non-essential code at the very end that uses thePIL(Python Imaging Library) module to create an image file displaying the rectangles generated during some test runs I made.

Anyway, here's the latest version of the code and output samples:

import random
from random import randint
random.seed()

NUM_RECTS = 20
REGION = Rect(0, 0, 640, 480)

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    @staticmethod
    def from_point(other):
        return Point(other.x, other.y)

class Rect(object):
    def __init__(self, x1, y1, x2, y2):
        minx, maxx = (x1,x2) if x1 < x2 else (x2,x1)
        miny, maxy = (y1,y2) if y1 < y2 else (y2,y1)
        self.min, self.max = Point(minx, miny), Point(maxx, maxy)

    @staticmethod
    def from_points(p1, p2):
        return Rect(p1.x, p1.y, p2.x, p2.y)

    width  = property(lambda self: self.max.x - self.min.x)
    height = property(lambda self: self.max.y - self.min.y)

plus_or_minus = lambda v: v * [-1, 1][(randint(0, 100) % 2)]  # equal chance +/-1

def quadsect(rect, factor):
    """ Subdivide given rectangle into four non-overlapping rectangles.
        'factor' is an integer representing the proportion of the width or
        height the deviatation from the center of the rectangle allowed.
    """
    # pick a point in the interior of given rectangle
    w, h = rect.width, rect.height  # cache properties
    center = Point(rect.min.x + (w // 2), rect.min.y + (h // 2))
    delta_x = plus_or_minus(randint(0, w // factor))
    delta_y = plus_or_minus(randint(0, h // factor))
    interior = Point(center.x + delta_x, center.y + delta_y)

    # create rectangles from the interior point and the corners of the outer one
    return [Rect(interior.x, interior.y, rect.min.x, rect.min.y),
            Rect(interior.x, interior.y, rect.max.x, rect.min.y),
            Rect(interior.x, interior.y, rect.max.x, rect.max.y),
            Rect(interior.x, interior.y, rect.min.x, rect.max.y)]

def square_subregion(rect):
    """ Return a square rectangle centered within the given rectangle """
    w, h = rect.width, rect.height  # cache properties
    if w < h:
        offset = (h - w) // 2
        return Rect(rect.min.x, rect.min.y+offset,
                    rect.max.x, rect.min.y+offset+w)
    else:
        offset = (w - h) // 2
        return Rect(rect.min.x+offset, rect.min.y,
                    rect.min.x+offset+h, rect.max.y)

# call quadsect() until at least the number of rects wanted has been generated
rects = [REGION]   # seed output list
while len(rects) <= NUM_RECTS:
    rects = [subrect for rect in rects
                        for subrect in quadsect(rect, 3)]

random.shuffle(rects)  # mix them up
sample = random.sample(rects, NUM_RECTS)  # select the desired number
print '%d out of the %d rectangles selected' % (NUM_RECTS, len(rects))

#################################################
# extra credit - create an image file showing results

from PIL import Image, ImageDraw

def gray(v): return tuple(int(v*255) for _ in range(3))

BLACK, DARK_GRAY, GRAY = gray(0), gray(.25), gray(.5)
LIGHT_GRAY, WHITE = gray(.75), gray(1)
RED, GREEN, BLUE = (255, 0, 0), (0, 255, 0), (0, 0, 255)
CYAN, MAGENTA, YELLOW = (0, 255, 255), (255, 0, 255), (255, 255, 0)
BACKGR, SQUARE_COLOR, RECT_COLOR = (245, 245, 87), (255, 73, 73), (37, 182, 249)

imgx, imgy = REGION.max.x + 1, REGION.max.y + 1
image = Image.new("RGB", (imgx, imgy), BACKGR)  # create color image
draw = ImageDraw.Draw(image)

def draw_rect(rect, fill=None, outline=WHITE):
    draw.rectangle([(rect.min.x, rect.min.y), (rect.max.x, rect.max.y)],
                   fill=fill, outline=outline)

# first draw outlines of all the non-overlapping rectanges generated
for rect in rects:
    draw_rect(rect, outline=LIGHT_GRAY)

# then draw the random sample of them selected
for rect in sample:
    draw_rect(rect, fill=RECT_COLOR, outline=WHITE)

# and lastly convert those into squares and re-draw them in another color
for rect in sample:
    draw_rect(square_subregion(rect), fill=SQUARE_COLOR, outline=WHITE)

filename = 'square_quadsections.png'
image.save(filename, "PNG")
print repr(filename), 'output image saved'

Output Sample 1

Output Sample 2

Answer 2

Three ideas:

Decrease the size of your objects

The first method fails because hitting a random array of 20 non-overlapping objects is highly improbable (actually (1-p)^20, where 0<p<1 is the probability of two objects colliding). If you could dramatically (orders-of-magnitude drama) decrease their size, it might help.

Pick them one by one

The most obvious improvement would be:

while len(rectangles)<N:
    new_rectangle=get_random_rectangle()
    for rectangle in rectangles:
        if not any(intersects (rectangle, new_rectangle) for rectangle in rectangles)
            rectangles.add(new_rectangle)

This would greatly improve your performance, as having a single intersection will not force you to generate a whole new set, just to pick a different single rectangle.

Pre-calculation

How often will you be using these sets in your game? Using a different set every second is a different scenario than using a set once in an hour. If you don't use these sets too often, pre-calculate s large-enough set so that the gamer would probably never see the same set twice. When pre-calculating, you don't care too much for the time spent (so you can even use your inefficient first algorithm).

Even if you actually need these rectangles at run time, it might be a good idea to calculate them a bit before you need them, when the CPU is idle for some reason, so that you'll always have a set ready in hand.

At run time, just pick a set at random. This is probably the best approach for real-time gaming.

Note: This solution assumes that you rectangles are kept in a space-saving manner, e.g. pairs of (x, y) coordinates. These pairs consume very little space, and you can actually save thousands, and even millions, in a file with reasonable size.

Useful links:

• Place random non-overlapping rectangles on a panel
• minimizing overlap in random rectangles

Answer 3

There is a very simple approximation to your problem which worked fine for me:

• Define a grid. For instance a 100 pixel grid writes (x,y) -> (int(x/100),int(y/100)). The grid elements do not overlap.
• Either put each object in a different grid (randomly inside the grid will look prettier), either put randomly a few objects in each grid, if you can allow a few objects to overlap.

I used this to randomly generate a 2D map (Zelda like). My objects' images are smaller than <100*100>, so I used grid of size <500*500> and allowed for 1-6 objects in each grid.

Answer 4

list_of_objects = []
for i in range(20):
    while True:
        new_object = create_object()
        if not any(collides(new_object, x) for x in list_of_objects):
            break
    list_of_objects.append(new_object)

I assume you already have the create_object() and collides() functions

You may also need to decrease the size of the rects if this loops too many times

Answer 5

Did you try:

Until there are enough objects:
    create new object
    if it doesn't collide with anything in the list:
        add it to the list

No sense recreating the entire list, or taking out everything that's involved in a collision.

Another idea is to "fix" collisions by either of the following approaches:

1) Find the center of the region of intersection, and adjust the appropriate corner of each intersecting rect to that point, such that they now touch on corner/edge instead of intersecting.

2) When a rectangle collides with something, randomly generate a sub-region of that rectangle and try that instead.

Answer 6

an alternative pseudocode, to those already mentioned:

while not enough objects:
  place object randomly
  if overlaps with anything else:
    reduce size until it fits or has zero size
  if zero size: 
    remove

Or something like that.

But this has the advantage of possibly creating some smaller objects than you intended, and creating objects which almost intersect (i.e. touch).

If it's a map for the player to traverse, they may still not be able to traverse it because their path could be blocked.

Answer 7

In my case I had a similar problem except that I had some pre-exiting rectangles inside the overall rectangle. So new rectangles had to be placed around those existing ones.

I used a greedy approach:

• Rectangularize the overall (global) rectangle: create a grid from the sorted x & sorted y coordinates of all rectangles so far. So that will give you an irregular (but rectangular) grid.
• For each grid cell calculate the area, this gives you a matrix of areas.
• Use Kadanes 2D algorithm to find the sub matrix that gives you the maximum area (= the largest free rectangle)
• Place a random rectangle in that free space
• Repeat

This requires a conversion from your original coordinate space to/from the grid space but straightforward to do.

(Note that running Kadene directly on the original, global rectangle takes to long. Going via a grid approximation is plenty fast for my application)