Генерировать случайное число вне диапазона в python
В настоящее время я работаю над игрой pygame, и мне нужно размещать объекты случайно на экране, за исключением того, что они не могут находиться в определенном прямоугольнике. Есть ли простой способ сделать это, а не непрерывно генерировать случайную пару координат, пока она не окажется за пределами прямоугольника?
Вот приблизительный пример того, как выглядит экран и прямоугольник.
______________
| __ |
| |__| |
| |
| |
|______________|
Если размер экрана составляет 1000x800, а прямоугольник - [x: 500, y: 250, width: 100, height: 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
Ответы
Ответ 1
Это требует некоторой мысли для создания равномерно случайной точки с этими ограничениями. Самый простой способ грубой силы, о котором я могу думать, - создать список всех допустимых точек и использовать random.choice()
для выбора из этого списка. Для этого используется несколько МБ памяти, но генерация точки очень быстрая:
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)
Логика здесь похожа на обратную сторону того, как экранные адреса вычисляются по координатам x и y на старых 8 и 16-разрядных микропроцессорах. Переменная rand_max
равна числу действительных экранных координат. Вычисляются координаты x и y пикселя, и если он находится внутри прямоугольника, пиксель выдвигается выше rand_max
, в область, которая не может быть сгенерирована с первым вызовом.
Если вы не слишком заботитесь о том, чтобы точка была случайной, это решение легко реализовать и очень быстро. Значения x являются случайными, но значение Y ограничено, если выбранный X находится в столбце с прямоугольником, поэтому пиксели выше и ниже прямоугольника будут иметь более высокую вероятность выбора, чем пиццы слева и справа от прямоугольника
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)
Ответ 2
- Разделите ящик на набор подборок.
- Среди действительных под-боксов выберите, какой из них помещает вашу точку с вероятностью, пропорциональной их областям.
- Выберите случайную точку равномерно случайным образом из выбранного суб-окна.
![random sub-box]()
Это будет генерировать выборки из равномерного распределения вероятностей в действительной области на основе цепного правила условной вероятности.
Ответ 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))
Результаты
Учитывая ограничения, описанные в 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
таким образом, чтобы каждый ящик был примерно того же размера, что и блокирующий блок. YMMV
Ответ 4
Я уже опубликовал другой ответ, который мне по-прежнему нравится, поскольку он прост и
ясно, и не обязательно медленно... во всяком случае это не совсем то, о чем попросил ОП.
Я подумал об этом, и я разработал алгоритм решения проблемы OP в пределах своих ограничений:
- разделить экран на 9 прямоугольников вокруг и содержать "отверстие".
- рассмотрим 8 прямоугольников ( "плитки" ) вокруг центрального отверстия "
- для каждого фрагмента, вычислите начало координат (x, y), высоту и площадь в пикселях
- вычислить суммарную сумму площадей плиток, а также общую площадь плиток
- для каждого извлечения, выберите случайное число от 0 до общей площади плиток (включительно и эксклюзивно)
- с использованием совокупных сумм, определяющих, в какой плите находится случайный пиксель
- с помощью
divmod
определить столбец и строку (dx, dy) в элементе
- с использованием истоков плитки в координатах экрана, вычислите случайный пиксель в координатах экрана.
Чтобы реализовать вышеизложенные идеи, в которых есть фаза инициализации, в которой мы вычисляем статические данные и фазу, в которой мы многократно используем эти данные, естественная структура данных является классом, и вот это моя реализация
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
Возможная оптимизация заключается в использовании алгоритма деления пополам, чтобы найти соответствующий фрагмент вместо более простого линейного поиска, который я реализовал.
Ответ 5
Если это генерация случайного, который вы хотите избежать, а не цикл, вы можете сделать следующее:
- Создайте пару случайных координат с плавающей запятой в [0,1]
- Масштабируйте координаты, чтобы указать точку во внешнем прямоугольнике.
- Если ваша точка находится за пределами внутреннего прямоугольника, верните ее
- Rescale для отображения внутреннего прямоугольника во внешний прямоугольник
- Перейти к шагу 3
Это будет работать лучше всего, если внутренний прямоугольник мал по сравнению с внешним прямоугольником. И это, вероятно, должно ограничиваться только прохождением цикла через некоторое количество раз, прежде чем генерировать новые случайные и повторять попытку.
Ответ 6
- определить функцию
- используйте
random.randrange
- Если обе координаты находятся в зоне отсутствия полета, вызовите рекурсивно функцию, которую вы определяете, пока не получите хороший ответ.
Вот пример кода, который вы можете адаптировать к вашим конкретным потребностям.
def good_point():
x, y = random.randrange(1000), random.randrange(800)
if 500<x<600 and 250<y<325: return good_point()
return x, y