如何随机放置几个不碰撞的矩形？

发布于 2024-10-06 12:43:59 字数 617 浏览 6 评论 0原文

我正在使用 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 个对象的列表。有什么建议吗？

编辑：矩形的大小都是随机的。

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

撧情箌佬 2024-10-13 12:43:59

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

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

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

大部分操作发生在 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'

Output Sample 1

first example output image

Output Sample 2

第二个示例输出图像

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

first sample output image

Output Sample 2

second sample output image

回复收藏 0 原文

半岛未凉 2024-10-13 12:43:59

三个想法：

减小对象的大小

第一种方法会失败，因为击中 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)

这将极大地提高您的性能，因为只有一个交集不会迫使您生成一个全新的集合，而只需选择一个不同的单个矩形。

预先计算

您在游戏中使用这些集合的频率是多少？每秒使用不同的集合与每小时使用一次集合的情况不同。如果您不经常使用这些集合，请预先计算足够大的集合，以便玩家可能永远不会两次看到相同的集合。预计算时，您不太关心所花费的时间（因此您甚至可以使用低效的第一个算法）。

即使您在运行时确实需要这些矩形，当 CPU 由于某种原因处于空闲状态时，在需要它们之前稍微计算一下它们可能是一个好主意，这样您就可以随时准备好一组矩形。

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

注意：
该解决方案假设矩形以节省空间的方式保存，例如(x, y) 坐标对。这些对占用的空间非常小，实际上您可以在一个大小合理的文件中保存数千甚至数百万。

有用的链接：

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:

回复收藏 0 原文

淡淡的优雅 2024-10-13 12:43:59

对于您的问题，有一个非常简单的近似方法，对我来说效果很好：

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

我用它来随机生成一个 2D 地图（类似塞尔达）。我的对象的图像小于 <100*100>，因此我使用了大小为 <500*500> 的网格。每个网格中允许有 1-6 个对象。

回复收藏 0 原文

天生の放荡 2024-10-13 12:43:59

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() 函数，

如果循环次数过多，您可能还需要减小矩形的大小

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)

I assume you already have the create_object() and collides() functions

You may also need to decrease the size of the rects if this loops too many times

回复收藏 0 原文

靖瑶 2024-10-13 12:43:59

您是否尝试过：

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

重新创建整个列表或删除冲突中涉及的所有内容是没有意义的。

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

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

2）当一个矩形与某物碰撞时，随机生成该矩形的一个子区域并尝试。

Did you try:

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

No sense recreating the entire list, or taking out everything that's involved in a collision.

Another idea is to "fix" collisions by either of the following approaches:

1) Find the center of the region of intersection, and adjust the appropriate corner of each intersecting rect to that point, such that they now touch on corner/edge instead of intersecting.

2) When a rectangle collides with something, randomly generate a sub-region of that rectangle and try that instead.

回复收藏 0 原文

抚你发端 2024-10-13 12:43:59

替代伪代码，对于已经提到的伪代码：

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

或者类似的东西。

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

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

an alternative pseudocode, to those already mentioned:

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

Or something like that.

But this has the advantage of possibly creating some smaller objects than you intended, and creating objects which almost intersect (i.e. touch).

If it's a map for the player to traverse, they may still not be able to traverse it because their path could be blocked.

回复收藏 0 原文