如何随机放置几个非碰撞矩形? [英] 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 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.

为了帮助可视化这种方法的结果，最后有一些非必要的代码使用 PIL(Python 成像库)模块来创建一个图像文件，显示在某些过程中生成的矩形我进行的测试运行.

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'

输出示例 1

输出示例 2

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