在Python中生成范围外的随机数

Question

我现在正在做一个pygame游戏，我需要在屏幕上随机放置物体，但这些物体不能放在一个指定的矩形区域内。有没有什么简单的方法可以做到这一点，而不是不断生成随机坐标，直到它们在矩形外面？

这里有个大概的例子，展示了屏幕和矩形的样子。

 ______________
|      __      |
|     |__|     |
|              |
|              |
|______________|

屏幕的大小是1000x800，而矩形的坐标是[x: 500, y: 250, 宽度: 100, 高度: 75]

从代码的角度来看，可以这样理解

x = random_int
0 <= x <= 1000
    and
500 > x or 600 < x

y = random_int
0 <= y <= 800
    and
250 > y or 325 < y

相关文章：

• 暂无相关问题

Answer 1

如果你想避免生成随机数，而不是避免循环，可以按照以下步骤操作：

1. 生成一对随机的浮点坐标，范围在[0,1]之间。
2. 将这些坐标放大，得到外部矩形中的一个点。
3. 如果这个点在内部矩形之外，就返回这个点。
4. 重新调整大小，把内部矩形映射到外部矩形。
5. 回到第3步。

这样做的效果最好是内部矩形相对于外部矩形比较小。而且可能需要限制循环的最大次数，超过这个次数就重新生成随机数再试一次。

Answer 2

我之前发过一个不同的回答，我还是挺喜欢的，因为它简单明了，而且不一定慢……不过这并不是提问者想要的答案。

我考虑了一下，想出了一个算法，可以在提问者的条件下解决他们的问题：

1. 把屏幕分成9个矩形，围绕着并包含“洞”。
2. 考虑中央洞周围的8个矩形（“瓦片”）。
3. 对于每个瓦片，计算它的起始位置（x, y）、高度和像素面积。
4. 计算这些瓦片的面积总和，以及所有瓦片的总面积。
5. 对于每次提取，选择一个在0到瓦片总面积之间的随机数（包括0和总面积）。
6. 利用累计面积来确定这个随机像素在哪个瓦片里。
7. 使用 divmod 来确定在瓦片中的列和行（dx, dy）。
8. 根据瓦片在屏幕坐标中的起始位置，计算出这个随机像素在屏幕坐标中的位置。

为了实现以上想法，我们需要一个初始化阶段来计算静态数据，以及一个阶段来重复使用这些数据，最自然的数据结构就是一个类，这里是我的实现。

from random import randrange

class make_a_hole_in_the_screen():

    def __init__(self, screen, hole_orig, hole_sizes):
        xs, ys = screen
        x, y = hole_orig
        wx, wy = hole_sizes
        tiles = [(_y,_x*_y) for _x in [x,wx,xs-x-wx] for _y in [y,wy,ys-y-wy]]
        self.tiles = tiles[:4] + tiles[5:]
        self.pixels = [tile[1] for tile in self.tiles]
        self.total = sum(self.pixels)
        self.boundaries = [sum(self.pixels[:i+1]) for i in range(8)]
        self.x = [0,    0,    0,
                  x,          x,
                  x+wx, x+wx, x+wx]
        self.y = [0,    y,    y+wy,
                  0,          y+wy,
                  0,    y,    y+wy]

    def choose(self):
        n = randrange(self.total)
        for i, tile in enumerate(self.tiles):
            if n < self.boundaries[i]: break
        n1 = n - ([0]+self.boundaries)[i]
        dx, dy = divmod(n1,self.tiles[i][0])
        return self.x[i]+dx, self.y[i]+dy

为了测试实现的正确性，这里有一个我在 python 2.7 上运行的粗略检查。

drilled_screen = make_a_hole_in_the_screen((200,100),(30,50),(20,30))
for i in range(1000000):
    x, y = drilled_screen.choose()
    if 30<=x<50 and 50<=y<80: print "***", x, y
    if x<0 or x>=200 or y<0 or y>=100: print "+++", x, y

一个可能的优化方法是使用二分查找算法来找到相关的瓦片，而不是我实现的简单线性搜索。

Answer 3

这个方法在时间和内存方面都能做到O(1)，也就是说无论处理多大的数据，所需的时间和内存都是固定的。

原因

一些被接受的答案和其他答案似乎都依赖于生成所有可能坐标的列表，或者不断重新计算直到找到一个合适的解决方案。这两种方法都比实际需要的时间和内存要多。

需要注意的是，根据坐标生成的均匀性要求，有不同的解决方案，下面会展示。

第一次尝试

我的方法是随机选择指定区域周围的有效坐标（想象一下“左/右”，“上/下”），然后随机选择一个边来决定：

