我正在使用 Pygame 开发一些 2D 游戏。我需要同时随机放置多个对象不相交。我已经尝试了一些明显的方法，但它们没有用。

明显的方法如下(伪):

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

那个方法花了很长时间。

我试过的其他方法:

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

该方法返回接近空列表。

我正在处理一个包含 2 到 20 个对象的列表。有什么建议吗？

编辑:矩形都是随机的不同大小。

最佳答案

我已经稍微更改了我的答案以解决您关于是否可以修改它以生成随机非碰撞正方形而不是任意矩形的后续问题。我以最简单的方式完成了这项工作，即对原始答案的矩形输出进行后处理，并将其内容转换为方形子区域。我还更新了可选的可视化代码以显示两种输出。显然，这种过滤可以扩展到做其他事情，比如稍微插入每个矩形或正方形以防止它们相互接触。

我的回答避免做许多已经发布的答案所做的事情——随机生成矩形，同时拒绝任何与任何已经创建的矩形相冲突的矩形——因为它听起来本质上很慢并且在计算上很浪费。相反，我的方法集中于仅生成一开始就不重叠的内容。

这使得需要做的事情变得相对简单，将其转化为一个可以非常快速地执行的简单区域分割问题。下面是如何做到这一点的一种实现。它以一个定义外边界的矩形开始，它分为四个较小的不重叠的矩形。这是通过选择一个半随机的内部点并将其与外部矩形的四个现有角点一起使用以形成四个子部分来实现的。

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

由于该算法生成子矩形的速度非常快，因此可以花一些计算时间来确定内部分割点。

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

无论如何，这是最新版本的代码和输出示例:

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

关于python - 我怎样才能随机放置几个非碰撞矩形？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4373741/