python - for - ¿Cómo puedo colocar aleatoriamente varias rectas sin colisiones?

sprites for pygame

Question

Estoy trabajando en algunos juegos en 2D con Pygame. Necesito colocar varios objetos al mismo tiempo al azar sin que se crucen . He intentado algunos métodos obvios pero no funcionaron.

Los métodos obvios siguen (en pseudo):

create list of objects
for object in list:
    for other object in list:
        if object collides with other object:
            create new list of objects

Ese método tomó por siempre.

Otro método que probé:

create list of objects
for object in list:
    for other object in list:
        if object collides with other object:
             remove object from list

Ese método regresó cerca de listas vacías.

Estoy lidiando con una lista que tiene entre 2 y 20 objetos grandes. ¿Alguna sugerencia?

EDIT: los rectángulos son todos diferentes tamaños al azar.

Answer 1

Has probado:

Until there are enough objects:
    create new object
    if it doesn''t collide with anything in the list:
        add it to the list

No tiene sentido recrear la lista completa, o sacar todo lo que está involucrado en una colisión.

Otra idea es "arreglar" las colisiones mediante cualquiera de los siguientes enfoques:

1) Encuentre el centro de la región de intersección, y ajuste la esquina apropiada de cada rect de intersección a ese punto, de modo que ahora toquen la esquina / borde en lugar de intersecarse.

2) Cuando un rectángulo colisiona con algo, genere al azar una subregión de ese rectángulo y pruebe eso en su lugar.

Answer 2

un pseudocódigo alternativo, a los ya mencionados:

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

O algo así.

Pero esto tiene la ventaja de, posiblemente, crear algunos objetos más pequeños de los que pretendía y crear objetos que casi se cruzan (es decir, tocar).

Si se trata de un mapa que el jugador puede recorrer, es posible que aún no pueda atravesarlo porque su ruta podría estar bloqueada.

Answer 3

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)

Supongo que ya tiene las create_object() y create_object()

También es posible que necesite disminuir el tamaño de las rectas si esto se repite demasiadas veces

Answer 4

Hay una aproximación muy simple a su problema que funcionó bien para mí:

• Definir una grilla Por ejemplo, una cuadrícula de 100 píxeles escribe (x, y) -> (int (x / 100), int (y / 100)). Los elementos de la grilla no se superponen.
• Ponga cada objeto en una cuadrícula diferente (al azar dentro de la cuadrícula se verá más bonito), o bien coloque aleatoriamente algunos objetos en cada cuadrícula, si puede permitir que algunos objetos se superpongan.

Usé esto para generar aleatoriamente un mapa 2D (como Zelda). Las imágenes de mis objetos son menores que <100 * 100>, por lo que utilicé una cuadrícula de tamaño <500 * 500> y se permitieron 1-6 objetos en cada cuadrícula.

Answer 5

He cambiado un poco mi respuesta para abordar su pregunta de seguimiento sobre si podría modificarse para generar cuadrados aleatorios que no colisionen en lugar de arbitrariamente rectángulos. Hice esto de la manera más simple posible que funcionaría, que era postprocesar la salida rectangular de mi respuesta original y convertir su contenido en subregiones cuadradas. También actualicé el código de visualización opcional para mostrar ambos tipos de resultados. Obviamente, este tipo de filtrado podría extenderse para hacer otras cosas, como insertar cada rectángulo o cuadrado ligeramente para evitar que se toquen entre sí.

Mi respuesta evita hacer lo que hacen muchas de las respuestas ya publicadas, es decir, generar rectángulos aleatoriamente al tiempo que se rechaza cualquiera que colisione con los que ya se crearon, porque suena intrínsecamente algo lento y desperdicio computacional. En cambio, se concentra en generar solo aquellos que no se superponen en primer lugar.

Eso hace que lo que se debe hacer sea relativamente simple convirtiéndolo en un problema de subdivisión de área que se puede hacer muy rápidamente. A continuación hay una implementación de cómo se podría hacer esto. Comienza con un rectángulo que define el límite exterior que divide en cuatro rectángulos pequeños que no se superponen. Esto se logra eligiendo un punto interior semialeatorio y usándolo junto con los cuatro puntos de esquina existentes del rectángulo externo para formar las cuatro subsecciones.