import random
# set bounding boxes    
maxx=1000
maxy=800
blocked_box = [(500, 250), (100, 75)]
# generate left/right, top/bottom and choose as you like
def gen_rand_limit(p1, dim):
    x1, y1 = p1
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    left = random.randrange(0, x1)
    right = random.randrange(x2+1, maxx-1)
    top = random.randrange(0, y1)
    bottom = random.randrange(y2, maxy-1)
    return random.choice([left, right]), random.choice([top, bottom])
# check boundary conditions are met
def check(x, y, p1, dim):
    x1, y1 = p1
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    assert 0 <= x <= maxx, "0 <= x(%s) <= maxx(%s)" % (x, maxx)
    assert x1 > x or x2 < x, "x1(%s) > x(%s) or x2(%s) < x(%s)" % (x1, x, x2, x)
    assert 0 <= y <= maxy, "0 <= y(%s) <= maxy(%s)" %(y, maxy)
    assert y1 > y or y2 < y, "y1(%s) > y(%s) or y2(%s) < y(%s)" % (y1, y, y2, y)
# sample
points = []
for i in xrange(1000):
    x,y = gen_rand_limit(*blocked_box)
    check(x, y, *blocked_box)
    points.append((x,y))

结果

根据提问者的要求，这实际上产生了想要的随机坐标（蓝色）在指定的矩形（红色）周围，但遗漏了任何在矩形外但在矩形的x或y维度内的有效点：

# visual proof via matplotlib
import matplotlib
from matplotlib import pyplot as plt
from matplotlib.patches import Rectangle
X,Y = zip(*points)
fig = plt.figure()
ax = plt.scatter(X, Y)
p1 = blocked_box[0]
w,h = blocked_box[1]
rectangle = Rectangle(p1, w, h, fc='red', zorder=2)
ax = plt.gca()
plt.axis((0, maxx, 0, maxy))
ax.add_patch(rectangle)

改进

通过仅限制x或y坐标，这个问题很容易解决（注意check不再有效，注释掉以运行这部分）：

def gen_rand_limit(p1, dim):
    x1, y1 = p1
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    # should we limit x or y?
    limitx = random.choice([0,1])
    limity = not limitx
    # generate x, y O(1)
    if limitx:
        left = random.randrange(0, x1)
        right = random.randrange(x2+1, maxx-1)
        x = random.choice([left, right])
        y = random.randrange(0, maxy)
    else:
        x = random.randrange(0, maxx)
        top = random.randrange(0, y1)
        bottom = random.randrange(y2, maxy-1)
        y = random.choice([top, bottom])
    return x, y 

调整随机偏差

正如评论中指出的，这个解决方案存在一个偏差，即给了矩形行/列外的点更多的机会。以下方法在原则上解决了这个问题，使每个坐标的概率相同：

def gen_rand_limit(p1, dim):
    x1, y1 = p1Final solution -
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    # generate x, y O(1)
    # --x
    left = random.randrange(0, x1)
    right = random.randrange(x2+1, maxx)
    withinx = random.randrange(x1, x2+1)
    # adjust probability of a point outside the box columns
    # a point outside has probability (1/(maxx-w)) v.s. a point inside has 1/w
    # the same is true for rows. adjupx/y adjust for this probability 
    adjpx = ((maxx - w)/w/2)
    x = random.choice([left, right] * adjpx + [withinx])
    # --y
    top = random.randrange(0, y1)
    bottom = random.randrange(y2+1, maxy)
    withiny = random.randrange(y1, y2+1)
    if x == left or x == right:
        adjpy = ((maxy- h)/h/2)
        y = random.choice([top, bottom] * adjpy + [withiny])
    else:
        y = random.choice([top, bottom])
    return x, y 

下面的图有10,000个点，用来展示点的均匀分布（点重叠在矩形边框上是因为点的大小）。

免责声明：请注意，这个图将红色矩形放在正中间，使得上/下和左/右之间的概率相同。因此，调整是相对于阻挡的矩形，而不是图表的所有区域。最终的解决方案需要单独调整每个区域的概率。

更简单的解决方案，但稍微修改了问题

事实证明，调整坐标系统不同区域的概率相当棘手。经过一些思考，我想出了一个稍微修改的方法：

意识到在任何二维坐标系统中，阻挡一个矩形会将区域分成N个子区域（在这个问题中N=8），可以选择有效的坐标。这样看，我们可以将有效的子区域定义为坐标的框。然后我们可以随机选择一个框，并从该框内随机选择一个坐标：

