¿Cómo puedo colocar al azar varias rectas no chocar?

Question

Estoy trabajando en algunos juegos 2D con Pygame. Necesito colocar varios objetos al mismo tiempo al azar sin ellos intersección . He intentado algunos métodos obvios pero no lo hicieron el trabajo.

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 se llevó para siempre.

Otro método Traté:

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

Este método devuelve listas vacías cerca.

Estoy tratando con una lista que es entre 2 - 20 objetos de gran tamaño. ¿Alguna sugerencia?

EDIT:. Los rectángulos son todos los tamaños aleatorios diferentes

Answer 1

He cambiado mi respuesta un poco para hacer frente a su pregunta de seguimiento sobre si podría modificarse para generar en lugar aleatorio no chocar cuadrados en lugar de rectángulos arbitrariamente. Hice esto en la forma más sencilla que pude que trabajaría, que era a la post-procesar la salida rectangular de mi respuesta original y convertir su contenido en sub-regiones cuadradas. También he actualizado el código de visualización opcional para mostrar ambos tipos de salida. Obviamente este tipo de filtrado podría extenderse a hacer otras cosas como insetting cada rectángulo o cuadrado ligeramente para evitar que se toquen entre sí.

Mi respuesta evita hacer lo que muchas de las respuestas que habían puesto a hacer - es decir, generar aleatoriamente rectángulos al tiempo que rechaza cualquier que chocan con los ya creados - porque suena inherentemente algo lento y computacionalmente desperdicio. En su lugar, sólo se concentra en la generación de los que no se solapen en el primer lugar.

Eso hace que lo que hay que hacer relativamente simple al convertirlo en un problema subdivisión área que se puede hacer muy rápidamente. A continuación se muestra una implementación de cómo esto podría hacerse. Se inicia con un rectángulo que define el límite exterior que se divide en cuatro rectángulos más pequeños que no se solapan. Esto se logra mediante la elección de un punto interior semi-aleatoria y su uso junto con los cuatro puntos de las esquinas existentes del rectángulo exterior para formar los cuatro subsecciones.

La mayor parte de la acción tendrá lugar en thequadsect()function. La elección del punto interior es crucial para determinar cuáles son las miradas de salida gusta. Puede restringir la forma que desee, por ejemplo, sólo seleccionando uno que daría lugar a sub-rectángulos de al menos una cierta anchura mínima o altura o no más grande que una cierta cantidad. En el código de ejemplo en mi respuesta, se define como el punto central ± ¹ / ₃ de la anchura y la altura del rectángulo exterior, pero básicamente cualquier punto interior trabajaría para en algún grado.

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

Para ayudar a visualizar los resultados de este enfoque, no hay un código que no sea esencial en el módulo mismo fin que los usos thePIL (Python Imaging Library) para crear un archivo de imagen que muestra los rectángulos generados durante algunas pruebas de funcionamiento que hice.

De todos modos, aquí está la versión más reciente de los ejemplos de código y 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'

Salida de muestra 1

Salida de muestra 2

Answer 2

Tres ideas de:

Disminuir el tamaño de los objetos

El primer método falla porque golpear una matriz aleatoria de 20 objetos que no se solapan es altamente improbable (en realidad (1-p)^20, donde 0<p<1 es la probabilidad de que dos objetos en colisión). Si usted podría drásticamente (órdenes de magnitud del drama) disminuir su tamaño, que podría ayudar.

los escoge 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 su rendimiento, ya que tiene una sola intersección no le obligan a generar un conjunto completamente nuevo, sólo para recoger un único rectángulo diferente.

Pre-cálculo

¿Con qué frecuencia va a usar estos conjuntos en su juego? Usando un conjunto diferente cada segundo es un escenario diferente que el uso de un conjunto una vez en una hora. Si usted no utiliza estos conjuntos con demasiada frecuencia, pre-Calcular el conjunto suficientemente grande s para que el jugador probablemente nunca ver el mismo conjunto dos veces. Cuando pre-cálculo, no se preocupan demasiado por el tiempo (lo que incluso puede usar su primer algoritmo ineficiente).

