python - layereddirty - sprites draw pygame




Wie kann ich mehrere nicht kollidierende Rekruten zufällig platzieren? (5)

Ich arbeite an einigen 2D-Spielen mit Pygame. Ich muss mehrere Objekte gleichzeitig zufällig platzieren, ohne dass sie sich schneiden . Ich habe ein paar offensichtliche Methoden ausprobiert, aber sie haben nicht funktioniert.

Offensichtliche Methoden folgen (in 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

Diese Methode dauerte ewig.

Andere Methode, die ich versucht habe:

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

Diese Methode hat fast leere Listen zurückgegeben.

Ich habe es mit einer Liste zu tun, die zwischen 2 - 20 Objekte groß ist. Irgendwelche Vorschläge?

EDIT: Die Rechtecke sind alle zufällig unterschiedliche Größen.


Hast du versucht:

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

Es ist sinnlos, die gesamte Liste neu zu erstellen oder alles, was mit einer Kollision zusammenhängt, herauszunehmen.

Eine andere Idee besteht darin, Kollisionen durch einen der folgenden Ansätze zu "reparieren":

1) Finde das Zentrum des Schnittpunktbereichs und stelle die entsprechende Ecke jedes sich kreuzenden Rechtecks ​​auf diesen Punkt ein, so dass sie jetzt auf Ecke / Kante treffen, anstatt sich zu schneiden.

2) Wenn ein Rechteck mit etwas kollidiert, erzeuge zufällig eine Unterregion dieses Rechtecks ​​und versuche es stattdessen.


ein alternativer Pseudocode, zu den bereits erwähnten:

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

Oder etwas ähnliches.

Dies hat jedoch den Vorteil, dass Sie möglicherweise kleinere Objekte erstellen können, als Sie vorgesehen haben, und Objekte erstellen, die sich fast schneiden (dh berühren).

Wenn es sich um eine Karte handelt, die der Spieler durchqueren muss, können sie diese möglicherweise immer noch nicht durchqueren, da ihr Pfad blockiert werden könnte.


Es gibt eine sehr einfache Annäherung an Ihr Problem, die für mich gut funktionierte:

  • Definieren Sie ein Raster. Zum Beispiel schreibt ein 100-Pixel-Gitter (x, y) -> (int (x / 100), int (y / 100)). Die Gitterelemente überlappen nicht.
  • Entweder legen Sie jedes Objekt in ein anderes Raster (zufällig innerhalb des Rasters wird schöner aussehen), entweder fügen Sie zufällig einige Objekte in jedes Raster ein, wenn Sie zulassen, dass sich einige Objekte überlappen.

Ich habe damit zufällig eine 2D-Karte (Zelda-Like) erstellt. Die Bilder meiner Objekte sind kleiner als <100 * 100>, daher habe ich ein Gitter der Größe <500 * 500> verwendet und für 1-6 Objekte in jedem Raster erlaubt.


Ich habe meine Antwort ein wenig geändert, um Ihre Folgefrage zu beantworten, ob sie geändert werden könnte, um stattdessen zufällige nicht kollidierende Quadrate statt willkürlicher Rechtecke zu erzeugen. Ich habe das auf die einfachste Art und Weise getan, die ich hätte tun können, nämlich die rechteckige Ausgabe meiner ursprünglichen Antwort nachzubearbeiten und ihren Inhalt in quadratische Unterbereiche umzuwandeln. Ich habe auch den optionalen Visualisierungscode aktualisiert, um beide Ausgabearten anzuzeigen. Offensichtlich könnte diese Art der Filterung auf andere Dinge ausgedehnt werden, wie zum Beispiel ein Rechteck oder ein Quadrat, um zu verhindern, dass sie sich gegenseitig berühren.

Meine Antwort vermeidet zu tun, was viele der bereits geposteten Antworten tun - nämlich Zufallsrechtecke zu erzeugen, während alle abgelehnt werden, die mit denen kollidieren, die bereits erstellt wurden - weil es von Natur aus etwas langsam und rechenintensiv klingt. Stattdessen konzentriert es sich darauf, nur diejenigen zu erzeugen, die sich überhaupt nicht überschneiden.

Das macht das, was getan werden muss, relativ einfach, indem man es in ein Flächenunterteilungsproblem verwandelt, das sehr schnell durchgeführt werden kann. Im Folgenden finden Sie eine Implementierung, wie dies durchgeführt werden könnte. Es beginnt mit einem Rechteck, das die äußere Grenze definiert, die es in vier kleinere nicht überlappende Rechtecke unterteilt. Dies wird erreicht, indem ein halb zufälliger innerer Punkt ausgewählt und zusammen mit den vier vorhandenen Eckpunkten des äußeren Rechtecks ​​verwendet wird, um die vier Unterabschnitte zu bilden.

Die meisten Aktionen finden in der Funktion quadsect() . Die Wahl des inneren Punktes ist entscheidend dafür, wie die Ausgabe aussieht. Sie können es beliebig einschränken, indem Sie nur einen auswählen, der Unterrechtecke von mindestens einer bestimmten Mindestbreite oder -höhe oder nicht mehr als einem bestimmten Betrag ergeben würde. Im Beispielcode in meiner Antwort ist dieser als Mittelpunkt ± 1/3 der Breite und Höhe des äußeren Rechtecks ​​definiert, aber im Prinzip würde jeder innere Punkt in gewissem Maße funktionieren.

Da dieser Algorithmus sehr schnell Unterrechtecke erzeugt, ist es in Ordnung, eine gewisse Berechnungszeit zu verwenden, um den inneren Teilungspunkt zu bestimmen.

Um die Ergebnisse dieses Ansatzes sichtbar zu machen, gibt es am Ende einen PIL Code, der das PIL Modul (Python Imaging Library) verwendet, um eine Bilddatei zu erstellen, die die Rechtecke anzeigt, die während einiger von mir erstellter Testläufe erzeugt wurden.

Wie auch immer, hier ist die neueste Version des Codes und der Ausgabe von Beispielen:

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'

Ausgabeprobe 1

Ausgabeprobe 2


In meinem Fall hatte ich ein ähnliches Problem mit der Ausnahme, dass ich einige Rechtecke vor dem Verlassen des Rechtecks ​​hatte. Also mussten neue Rechtecke um die bestehenden herum gelegt werden.

Ich habe einen gierigen Ansatz gewählt:

  • Rechteckig das gesamte (globale) Rechteck: Erstellen Sie ein Gitter aus den sortierten x- und sortierten y-Koordinaten aller bisheriger Rechtecke. So erhalten Sie ein unregelmäßiges (aber rechteckiges) Raster.
  • Berechnen Sie für jede Gitterzelle die Fläche, damit erhalten Sie eine Matrix von Flächen.
  • Verwenden Sie den 2D- Algorithmus von Kadanes , um die Submatrix zu finden, die Ihnen die maximale Fläche bietet (= das größte freie Rechteck)
  • Platzieren Sie ein zufälliges Rechteck in diesem freien Speicherplatz
  • Wiederholen

Dies erfordert eine Konvertierung von Ihrem ursprünglichen Koordinatenraum in / aus dem Gitterraum, aber einfach zu tun.

(Beachten Sie, dass das Ausführen von Kadene direkt auf dem ursprünglichen, globalen Rechteck zu lange dauert. Das Gehen über eine Gitterapproximation ist für meine Anwendung schnell)





rect