def gen_rand_limit(p1, dim):
    x1, y1 = p1
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    # generate x, y O(1)
    boxes = (
       ((0,0),(x1,y1)),   ((x1,0),(x2,y1)),    ((x2,0),(maxx,y1)),
       ((0,y1),(x1,y2)),                       ((x2,y1),(maxx,y2)),
       ((0,y2),(x1,maxy)), ((x1,y2),(x2,maxy)), ((x2,y2),(maxx,maxy)),
    )
    box = boxes[random.randrange(len(boxes))]
    x = random.randrange(box[0][0], box[1][0])
    y = random.randrange(box[0][1], box[1][1])
    return x, y 

注意这并不是一个通用的方法，因为被阻挡的框可能不在中间，因此boxes的形状会不同。由于每个框被选择的概率相同，我们在每个框中得到的点的数量是相同的。显然，较小的框中的点密度更高：

如果要求在所有可能的坐标中生成均匀分布，解决方案是计算boxes，使每个框的大小大约与阻挡框相同。你的情况可能会有所不同。

Answer 4

1. 把这个大盒子分成几个小盒子。
2. 在这些有效的小盒子中，按照它们的面积来决定放哪个点，面积越大的小盒子被选中的概率就越高。
3. 从选中的小盒子里随机挑一个点。

这样做可以从有效区域中生成均匀分布的样本，这个过程是基于条件概率的链式法则。

Answer 5

要在这些限制条件下生成一个均匀随机的点，需要花点心思。我想到的最简单的办法就是列出所有有效的点，然后用random.choice()从这个列表中随机选择一个。这种方法会占用几MB的内存来存储列表，但生成一个点的速度非常快：

import random

screen_width = 1000
screen_height = 800
rect_x = 500
rect_y = 250
rect_width = 100
rect_height = 75

valid_points = []
for x in range(screen_width):
    if rect_x <= x < (rect_x + rect_width):
        for y in range(rect_y):
            valid_points.append( (x, y) )
        for y in range(rect_y + rect_height, screen_height):
            valid_points.append( (x, y) )
    else:
        for y in range(screen_height):
            valid_points.append( (x, y) )

for i in range(10):
    rand_point = random.choice(valid_points)
    print(rand_point)

还有一种方法是生成一个随机数，然后把它映射到屏幕上的一个有效点，这样占用的内存更少，但过程有点复杂，生成点的时间也会更长。可能还有更简洁的方法，但这里有一种使用上面提到的屏幕大小变量的做法：

rand_max = (screen_width * screen_height) - (rect_width * rect_height) 
def rand_point():
    rand_raw = random.randint(0, rand_max-1)
    x = rand_raw % screen_width
    y = rand_raw // screen_width
    if rect_y <= y < rect_y+rect_height and rect_x <= x < rect_x+rect_width:
        rand_raw = rand_max + (y-rect_y) * rect_width + (x-rect_x)
        x = rand_raw % screen_width
        y = rand_raw // screen_width
    return (x, y)

这里的逻辑有点像老式8位和16位微处理器中，如何根据x和y坐标计算屏幕地址的反向过程。变量rand_max等于有效屏幕坐标的数量。然后计算像素的x和y坐标，如果这个点在矩形内，就把它推到rand_max之上，进入第一个调用无法生成的区域。

如果你对点的均匀随机性要求不高，这个方法实现起来很简单，而且速度很快。x值是随机的，但如果选中的x在矩形的那一列，y值就会受到限制，所以矩形上方和下方的像素被选中的概率会比矩形左右的像素高：

def pseudo_rand_point():        
    x = random.randint(0, screen_width-1)
    if rect_x <= x < rect_x + rect_width: 
        y = random.randint(0, screen_height-rect_height-1)
        if y >= rect_y:
            y += rect_height
    else:
        y = random.randint(0, screen_height-1)
    return (x, y)

另一个答案是计算像素在屏幕某些区域的概率，但他们的答案还不太正确。这是一个类似的想法，先计算像素在某个区域的概率，然后再计算它在该区域内的位置：

valid_screen_pixels = screen_width*screen_height - rect_width * rect_height
prob_left = float(rect_x * screen_height) / valid_screen_pixels
prob_right = float((screen_width - rect_x - rect_width) * screen_height) / valid_screen_pixels
prob_above_rect = float(rect_y) / (screen_height-rect_height)
def generate_rand():
    ymin, ymax = 0, screen_height-1
    xrand = random.random()
    if xrand < prob_left:
        xmin, xmax = 0, rect_x-1
    elif xrand > (1-prob_right):
        xmin, xmax = rect_x+rect_width, screen_width-1
    else:
        xmin, xmax = rect_x, rect_x+rect_width-1
        yrand = random.random()
        if yrand < prob_above_rect:
            ymax = rect_y-1
        else:
            ymin=rect_y+rect_height
    x = random.randrange(xmin, xmax)
    y = random.randrange(ymin, ymax)
    return (x, y)