Prozedurales Erzeugen eines Gebäudes eines bestimmten Bereichs

Ich und ein Team arbeiten an einem Fabrikbauspiel, das dem Spieler zu Beginn des Spiels eine zufällige Fabrik gibt. Um sicherzustellen, dass es ein Gefühl von "Fairness" gibt, würde die zufällig erzeugte Fabrik im Idealfall eine Fläche innerhalb weniger Einheiten von (Platzhalterwert) 30 haben.

Es ist relativ einfach, einen einfachen Zufallsgenerator für Rechtecke zu schreiben, um diese Spezifikationen zu erfüllen. Unser Ziel ist jedoch, dass die Fabrik komplexer ist, vielleicht aus 2, 3 oder sogar 4 sich überschneidenden Rechtecken besteht und komplexere Formen erzeugt (denken Sie an L, Gebäude in U- und O-Form).

Ich habe versucht, ein zufälliges Rechteck zu generieren und dann mit der Basisalgebra ein zweites Rechteck auszufüllen. Bisher hatte ich jedoch kein Glück, mehr als zwei Rechtecke zu implementieren, und auch dann bin ich mit den Ergebnissen für ein Design mit nur zwei Rechtecken nicht zufrieden .

Einige weitere relevante Informationen: 2D von oben nach unten Einige der Mechaniken sind faktoriell, sodass Räume eine angemessene Länge und Breite haben sollten, um Platz für Maschinen zu schaffen.

Danke im Voraus!

BEARBEITEN: Wenn ich "gute" oder "schlechte" Ausgaben sage, ist eine schlechte Ausgabe jede Ausgabe, deren Speicherplatz vom Player nicht genutzt werden kann. Die Fabrikform begrenzt, wo der Spieler Fabrikmaschinen wie Förderbänder platzieren kann. Idealerweise sollte die Fabrik keine Bereiche mit einer Breite von nur 1-2 Blöcken haben. Die Form sollte nicht ein oder zwei große Rechtecke mit einer Linie von 1-2 Blöcken sein, die an einer Seite "hängen". Eine gute Ausgabe wäre, wenn die gesamte Bodenfläche "bearbeitbar" ist, sodass alle Bereiche mindestens 3-4 Blöcke breit sind. Eine gute Ausgabe muss nicht immer komplex sein (1 oder 2 Rechtecke sind in Ordnung), aber es sollte eine faire Chance bestehen, wenn sie aus mehr als 1-2 Rechtecken besteht.

Sie können vorgenerierte Polyominoes als Meta-Formen verwenden, um eine Auswahl von Gebäuden zu erstellen.

Nehmen wir an, Ihr minimaler akzeptabler Abstand beträgt 3 Blöcke. Dann ist die kleinste akzeptable Gebäudeeinheit, die wir in Betracht ziehen, 3x3. Der Einfachheit halber werde ich das eine Zelle nennen und es gibt eine Fläche von 9 Blöcken. Nehmen Sie als Nächstes Ihren Zielstartbereich und teilen Sie ihn durch den Zellbereich. Unter Verwendung des von Ihnen angegebenen Startwerts erhalten wir 3.333; 3 Zellen würden Ihnen also ein bisschen weniger geben, als Sie möchten, und 4 Zellen würden Ihnen mehr geben.

Von hier aus haben Sie mehrere Möglichkeiten. Wenn Sie in Ihrem Startbereich flexibel sind, verwenden Sie die für Sie am besten geeignete Methode, um die Anzahl der Zellen zu bestimmen, mit denen Sie eine akzeptable Menge erhalten (dh auf den nächsten Wert runden, aufrunden usw.). Ich werde das die Zellenzahl nennen.

Wählen Sie als nächstes zufällig das Polyomino mit der gewünschten Zellenzahl aus. Ersetzen Sie jedes Quadrat auf dem Polyomino durch eine Gebäudezelle und Sie haben Ihre endgültige Form.

Nehmen wir zur Veranschaulichung an, wir runden ab. Hier sind alle Polyominoe der Größe 3 (ohne Rotationen / Flips):

Nehmen wir an, wir wählen zufällig die L-Form aus und wenden eine zufällige Drehung an. Ihr Gebäude würde das folgende Layout haben:

Ein paar Probleme. Erstens ist die Anzahl der Zellen, die Sie verwenden können, begrenzt. Wikipedia gibt Ihnen alle Polyomino bis zur Größe 8 ( Oktomino ). Es enthält zusammenfassende Daten für bis zu Größe 12, aber ich weiß nicht, ob es für alle eine Online-Auflistung gibt. Zweitens funktioniert die obige Lösung nur bei Gebäudegrößen, bei denen es sich um ein Vielfaches von 9 handelt. Es gibt verschiedene Möglichkeiten, um einige dieser Probleme zu umgehen:

1) Verwenden Sie eine andere Zellengröße. Zum Beispiel 3x4, 4x4 usw.

2) Füge einem Ausgangspolyomino zusätzliche Zellen hinzu. Dies kann schwierig sein, wenn Sie sicherstellen müssen, dass alle Formen gleich wahrscheinlich sind. Für die meisten Spieleentwicklungszwecke ist jedoch keine wirklich gleichmäßige Verteilung der Gebäudeformen erforderlich.

