Как я могу случайно разместить несколько не сталкивающихся прямоугольников?

Я работаю над 2D-играми с Pygame. Мне нужно разместить сразу несколько объектов в случайном порядке без их пересечения . Я попробовал несколько очевидных методов, но они не сработали.

Очевидные методы следуют (в псевдо):

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 объектов. Какие-либо предложения?

EDIT: прямоугольники имеют разные размеры.

    Я немного изменил свой ответ, чтобы ответить на ваш вопрос о том, можно ли его изменить, вместо этого создавайте случайные не сталкивающиеся квадраты, а не произвольные прямоугольники. Я сделал это самым простым способом, который мог бы работать, что должно было выполнить обработку прямоугольного вывода моего исходного ответа и превратить его содержимое в квадратные подрегионы. Я также обновил дополнительный код визуализации, чтобы показать оба вида вывода. Очевидно, что такая фильтрация может быть расширена, чтобы делать другие вещи, такие как вставка каждого прямоугольника или квадрата, чтобы они не касались друг друга.

    Мой ответ позволяет избежать того, что многие из уже опубликованных ответов – случайным образом генерировать прямоугольники, отвергая любые конфликты с уже созданными, потому что это звучит по своей сути несколько медленным и вычислительно расточительным. Вместо этого он концентрируется только на генерирующих, которые не перекрываются в первую очередь.

    Это делает то, что нужно сделать относительно просто, превратив его в проблему разбиения области, которая может быть выполнена очень быстро. Ниже приведена одна реализация того, как это можно сделать. Он начинается с прямоугольника, определяющего внешнюю границу, которую он делит на четыре меньших неперекрывающихся прямоугольника. Это достигается путем выбора полуслучайной внутренней точки и использования ее вместе с четырьмя существующими угловыми точками внешнего прямоугольника для формирования четырех подразделов.

    Большая часть действия quadsect() функции quadsect() . Выбор внутренней точки имеет решающее значение для определения того, как выглядит вывод. Вы можете ограничить его любым способом, например, выбрать только тот, который приведет к появлению суб-прямоугольников, по крайней мере, определенной минимальной ширины или высоты или не больше, чем какая-либо сумма. В примере кода в моем ответе он определяется как центральная точка ± 1/3 ширины и высоты внешнего прямоугольника, но в основном любая внутренняя точка будет работать в некоторой степени.

    Поскольку этот алгоритм очень быстро генерирует суб-прямоугольники, вполне можно потратить некоторое вычислительное время, определяющее внутреннюю точку деления.

    Чтобы визуализировать результаты этого подхода, в самом конце есть некоторые несущественные коды, которые используют модуль PIL (Python Imaging Library) для создания файла изображения, отображающего прямоугольники, созданные во время некоторых тестовых прогонов, которые я сделал.

    Во всяком случае, вот последняя версия кода и выходных образцов:

     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

    второе выходное изображение выборки

    Три идеи:

    Уменьшить размер ваших объектов

    Первый метод терпит неудачу, поскольку попадание случайного массива из 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) 

    Это значительно улучшило бы вашу производительность, поскольку наличие одного пересечения не заставит вас генерировать совершенно новый набор, просто чтобы выбрать другой отдельный прямоугольник.

    Предварительное вычисление

    Как часто вы будете использовать эти наборы в своей игре? Использование другого набора каждую секунду – это другой сценарий, чем использование набора один раз в час. Если вы не используете эти наборы слишком часто, предварительно вычислите s достаточно большой набор, чтобы игрок, возможно, никогда не увидит тот же набор дважды. При предварительном вычислении вам не очень-то нужно потратить время (так что вы даже можете использовать свой неэффективный первый алгоритм).

    Даже если вы действительно нуждаетесь в этих прямоугольниках во время выполнения, может быть хорошей идеей рассчитать их немного до того, как они вам понадобятся, когда CPU по какой-то причине простаивает, так что вы всегда будете иметь готовый набор.

    Во время выполнения просто выберите набор случайным образом. Это, вероятно, лучший подход для игр в реальном времени.

    Примечание. Это решение предполагает, что прямоугольники сохраняются экономно, например, пары координат (x, y) . Эти пары потребляют очень мало места, и вы действительно можете сэкономить тысячи и даже миллионы в файле с разумным размером.

    Полезные ссылки:

    • Поместите случайные неперекрывающиеся прямоугольники на панели
    • минимизация перекрытия в случайных прямоугольниках

    Существует очень простое приближение к вашей проблеме, которая отлично подходит для меня:

    • Определите сетку. Например, сетка с 100 пикселями записывает (x, y) -> (int (x / 100), int (y / 100)). Элементы сетки не перекрываются.
    • Либо помещайте каждый объект в другую сетку (случайно внутри сетки будет выглядеть красивее), либо случайным образом помещают несколько объектов в каждую сетку, если вы можете позволить нескольким объектам пересекаться.

    Я использовал это для случайного создания 2D-карты (например, Zelda). Изображения моих объектов меньше, чем <100 * 100>, поэтому я использовал сетку размером <500 * 500> и разрешал для 1-6 объектов в каждой сетке.

     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()

    Возможно, вам также понадобится уменьшить размер прямоугольников, если это слишком много раз

    Ты пробовал:

     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) Когда прямоугольник сталкивается с чем-то, произвольно сгенерируйте подобласть этого прямоугольника и попробуйте это вместо этого.

    альтернативный псевдокод, к уже упомянутым:

     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 

    Или что-то типа того.

    Но у этого есть преимущество, возможно, создание меньших объектов, чем вы предполагали, и создание объектов, которые почти пересекаются (т.е. касаются).

    Если это карта для прохождения игрока, они все равно не смогут пройти ее, потому что их путь может быть заблокирован.