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 -- which is randomly generating rectangles while rejecting any that collide with any already created -- because it sounds inherently slow and computationally wasteful. My approach concentrates instead 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 simple area subdivision problem which can be performed very quickly. Below is one implementation of how that can 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 the quadsect() 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 the PIL (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.