我如何随机放置几个非coll缩的矩形？

https://stackoverflow.com/questions/4373741

09-10-2019
|

题

我正在使用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 Imaging库）模块创建一个图像文件，显示我进行的某些测试过程中生成的矩形。

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

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

first sample output image

输出样本2

second sample output image

其他提示

三个想法：

减小物体的大小

第一个方法失败了，因为击中20个非重叠对象的随机数组非常不可能（实际上 (1-p)^20, ，在哪里 0<p<1 是两个对象碰撞的概率）。如果您可以显着（魔力戏剧命令）降低其规模，那可能会有所帮助。

一个接一个地选择

最明显的改进是：

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)

这将大大提高您的性能，因为拥有一个交叉路口不会迫使您生成一个全新的集合，而只是为了选择其他矩形。

预计

您将在游戏中使用这些套装多久？每秒使用不同的集合与一个小时使用一次集合不同。如果您不经常使用这些套件，则预测S的大量套件，因此游戏玩家可能永远不会看到两次相同的集合。预先计算时，您不太在乎所花费的时间（因此您甚至可以使用效率低下的第一算法）。

即使您实际上在运行时需要这些矩形，也可能是一个好主意，最好在需要时，当CPU出于某种原因而闲置时，因此您始终准备好一套套装。

在运行时，只需随机选择一个。这可能是实时游戏的最佳方法。

笔记：该解决方案假设您的矩形以节省空间的方式保存，例如 (x, y) 坐标。这些对消耗的空间很少，实际上您可以将数千甚至数百万的文件保存在具有合理尺寸的文件中。

有用的链接：

您的问题有一个非常简单的近似值，对我来说很好：

定义网格。例如，100像素网格写入（x，y） - >（int（x/100），int（y/100））。网格元素不会重叠。
要么将每个对象放在不同的网格中（在网格中随机看起来更漂亮），要么在每个网格中随机放置几个对象，如果您可以允许一些对象重叠。

我用它随机生成2D地图（Zelda Like）。我的对象的图像小于<100*100>，因此我使用了大小<500*500>的网格，并且每个网格中允许1-6个对象。

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)

我认为你已经有 create_object() 和 collides() 功能

如果循环过多，您可能还需要降低矩形的大小

你试过了吗：

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

重新创建整个列表或删除碰撞所涉及的所有内容。

另一个想法是通过以下任何一种方法“修复”碰撞：

1）找到交叉区域的中心，并将每个相交的rect的适当角度调整到该点，以便它们现在触及角/边缘而不是相交。

2）当矩形与某些东西发生碰撞时，随机生成该矩形的子区域，然后尝试一下。

已经提到的替代伪代码：

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

或类似的东西。

但这具有可能创建比您预期的小对象的优点，并创建几乎相交的对象（即触摸）。

如果这是玩家穿越的地图，他们可能仍然无法穿越它，因为他们的路径可能会被阻塞。

就我而言，我也有类似的问题，除了我在整个矩形内有一些预删除的矩形。因此，必须将新矩形放置在这些现有的矩形周围。

我使用了一种贪婪的方法：

矩形整体（全局）矩形：从迄今为止所有矩形的所有矩形的X＆CORDINATIES创建一个网格。因此，这将为您提供不规则（但矩形）的网格。
对于每个网格单元，计算该区域，这为您提供了一个区域矩阵。
利用 Kadanes 2d 算法找到为您提供最大面积的子矩阵（=最大的自由矩形）
将随机矩形放在那个自由空间中
重复

这需要从原始的坐标空间转换为/从网格空间，但要直接做。

（请注意，直接在原始的全局矩形上运行kadene需要很长的时间。通过网格近似对于我的应用程序很快）

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow