在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. 将框分成一组子框.
2. 在有效的子框中,选择哪一个放置您的点,概率与其面积成比例
3. 从所选子框内随机选择一个随机点.

这将基于条件概率的链规则从有效区域上的均匀概率分布生成样本.

Answer 2

这在时间和内存方面提供了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))

结果

考虑到OP中概述的约束,这实际上根据需要在指定的矩形(红色)周围产生随机坐标(蓝色),但是省略了矩形之外的任何有效点但是落在相应的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个点来说明点的均匀放置(覆盖框'边界的点是由于点大小).

免责声明:请注意,该地块则以红色框的正中央这样top/bottom,left/right有彼此之间具有相同的概率.因此,调整相对于阻塞框,但不是针对图的所有区域.最终解决方案需要分别调整每个概率的概率.

更简单的解决方案,但略有修改的问题

事实证明,调整坐标系不同区域的概率非常棘手.经过一番思考后,我想出了一个略微修改过的方法:

实现在任何2D坐标系上,阻挡矩形将该区域划分为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 3

我已经发布了一个我仍然喜欢的不同答案,因为它简单明了,并不一定很慢......无论如何,这并不是OP所要求的.

我想到了它,我设计了一个算法来解决他们的约束中的OP问题:

1. 将屏幕分成9个矩形并包含"洞".
2. 考虑中心孔周围的8个矩形("瓷砖")
3. 对于每个图块,计算原点(x,y),高度和面积(以像素为单位)
4. 计算平铺区域的累积总和,以及平铺的总面积
5. 对于每次提取,选择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 4

需要一些思考来生成具有这些约束的均匀随机点.我能想到的最简单的蛮力方法是生成所有有效点的列表,并使用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值会受到约束,因此矩形上方和下方的像素将被选择的概率高于矩形左侧和右侧的pizels :

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)