3) Ein Gebäude ausstatten, um es größer zu machen. Zurück zum Beispiel: Wenn Sie 3 Zellen verwendet hätten, hätte Ihr Gebäude eine Fläche von 27 Quadraten, so dass Sie um 3 verkürzt wären. Sie könnten dann den Umfang nach einer Stelle absuchen, an der eine Gruppe von Quadraten der Größe 1x3 aufgeklebt werden kann. Solange Ihre Make-up-Gruppe mindestens AxB ist, wobei A mindestens Ihr akzeptabler Mindestabstand ist, wird Ihr Ergebnis nicht gegen Ihre zulässige Mindestabstandsbeschränkung verstoßen. Aufbauend auf dem obigen Beispiel sehen Sie hier ein Beispiel für ein mögliches Ergebnis:

4) Anstatt ein zu kleines Gebäude auszufüllen, können Sie ein zu großes Gebäude abschneiden. Das Einhalten der Mindestabstandsbeschränkung ist komplexer als die Auffülloption, bietet jedoch mehr Alternativen.

Einige andere Kommentare:

Nur weil Sie alle möglichen Polyominos einer bestimmten Größe verwenden könnten, heißt das noch lange nicht, dass Sie es tun sollten. Wenn einige von ihnen keinen Spaß machen, brechen Sie Ihr Thema, beleidigen Sie Ihr Publikum (Hakenkreuzmuster) oder verursachen Sie ein anderes Problem, entfernen Sie sie. Sie können Ihre Auswahlroutine auch gewichten, wenn einige Muster interessant sind, aber zu seltsam, um sie routinemäßig aufzurufen. Schließlich können Sie diese Lösung in Kombination mit Ihrer aktuellen Strategie verwenden. Möglicherweise erzeugen Sie in 70% der Fälle rechteckige Gebäude und in 30% der Fälle verwenden Sie den Polyomino-Ansatz. Oder Sie beginnen mit einem rechteckigen Gebäude und kleben ein kleines Polyomino nach außen.

Eine einfache Möglichkeit, einen Prozedurgenerator zu erstellen, ist:

1. Dinge nach dem Zufallsprinzip bauen
2. Führen Sie eine Funktion aus, die überprüft, ob die Ausgabe korrekt ist
3. Wenn die Ausgabe nicht gut ist, fahren Sie mit Schritt 1 fort

Selbst wenn es Tausende von Durchläufen dauert, kommen die meisten einfachen Generatoren mit diesem Ansatz zurecht. Der Vorteil ist, dass im Generator nicht viele intelligente Funktionen erforderlich sind. Da die Überprüfung, ob etwas gut ist, viel einfacher ist als die Erstellung von 100% ig guten Funktionen, ist dieser Ansatz sehr einfach.

Sie haben einige objektive Maßnahmen aufgeführt, um festzustellen, ob eine Ausgabe gut ist. Das sollte ausreichen, um einen schnellen und schmutzigen Generator zu erstellen. Platzieren Sie Rechtecke zufällig in einem Bereich und lehnen Sie die Ausgabe ab, wenn beispielsweise Bereiche vorhanden sind, die nur 1-2 Blöcke breit sind.

Beginne damit, verbessere und optimiere danach.

Bei einer Einschränkung von "Alle Bereiche sind mindestens 3-4 Blöcke breit" ist die erste Idee, die mir in den Sinn kommt, etwa die folgende:

1. Wählen Sie eines von 3x3, 3x4, 4x3 oder 4x4
2. platziere einen Block dieser Größe in der Mitte des Gitters
3. Wähle eine Richtung (oben, links, rechts, unten)
4. Versuchen Sie, einen 3x3-Block neben zuvor platzierten Blöcken in dieser Richtung zu platzieren
5. Wenn dies erfolgreich ist, versuchen Sie mit einiger Wahrscheinlichkeit, den Block in einer der Richtungen, die Sie nicht gerade ausgewählt haben, zu einem 4x3-Block zu erweitern
6. Verschieben Sie mit einiger Wahrscheinlichkeit eine zufällige Kante der ausgefüllten Blöcke
7. Wiederholen Sie die Schritte 3 bis 6, bis der Bereich groß genug ist

Die Grundidee ist, vorausgesetzt, Sie möchten, dass alle Bereiche mindestens eine bestimmte Größe haben. Arbeiten Sie nur in Bereichen mit dieser Größe. Wenn Sie allgemein möchten, dass etwas für alle generierten Ausgaben zutrifft, prüfen Sie, ob es für alle teilweise generierten Ausgaben zutrifft.

Ziehen Sie in Betracht, Boolesche Werte NOT und UNION zu verwenden und zufällig zwischen ihnen zu wählen.

1. Platziere ein zufälliges Rechteck.
2. Platziere ein zweites zufälliges Rechteck.
3. Wählen Sie nach dem Zufallsprinzip, ob Sie sie UNIONIEREN oder die zweite von der ersten SUBTRAKTIEREN möchten.
4. Wiederholen Sie dies für eine Reihe von Rechtecken. Obwohl nur zwei oder drei vernünftig genug Ergebnisse liefern könnten.

Dann würde ich die Fläche berechnen und sie vergrößern oder verkleinern, um sie näher an die gewünschte ungefähre Größe anzupassen, und dann testen, ob es keine Abmessungen gibt, die unter einem erforderlichen Mindestbetrag liegen.