如何随机放置多个不重叠的矩形？
我正在用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个物体。有没有什么建议？
补充：这些矩形的大小都是随机的，形状也不一样。
7 个回答
这里有一个非常简单的方法可以解决你的问题，我用过，效果不错：
- 首先，定义一个网格。比如说，设定一个100像素的网格，把坐标(x,y)转换为(int(x/100),int(y/100))。这样网格之间不会重叠。
- 你可以选择把每个物体放在不同的网格里（在网格内随机放置会更好看），或者在每个网格里随机放几个物体，如果你允许物体之间有些重叠的话。
我用这个方法随机生成了一个2D地图（像《塞尔达传说》那样）。我的物体图像小于100*100，所以我用了一个500*500的网格，并允许每个网格里放1到6个物体。
三个想法：
减小对象的大小
第一个方法不太靠谱，因为随机碰撞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)坐标。这些坐标占用的空间非常少，你实际上可以在一个合理大小的文件中保存成千上万，甚至数百万个。
有用的链接：
我稍微修改了一下我的回答，以便更好地回答你关于是否可以改成生成随机的不重叠的正方形而不是任意的矩形的问题。我用最简单的方法来实现这个，就是对我原来的答案中的矩形输出进行后处理，把它们转变成正方形的小区域。我还更新了可选的可视化代码，以显示这两种输出。显然，这种过滤方法可以扩展到其他用途，比如稍微缩进每个矩形或正方形，以防它们相互接触。
我的回答避免了许多已经发布的答案所做的事情——即随机生成矩形，同时拒绝与任何已创建的矩形重叠的矩形，因为这听起来本质上很慢且浪费计算资源。我的方法则专注于只生成那些一开始就不重叠的矩形。
这使得需要完成的工作相对简单，因为它变成了一个简单的区域划分问题，可以非常快速地执行。下面是如何实现这一点的一个示例。它从一个定义外部边界的矩形开始，然后将其划分为四个不重叠的小矩形。这是通过选择一个半随机的内部点，并将其与外部矩形的四个角点一起使用，来形成四个子区域。
大部分操作发生在quadsect()函数中。内部点的选择对输出的外观至关重要。你可以根据需要进行限制，比如只选择那些能生成至少有一定最小宽度或高度的子矩形，或者不超过某个大小。在我回答中的示例代码里，它被定义为外部矩形的中心点±1/3的宽度和高度，但基本上任何内部点都能在一定程度上工作。
由于这个算法可以非常快速地生成子矩形，因此花一些计算时间来确定内部划分点是可以接受的。
为了帮助可视化这种方法的结果，最后有一些非必要的代码，使用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
