Prozedurales Erzeugen eines Gebäudes eines bestimmten Bereichs

15

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.

user2129189
quelle

Antworten:

7

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):

Bildbeschreibung hier eingeben

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:

Bildbeschreibung hier eingeben

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:

Bildbeschreibung hier eingeben

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.

Pikalek
quelle
16

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.

congusbongus
quelle
Vielen Dank! Ich erinnere mich, dass ich darüber nachgedacht habe, aber der Gedanke, dass es eine Chance für mehrere Sekunden + Ladezeit geben könnte, hat mich gestoppt. Mir ist jetzt klar, wie unglaublich klein diese Chance ist. Ich werde das ausprobieren müssen, aber ich könnte warten, ob jemand zuerst eine direktere Lösung hat.
user2129189
@ user2129189 Wenn Sie Ihren Generator in Betrieb genommen haben, können Sie die Zufallszahlenbereiche immer noch optimieren, um zu vermeiden, dass Layouts erstellt werden, die den Test wahrscheinlich nicht bestehen. Es ist auch möglich, diesen Trial-and-Error-Generierungsalgorithmus über mehrere Kerne zu parallelisieren, indem jeder Kern jeweils ein Layout generiert.
Philipp
3
Ich selbst bin kein Fan von Methoden zur Generierung von Zurückweisungen und Wiederholungen. Sie sind schnell genug, wenn Ihr Generator nur eine einfache Sache tut, aber für Spielebenen beginnen wir normalerweise, mehr Funktionen und Generierungsschritte zu überlagern, um reichere Karten zu erstellen. Zu diesem Zeitpunkt ist die Wahrscheinlichkeit, eine tragfähige Karte zu treffen, das Produkt der Wahrscheinlichkeit, dass jeder Schritt erfolgreich ist, was schnell schrumpfen kann. Dies ist nicht nur eine akademische Angelegenheit - ich habe mit Entwicklern gesprochen, die ein System zum Zwischenspeichern von Gut / Schlecht-Samen implementieren mussten, um übermäßige Generierungszeiten zu vermeiden, wenn ein baulich korrekter Single-Pass-Generator einfacher gewesen wäre.
DMGregory
@DMGregory ja das kann ich definitiv sehen. Ein einfacher Zufallsgenerator würde in meinem Fall in wenigen Durchläufen zu 99% funktionieren, aber wenn ich später mehr Komplexität hinzufügen möchte, könnte sich dies erheblich verlangsamen. Kennt jemand irgendwelche realen Programmier- / Spieleanwendungen des Guess and Check-like-Modells?
user2129189
Möglicherweise kann es Stufen von Generationenfunktionen und -prüfungen geben, wobei darauf geachtet wird, die Formulierung der Bedingungen an das aktuelle Generationsniveau anzupassen. Auf diese Weise muss nicht das gesamte Level neu generiert werden, sondern nur der Fehler, bei dem ein Gegenstand leicht falsch platziert wurde.
Pysis
7

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.

Ryan1729
quelle
4
Ich würde die Dinge vereinfachen, indem ich immer von einem 3x3-Block aus beginne und dann 3x1-Blöcke an zufälligen Positionen hinzufüge, an denen jedes Quadrat an ein bestehendes angrenzt. Wenn Sie einen 3x3-Block hinzufügen, gibt es vier mögliche Positionen. Alle geben Ihnen einen 3x4-Block mit sechs möglichen Positionen für die nächste. Von da an wird es komplizierter, aber nicht so schlimm.
JollyJoker
0

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.

Tintenfisch
quelle
Ihre Skalierungsidee, um den gewünschten Bereich zu erhalten, ist eigentlich ziemlich clever. Ich könnte etwas Leises wie dieses implementieren.
user2129189