如何随机放置几个不碰撞的矩形？ [英] How can I randomly place several non-colliding rects?

问题描述

我正在与Pygame合作开发一些2D游戏。我需要同时将它们随机交叉放置，同时随机放置多个对象。我尝试了一些明显的方法，但是它们没有用。

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.

我尝试过的其他方法：

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.

我正在处理的列表的大小在2到20个对象之间。有建议吗？

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

编辑：这些矩形都是随机大小不同的

The rectangles are all random different sizes.

推荐答案

我对答案做了一些修改，以解决您的后续问题，即是否可以对其进行修改以生成随机的非碰撞的正方形而不是任意的矩形。我用最简单的方法做到了这一点，那就是对原始答案的矩形输出进行后处理，然后将其内容转换为方形子区域。我还更新了可选的可视化代码，以显示两种输出。显然，这种过滤可以扩展为执行其他操作，例如稍微插入每个矩形或正方形以防止它们彼此接触。

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.

大多数操作发生在 quadsect（）函数中。内部点的选择对于确定输出的外观至关重要。您可以按自己希望的方式对其进行约束，例如仅选择一个会导致子矩形至少具有某个最小宽度或高度或不大于某个数量的子矩形。在我的答案的示例代码中，将其定义为外部矩形的宽度和高度的中心点± ¹ / ₃ ，但是基本上任何内部点都可以

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.

为帮助可视化此方法的结果，最后有一些不必要的代码使用 PIL （Python Imaging Library）模块创建

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'

输出样本1

输出示例2

这篇关于如何随机放置几个不碰撞的矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！