Comment puis-je placer au hasard plusieurs rectors non-collisions?

Un pseudocode alternatif, à ceux déjà mentionnés: xxx

ou quelque chose comme ça.

Mais cela a l'avantage de créer éventuellement de créer des objets plus petits que vous ne vouliez et créer des objets qui se croisent presque (c.-à-d. Touch).

Si c'est une carte pour le joueur de traverser, ils ne pourront toujours pas le traverser parce que leur chemin pourrait être bloqué.

J'ai changé ma réponse un peu pour répondre à votre question de suivi sur le point de savoir s'il pourrait être modifié pour générer au lieu de générer des carrés de non-collision aléatoires des carrés em> plutôt que des rectangles arbitrairement. Je l'ai fait de la manière la plus simple que je puisse travailler, qui devait poster la production rectangulaire de ma réponse originale et transformer son contenu en sous-régions carrées. Je également mis à jour le code de visualisation en option pour montrer les deux types de sortie. Évidemment, ce type de filtrage pourrait être étendu pour faire d'autres choses comme l'instar de chaque rectangle ou de la place légèrement pour les empêcher de se toucher.

Ma réponse évite de faire ce que bon nombre des réponses déjà publiées - qui génèrent des rectangles tout en générant au hasard. rejeter toutes celles qui entrent en collision avec tout déjà créé - parce que cela semble intrinsèquement lent et informatiquement gaspillage. Mon approche se concentre à la place pour générer uniquement ceux qui ne se chevauchent pas en premier lieu. P>

qui doit être fait relativement simple en le transformant en un simple problème de subdivision de surface qui peut être effectué très rapidement. Vous trouverez ci-dessous une implémentation de la manière dont cela peut être fait. Elle commence par un rectangle définissant la limite extérieure qui la divise en quatre petits rectangles ne se chevauchent pas. Cela est accompli en choisissant un point intérieur semi-aléatoire et l'utiliser en même temps que les quatre points d'angle existants du rectangle extérieur pour former les quatre sous-sections. P>

La plupart du lieu de prendre d'action dans le quadsect () code> fonction. Le choix du point intérieur est crucial pour déterminer ce que ressemble à la sortie. Vous pouvez contraindre comme vous le souhaitez, par exemple que la sélection qui se traduirait par des sous-rectangles d'au moins une certaine largeur minimale ou à la hauteur ou pas plus grand que une certaine quantité. Dans le code échantillon dans ma réponse, il est défini comme étant le point central  ± 1 sup> / 3 sub> de la largeur et la hauteur du rectangle extérieur, mais au fond tout point intérieur fonctionnerait Dans une certaine mesure. P>

Étant donné que cet algorithme génère des sous-rectangles très rapidement, il est correct de passer du temps de calcul déterminant le point de division intérieure. P>

Pour visualiser les résultats de cette approche, il y a un code non essentiel à la fin que les utilisations du module PIL code> (Python Imaging Library) pour créer un fichier image affichant les rectangles générés au cours de certaines courses d'essai j'ai fait. p>

Quoi qu'il en soit, voici la dernière version du code et des échantillons de sortie: p>

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'