Wykorzystanie L-Systems do proceduralnego generowania miast

Obecnie tworzę aplikację, która koncentruje się na treści generowanej proceduralnie. Do tej pory z powodzeniem wdrożyłem proceduralne generowanie terenu i kształtu mapy za pomocą szumu simpleks. Jestem naprawdę zadowolony z tego, jak to wygląda. Teraz próbuję zrobić to samo dla miast. Muszę tylko wygenerować dwuwymiarowy układ ulic i budynków. Zajrzałem do tego i wydaje się, że większość ludzi sugeruje używanie L-Systems. Wydaje mi się jednak, że nie mogę ich otoczyć. Dostaję koncepcję, ale nie implementację do kodu. Czy ktoś ma jakieś przykłady kodu L-Systems dla miast generowanych proceduralnie lub sugestie dotyczące innych sposobów obsługi miast?

L-Systems , z tego co mogę powiedzieć *, to zbiór zasad substytucji podobnych do gramatyki, które można stosować rekurencyjnie, aby uzyskać interesujące, „organiczne” wyniki.

Rośliny są tam, gdzie często stosowane są systemy L, ponieważ wykazują one duży wzrost rekurencyjny (tj. Gałąź dzieli się na więcej gałęzi). Dla prostego przykładu pokażę drzewo „Lollipop” wygenerowane za pomocą L-Systemu:

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)

Tak więc w pierwszej generacji mamy dopiero początek:

o
|

W 2. generacji przestrzegamy każdej z zasad i zastępujemy istniejące części zgodnie z nimi. Zastępujemy „kule” „dwoma patykami i piłkami”:

o   o
 \ /
  |

Generacja 3:

o o   o o
 \|   |/
   \ /
    |

Wkrótce będziemy mieli ładne (gówniane) duże drzewo!

Aby to zrobić w kodzie, możesz to zrobić rekurencyjnie (tj. DFS), ciągle stosując reguły dla tych samych części, aż osiągniesz dowolny arbitralny koniec, lub możesz to zrobić iteracyjnie (tj. BFS), jak to zrobiliśmy w tym przykładzie , wykonując jedną regułę „przekaż” wszystkim elementom i powtarzając szereg kroków. To jest:

Rekurencyjnie:

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

Iteracyjnie:

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

Wiele zastosowań L-Systems wykonuje krok „rozwijania się” za pomocą podziału - to znaczy, że części stają się coraz mniejsze, gdy są „hodowane”, większe części po prostu się dzielą. W przeciwnym razie Twój rosnący system może zacząć nakładać się na siebie. Zobaczysz w moim przykładzie z lizakiem, magicznie upewniłem się, że dwie gałęzie nie zachodzą na siebie przez zmianę kształtu nowych gałęzi. Zróbmy przykład miasta za pomocą podziału:

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)

Będzie to miało sens za chwilę.

Generacja 1:

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

Pojedynczy, nudny pionowy blok. (V oznacza pion.)

Generacja 2: zastępujemy pionowy blok poziomymi blokami z pionową drogą pośrodku

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

R oznacza drogę! Losowo rozłożyłem podział, nie chcemy nudnych regularnych części w PCG.

Generacja 3: zastępujemy poziome bloki pionowymi blokami oddzielonymi poziomymi drogami. Istniejące drogi pozostają; nie ma dla nich żadnych zasad.

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

Zauważ, jak drogi łączą się ze sobą, co jest miłe. Powtórz to wystarczająco dużo razy, a skończysz z czymś takim (rażąco wyrwane powiązaną odpowiedź ):

Zauważ, że jest wiele szczegółów, których nie omówiłem i że ten wynik wygląda na „oczywiście” wygenerowany - prawdziwe miasta wyglądają nieco inaczej. To sprawia, że ​​PCG jest zabawny / trudny. Istnieje wiele rzeczy, które możesz zrobić, aby poprawić i poprawić swoje wyniki, ale ponieważ nie jestem związany z L-Systems, zostawię tę odpowiedź tutaj; mam nadzieję, że to pomoże Ci zacząć.

_{* - Nie studiowałem formalnie systemów L, chociaż spotkałem określone typy, takie jak gramatyka i roślinność PCG; proszę mnie poprawić, jeśli popełniam błędy w definicjach lub pojęciach}

@ongongbongus odpowiedź jest doskonała, pozwól mi dodać kilka rzeczy.

Bloki należy podzielić na obszary budowlane zgodnie ze wszystkimi drogami, które je otaczają. Kiedy masz dookoła drogę, ogólnym wzorem jest pierścień. Zobacz ten link na przykład: http://oldurbanist.blogspot.fr/2012/01/city-blocks-spaces-in-between.html

(W zależności od gęstości, w środku pierścienia może nie być miejsca, patrz Kowloon).

Po wykonaniu bloków musisz wygenerować budynki. Są nieco trudne i wymagają generacji dwóch przebiegów. Są częściowo współzależne: twój generator nie powinien tworzyć okna, które znajduje się przed ścianą boczną następnego budynku.

I aby dodać temu życiu, możesz wpłynąć na pokolenie za pomocą takich środowisk, jak teren lub mapa ekonomiczna: Drogi (z wyjątkiem San Francisco) zwykle omijają duże wzgórza, zamiast jechać prosto, a typy domów są ciężkie pod wpływem części miasta, w której się znajdują.

baw się dobrze.