Incluso si realmente necesita estos rectángulos en tiempo de ejecución, que podría ser una buena idea para ellos calcular un poco antes de que los necesite, cuando la CPU está inactivo por alguna razón, por lo que siempre tendrá un conjunto listo en mano.

En tiempo de ejecución, sólo debes elegir un conjunto al azar. Este es probablemente el mejor enfoque para el juego en tiempo real.

Nota: Esta solución da por supuesto que los rectángulos se mantienen de una manera que ahorra espacio, por ejemplo, pares de coordenadas (x, y). Estos pares consumen muy poco espacio, y en realidad se puede ahorrar miles, e incluso millones, en un archivo con un tamaño razonable.

Enlaces útiles:

• lugar al azar rectángulos que no se solapan en un panel
• minimización superposición en rectángulos aleatorios

Answer 3

Hay una aproximación muy sencilla a su problema que funcionaba bien para mí:

• Definir una cuadrícula. Por ejemplo, un 100 escrituras cuadrícula de píxeles (x, y) -> (int (x / 100), int (y / 100)). Los elementos de la red no se superponen.
• o bien poner cada objeto en una cuadrícula diferente (al azar dentro de la cuadrícula se verá más bonito), o bien poner al azar un par de objetos en cada cuadrícula, si se puede permitir que unos pocos objetos de superposición.

I usó este para generar aleatoriamente un mapa 2D (Zelda similares). imágenes mis objetos son más pequeños que <100 * 100>, por lo que utiliza la rejilla de tamaño <500 * 500> y se dejó durante 1-6 objetos en cada cuadrícula.

Answer 4

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)

Asumo que ya tiene las funciones create_object() y collides()

También puede que tenga que reducir el tamaño de las rectas si este bucles demasiadas veces

Answer 5

¿Usted intentó:

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 volver a crear toda la lista, o la obtención de todo lo que está involucrado en una colisión.

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

1) Encontrar el centro de la región de intersección, y ajustar la esquina apropiada de cada rect intersección a ese punto, de manera que ahora se tocan en la esquina / borde en lugar de intersección.

2) Cuando un rectángulo choca con algo, generar aleatoriamente un sub-región de ese rectángulo y tratan de que en lugar.

Answer 6

un pseudocódigo alternativa, de 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 por el estilo.

Sin embargo, esto tiene la ventaja de la posibilidad de la creación de algunos de los objetos más pequeños de lo previsto, y la creación de objetos que casi se cruzan (es decir, tacto).

Si se trata de un mapa para que el jugador de recorrido, aún pueden no ser capaces de atravesar porque su camino podría ser bloqueado.

Answer 7

En mi caso he tenido un problema similar, excepto que tuve algunos rectángulos pre-sale de dentro del rectángulo en general. Así que los nuevos rectángulos tuvieron que ser colocado alrededor de los ya existentes.

I utilizó un enfoque codiciosos:

• Rectangularize el rectángulo global (global): crear una cuadrícula de la ordenada x y ordenada coordenadas y de todos los rectángulos hasta ahora. Por lo que le dará una rejilla irregular (pero rectangular).
• Para cada celda de la cuadrícula calcular el área, esto le da una matriz de áreas.
• Kadanes 2D algoritmo para encontrar la matriz de sub que proporciona la máxima área (= el rectángulo más grande libre)
• coloca un rectángulo aleatoria de modo que el espacio libre
• Repetir

Esto requiere una conversión de su original, espacio de coordenadas a / desde el espacio de parrilla, pero sencillo de hacer.

(Nota que la ejecución de Kadene directamente sobre el original, rectángulo mundial lleva a larga. Yendo a través de una aproximación rejilla está bastante rápido para mi aplicación)