La mayor parte de la acción tiene lugar en la función quadsect() . La elección del punto interior es crucial para determinar cómo se ve la salida. Puede restringirlo de la forma que desee, como seleccionar solo uno que dé como resultado rectángulos de al menos un ancho o alto mínimo determinado o no mayor que una cierta cantidad. En el código de muestra en mi respuesta, se define como el punto central ± 1/3 del ancho y la altura del rectángulo externo, pero básicamente cualquier punto interior funcionaría hasta cierto punto.

Dado que este algoritmo genera sub-rectángulos muy rápidamente, está bien pasar algún tiempo computacional determinando el punto de división interior.

Para ayudar a visualizar los resultados de este enfoque, al final hay un código no esencial que usa el módulo PIL (Biblioteca de imágenes de Python) para crear un archivo de imagen que muestre los rectángulos generados durante algunas ejecuciones de prueba que realicé.

De todos modos, aquí está la última versión del código y muestras de salida:

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''

Muestra de salida 1

Muestra de salida 2

Answer 6

Tres ideas:

Disminuye el tamaño de tus objetos

El primer método falla porque golpear una matriz aleatoria de 20 objetos no superpuestos es altamente improbable (en realidad (1-p)^20 , donde 0<p<1 es la probabilidad de que dos objetos colisionen). Si pudiera dramáticamente (drama de órdenes de magnitud) disminuir su tamaño, podría ayudar.

Elija uno por uno

La mejora más obvia sería:

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)

Esto mejoraría en gran medida tu rendimiento, ya que tener una sola intersección no te obligará a generar un conjunto completamente nuevo, solo para elegir un único rectángulo diferente.

Cálculo previo

¿Con qué frecuencia usarás estos juegos en tu juego? Usar un conjunto diferente cada segundo es un escenario diferente que usar un conjunto una vez cada hora. Si no usa estos conjuntos con demasiada frecuencia, precalcule lo suficientemente grande como para que el jugador probablemente nunca vea el mismo conjunto dos veces. Al realizar el cálculo previo, no le importa demasiado el tiempo que pasa (por lo que incluso puede usar su primer algoritmo ineficiente).

Incluso si realmente necesita estos rectángulos en tiempo de ejecución, podría ser una buena idea calcularlos un poco antes de que los necesite, cuando la CPU esté inactiva por alguna razón, para que siempre tenga un juego listo en la mano.

En tiempo de ejecución, simplemente elige un conjunto al azar. Este es probablemente el mejor enfoque para los juegos en tiempo real.

Nota: Esta solución asume que los rectángulos se guardan en una forma que ahorra espacio, por ejemplo, pares de (x, y) coordenadas. Estos pares consumen muy poco espacio, y en realidad se pueden guardar miles, e incluso millones, en un archivo de tamaño razonable.

Enlaces útiles:

• Coloque rectángulos aleatorios que no se superpongan en un panel
• minimizando la superposición en rectángulos aleatorios

Answer 7

En mi caso, tuve un problema similar, excepto que tenía algunos rectángulos de pre-salida dentro del rectángulo general. Entonces, se tuvieron que colocar nuevos rectángulos alrededor de los existentes.

Utilicé un enfoque codicioso:

• Reorganiza el rectángulo general (global): crea una cuadrícula a partir de las coordenadas x ordenadas y ordenadas de todos los rectángulos hasta ahora. Entonces eso le dará una cuadrícula irregular (pero rectangular).
• Para cada celda de la grilla calcule el área, esto le da una matriz de áreas.
• Usa el algoritmo 2D de Kadanes para encontrar la matriz secundaria que te da el área máxima (= el rectángulo libre más grande)
• Coloque un rectángulo al azar en ese espacio libre
• Repetir

Esto requiere una conversión de su espacio de coordenadas original a / desde el espacio de la cuadrícula pero fácil de hacer.

(Tenga en cuenta que ejecutar Kadene directamente en el rectángulo original original lleva demasiado tiempo. Ir por una aproximación de cuadrícula es bastante rápido para mi aplicación)