Verwendung von L-Systemen zur prozeduralen Generierung von Städten

Ich mache gerade eine App, die sich stark auf prozedural generierte Inhalte konzentriert. Bisher habe ich die prozedurale Generierung des Geländes und der Form einer Karte mithilfe von Simplex-Rauschen erfolgreich implementiert. Ich bin sehr zufrieden damit, wie es aussieht. Jetzt versuche ich dasselbe für Städte zu tun. Ich muss nur ein 2D-Layout der Straßen und Gebäude erstellen. Ich habe es mir angesehen und es scheint, dass die meisten Leute die Verwendung von L-Systemen vorschlagen. Ich kann jedoch nicht scheinen, meinen Kopf um sie zu wickeln. Ich verstehe das Konzept, aber nicht die Implementierung in Code. Hat jemand Codebeispiele für L-Systeme für prozedural generierte Städte oder Vorschläge für andere Möglichkeiten, mit den Städten umzugehen?

L-Systeme sind , soweit ich das beurteilen kann *, eine Reihe grammatikalischer Substitutionsregeln, die Sie rekursiv anwenden können, um interessante "organische" Ergebnisse zu erhalten.

In Pflanzen werden häufig L-Systeme verwendet, da sie viel rekursives Wachstum aufweisen (dh der Zweig teilt sich in mehr Zweige auf). Als einfaches Beispiel zeige ich einen "Lutscher" -Baum, der mit einem L-System generiert wurde:

variables : | o              (these are the things that will grow)
start  : o
         |                   (this is what we start with)
rules  : (o → o   o)         (these are the substitution rules that we apply
               \ /            one step at a time)

Bei Generation 1 haben wir also gerade erst den Anfang:

o
|

Bei Generation 2 folgen wir jeder der Regeln und ersetzen die vorhandenen Teile gemäß den Regeln. Wir ersetzen die "Bälle" durch "Zwei-Stöcke-und-Bälle":

o   o
 \ /
  |

Generation 3:

o o   o o
 \|   |/
   \ /
    |

Bald haben wir einen hübschen (beschissenen) großen Baum!

Um dies im Code zu tun, können Sie dies entweder rekursiv (dh DFS) tun und die Regeln kontinuierlich auf dieselben Teile anwenden, bis Sie ein beliebiges Ende erreichen, oder Sie können dies iterativ (dh BFS) tun, wie wir es in diesem Beispiel getan haben Durchführen einer Regel "Übergeben" aller Elemente und Wiederholen einer Reihe von Schritten. Das ist:

Rekursiv:

tree = start
grow(tree, start)

func grow(tree, part)
    if this part of the tree is big enough
        stop
    if part is 'o'
        replace part with 'o\/o'
        grow(tree, the left 'o')
        grow(tree, the right 'o')

Iterativ:

tree = start
for a number of iterations
    for each part in tree
        if part is 'o':
            replace with 'o\/o'

Viele Anwendungen von L-Systemen führen den Schritt "Wachsen" mithilfe der Unterteilung durch. Das heißt, die Teile werden immer kleiner, wenn sie "gewachsen" werden. Die größeren Teile werden nur geteilt. Andernfalls kann es vorkommen, dass sich Ihr wachsendes System überlappt. Sie werden in meinem Beispiel für einen Lutscherbaum sehen, dass ich auf magische Weise sichergestellt habe, dass sich die beiden Zweige in der Mitte nicht überlappen, indem ich die Form der neuen Zweige geändert habe. Lassen Sie uns tun , um die Stadt am Beispiel Unterteilung:

variables: block_vertical block_horizontal road_vertical road_horizontal
start: block_vertical
rules: (block_vertical → block_horizontal road_vertical block_horizontal)
       (block_horizontal → block_vertical road_horizontal block_vertical)

Dies wird in einer Minute Sinn machen.

Generation 1:

+--------------------+
|                    |
|                    |
|                    |
|        V           |
|                    |
|                    |
|                    |
+--------------------+

Ein einzelner, langweiliger vertikaler Block. (Das V steht für vertikal.)

Generation 2: Wir ersetzen den vertikalen Block durch horizontale Blöcke durch eine vertikale Straße in der Mitte

+--------------------+
|       r            |
|       r            |
|       r            |
|   H   r      H     |
|       r            |
|       r            |
|       r            |
+--------------------+

Das r steht für Straße! Ich habe die Aufteilung zufällig verteilt, wir wollen keine langweiligen regulären Teile in PCG.

Generation 3: Wir ersetzen die horizontalen Blöcke durch vertikale Blöcke, die durch horizontale Straßen getrennt sind. Die vorhandenen Straßen bleiben erhalten; Es gibt keine Regeln für sie.

+--------------------+
|   V   r            |
|       r            |
|rrrrrrrr            |
|       r      V     |
|   V   r            |
|       rrrrrrrrrrrrr|
|       r      V     |
+--------------------+

Beachten Sie, wie die Straßen miteinander verbunden sind, was sehr schön ist. Wiederholen Sie dies oft genug und Sie werden am Ende so etwas haben ( eine verwandte Antwort wurde offensichtlich abgezockt ):

Beachten Sie, dass es viele Details gibt, die ich nicht behandelt habe, und dass dieses Ergebnis "offensichtlich" generiert aussieht - echte Städte sehen etwas anders aus. Das macht PCG Spaß / schwer. Es gibt endlose Dinge, die Sie tun können, um Ihre Ergebnisse zu optimieren und zu verbessern. Da ich jedoch nichts mit L-Systems zu tun habe, lasse ich diese Antwort hier. Ich hoffe, dies hilft Ihnen beim Einstieg.

_{* - Ich habe L-Systems nicht offiziell studiert, obwohl ich auf bestimmte Typen wie Grammatik und PCG-Vegetation gestoßen bin. Bitte korrigieren Sie mich, wenn ich falsche Definitionen oder Konzepte habe}

@ Kongusbongus Antwort ist ausgezeichnet, lassen Sie mich ein paar Dinge hinzufügen.

Blöcke müssen entsprechend allen Straßen, die sie begrenzen, in Gebäudebereiche aufgeteilt werden. Wenn Sie ringsum eine Straße haben, ist das Gesamtmuster ein Ring. Siehe diesen Link zum Beispiel: http://oldurbanist.blogspot.fr/2012/01/city-blocks-spaces-in-between.html

(Abhängig von der Dichte ist möglicherweise kein Platz in der Ringmitte vorhanden, siehe Kowloon).

Sobald Sie die Blöcke fertig haben, müssen Sie die Gebäude generieren. Sie sind etwas knifflig und erfordern eine Generierung mit zwei Durchgängen. Sie sind teilweise voneinander abhängig: Ihr Generator sollte kein Fenster vor der nächsten Gebäudeseitenwand erstellen.

Und um dem Leben hinzuzufügen, möchten Sie vielleicht die Generation mit Umgebungen wie dem Gelände oder einer Wirtschaftskarte beeinflussen: Straßen (außer in San Francisco) neigen dazu, große Hügel zu umrunden, anstatt geradeaus zu fahren, und die Haustypen sind stark beeinflusst von dem Teil der Stadt, in dem sie sich befinden.

habe Spaß.