Jak napisać generator poziomów à la Spelunky - czyli szkoła dobrego generowania proceduralnego

(źródło: https://store.steampowered.com)

Spelunky - przyjemna platformówka, o której słyszał chyba niemal każdy. Jednym z ważniejszych elementów gameplay'u jest fakt, że wszystkie poziomy są generowanie proceduralnie / losowo - choć wyglądają tak dobrze, jakby zostały zaprojektowanie przez człowieka. Jak osiągnięto tak świetny efekt? I ważniejsze pytanie: jak osiągnąć taki efekt w swojej grze?

Zacznę od tego, że losowość jest zajebista.

Gdy ślepemu losowi oddajemy moc tworzenia naszych poziomów czy map - pozwalamy sobie, by nasza własna gra nas zaskoczyła. Dajemy procesorowi moc tworzenia wciąż nowych, nieodkrytych światów, labiryntów czy kontynentów.

I przedłużamy zabawę teoretycznie w nieskończoność.

Taka idea przyświecała od początku twórcom gier z gatunku roguelike - gdzie przemierzamy niekończące się labirynty lochów i pokonujemy potwory, a wszystko to okraszone zacną grafiką ASCII (tudzież nieco już lepszą):

(źródło: giantbomb.com)

Wszystko fajnie, wszystko cacy, ale... szybko niestety jednak pojawia się problem - który ktoś ładnie określił mianem "efektu owsianki".

Gdy każemy komputerowi zbyt często rzucać kośćmi - mieli on zawartość na drobne kawałki i miesza je ze sobą równomiernie. I cóż z tego, że każdy z nowych poziomów jest unikalny, skoro 1) nie widać w nim ludzkiej ręki, celowości, 2) wszystkie na oko wyglądają niestety tak samo albo bardzo podobnie..?

Przekonałem się o tym dobitnie, tworząc kiedyś swój własny (pierwszy) generator poziomów do pseudo-roguelike'a. Idea była prosta - kod tworzył kilka losowych pomieszczeń (o przypadkowych wymiarach i położeniu) i łączył je ze sobą jeden po drugim łamanym korytarzem - nie patrząc, czy przecina inne pomieszczenia lub korytarze.

W idei miało to tworzyć ciekawe przecięcia, nałożenia, załomy architektoniczne etc. Pomysł bardzo mi się podobał, ale dopadł mnie niestety...

Efekt owsianki

Im więcej jednak było pomieszczeń - tym bardziej "efekt owsianki" (albo nawet kaszanki) dawał o sobie znak:

Kolejne poziomy były chaotyczne, niewiele się od siebie różniły i - co najgorsze - było wyraźnie widać, że są nieudolnie generowane przez komputer - nie było w nich jakiegoś głębszego zamysłu i logiki. Ot - kupa pomieszczeń i poplątanych korytarzy.

Jakoby geometrycznie - ale jednak z dużą dozą przypadku.

Spójrzmy jednak, jak to robi wspomniany Spelunky. Poziomy, mimo że generowane proceduralnie-losowo, za każdym razem wyglądają czysto, są uporządkowane, jakby były stworzone przez istotę rozumną:

(źródło: critical-gaming.squarespace.com)

Jak to się udało? Oto sekret. Autor gry zrobił coś szalenie prostego w założeniach, a zarazem coś bardzo efektywnego. Cały poziom składa się z 16 obszarów - w formacie 4x4.

(źródło: killscreen.com)

Silnik gry generuje najpierw ścieżkę, po której powinien poruszać się gracz. Autor stworzył bogatą bazę szablonów dla każdego kafelka układanki - każdy przygotowany tak, by miał wejścia z odpowiedniej strony.

Przykładowo - kafelek nr 3 ma wejścia z góry, z lewej i z prawej, z kolei kafelek nr 2 ma z lewej, z prawej i z dołu. Oczywiście każdy szablon takiego kafelka jest przygotowany ręcznie, ale żeby nieco urozmaicić wygląd - niektóre bloki są generowane losowo - przez co nawet, gdy dany szablon kafelka się powtórzy, to nie będzie on wyglądał w 100% identycznie.

Zatem założenie jest bardzo proste - opracować ścieżkę gracza, dopasować kafelki dla schematu przejścia poziomu tak, by gracz mógł przez wysadzania ścian dotrzeć do wyjścia, a następnie wybrać z różnych szablonów gotowe wyglądy kafelek.

W efekcie każdy poziom z jednej strony jest niepowtarzalny, a z drugiej - wygląda, jakby został zaprojektowany ludzką ręką.

Wydaje się, że takie podejście jest idealnym balansem między ręcznym projektowaniem poziomów, a pozwoleniem chaosowi na wdarcie się do naszego cyfrowego świata. Powstaje nieskończenie wiele kombinacji przejść, dróg, pomieszczeń - a zarazem zachowują one ład i poczucie celowego designu.

Jak stworzyć taki generator poziomów krok po kroku:

Pokażę to na przykładzie mojego generatora map dla gry a la roguelike - a więc z rzutu od góry. Przykładowe mapy, jakie generuje program mojego pomysłu:

Jakby nie upieram się, że jest to mistrzostwo świata i nic więcej nie da się tu już poprawić - ale pomyślałem, że może komuś przydadzą się moje spostrzeżenia i doświadczenia przy budowaniu takiego generatora :)

Co więc zrobiłem?

1. Stworzyłem tzw. POKÓJ :)

Jest to nic innego jak struktura danych, która posiada 4 wyjścia (północ, południe, wschód, zachód), które są otwarte lub zamknięte (prawda / fałsz).

2. Stworzyłem siatkę pokojów 5x5

Stwierdziłem, że siatka pokojów 5x5 da mi większe pole do popisu, niż 4x4, które wydawało mi się nieco za małe. W pierwotnym stanie - wszystkie pokoje mają zamknięte wszystkie drzwi w każdym kierunku.

3. Wylosowałem ścieżkę

Komputer wybiera losowo jeden pokój, a następnie losuje kierunek wycieczki. Gdy go wybierze, otwiera drzwi w danym kierunku, a w nowym pokoju otwiera drzwi powrotne (wychodzące na pokój, z którego przyszliśmy). W przykładzie - zaczęliśmy w pokoju [1,2] i wybraliśmy kierunek na wschód:

Następnie - w kolejnym pokoju - znów losujemy kierunek - tym razem padło na północ:

Ponownie otwieramy drzwi - tym razem na północ, a w pokoju powyżej - otwieramy drzwi południowe. Potem znów losujemy kierunek - pilnując, by nie cofnąć się do pokoju, który już odwiedziliśmy (można stworzyć właściwość pokoju pt. "odwiedzony" - aby komputer odrzucał dany pokój bez sprawdzania wszystkich drzwi po kolei).

I tak dowolną liczbę razy - aż uzyskamy ścieżkę o zadowalającej nas długości:

Może się tutaj zdarzyć, że nasz "wężyk" zatnie się sam na swoim ogonie lub w kącie pomieszczenia i nie będzie już miał kierunku dalszej podróży. Wtedy można:

- anulować całą procedurę i zacząć od początku

- pozwolić ścieżce rozwiać się po swoich śladach - czyli przejść przez pokój, który już był odwiedzony

- zakończyć rozwijanie ścieżki (ja wybrałem taką opcję)

W efekcie powstała nam mapa pomieszczeń z unikalną ścieżką, która przechodzi przez część z nich. 

4. Urozmaiciłem ścieżki

Taka mapa byłaby jednak nudna, więc postanowiłem dodać procedurę, która tworzy odnogi głównej ścieżki.

Po pierwsze - losuje ona pokój, który BYŁ już odwiedzony - przykładowo:

I robi dokładnie to samo - wybiera kierunek, otwiera kolejny nieodwiedzony pokój itd.

I potem znów wybiera jakiś odwiedzony pokój:

I znów otwiera kolejne pokoje, tworząc ścieżkę:

Aby jeszcze bardziej urozmaicić wygląd labiryntu - kazałem programowi wybrać kilka dowolnych ODWIEDZONYCH pokojów i sprawdzić, czy OBOK są już odwiedzone inne pokoje - i czasem (50/50) otworzyć je - by stworzyć pętlę:

Oczywiście można łatwo bawić się ustawieniami procedur i powtórzeniami tak, aby uzyskiwać odpowiednio "gęste" rozstawienie ścieżek i pętli.

5. Określiłem typy pokoi

W efekcie powstało nam na naszej mapie aż 16 typów pokoi - które mają pootwierane i pozamykane różne przejścia:

Jak się domyślasz - każdy (no może z wyjątkiem pomieszczenia ze wszystkimi zamkniętymi drzwiami) z nich stanowi bazę do stworzenia osobnego szablonu danego kafla.

Mój generator wstępnie dopasowuje typy pokojów do rozmieszczenia na siatce:

Powstałe mapy są bardzo schludne, przejrzyste, sprawiają wrażenie zaprojektowanych świadomie :)

Niemniej ich powtarzalność byłaby po jakimś czasie nużąca. Dlatego teraz przejdziemy do wypełniania kafli odpowiednimi szablonami.

6. Stworzyłem szablony kafelków

Do tego napisałem osobny program - edytor, który pozwala szybko narysować odpowiedni kafelek. Każdy z nich ma 9x9 bloków - co pozwala się już popisać kreatywnie (jednak 7x7 było za mało).

Tutaj, jak widać, edytujemy typ kafelka "odwrócone T" - z wyjściami góra / dół / prawo.

Przy każdym takim szablonie trzeba pamiętać, żeby pozostawić wolny blok na środku ściany, która ma "otwarte drzwi":

Bo gdy już ułożymy pokoje obok siebie - to musimy mieć pewność, że będzie przynajmniej między nimi przejście szerokie na minimum jeden blok.

Tymi rzędami zer i jedynek po lewej nie przejmujcie się - to po prostu sposób, w jaki mój program zapisuje w pliku układ danego kafelka (9x9 zer lub jedynek - w zależności, czy dany blok jest ścianą czy wolnym miejscem). Dane zapisałem w zwykłym .txt :)

Jak widzisz - każdy typ kafelka ma różne szablony, spośród których program po prostu losuje jeden i wstawia na mapę tam, gdzie pasuje. I to jest ostatni podpunkt:

7. Dopasowałem szablony do kafelków do mapy

W ten sposób powstaje nieograniczona liczba możliwych do uzyskania kombinacji. Nawet, gdyby program jakimś cudem wylosował 2x taką samą ścieżkę ogólną przez pokoje wraz z odnogami i pętlami, to i tak uzupełni ją zupełnie innymi szablonami bloczków, przez co uzyska się zupełnie inną mapę i inne wrażenia.

Kombinacji jest więc nieskończenie wiele:

Jak dobrze się przyjrzysz - to zauważysz układ kafelek i skąd / dokąd mają pootwierane przejścia. Jednak celem jest zaprojektowanie takich szablonów, aby nie dało się łatwo tego odkryć i by uzyskać wrażenie maksymalnie naturalnych przejść między jednym pokojem a drugim.

Uff... było trochę roboty. Ale trzeba przyznać, że efekt jest dość porządny.

Podobnie, jak to było w przypadku Spelunky - mamy mapy dość jasne, z wyraźnie wytyczoną ścieżką, zawierające elementy symetryczne (przez co sprawiające wrażenie zaprojektowanych przez człowieka), ale jednocześnie bardzo różnorodne.

Teraz oczywiście należałoby je wypełnić potworami, znajdźkami itd. Ale to już temat na inny post :)

***

Mam nadzieję, że moje doświadczenia komuś przydadzą się w napisaniu generatora map i że może nawet ktoś ulepszy tę metodę :)

Myślę, że tan kierunek rozwoju generatorów proceduralnych map / poziomów jest bardzo przyszłościowy - stosunkowo łatwy do zaimplementowania (w przeciwieństwie do zastosowania np. aparatów komórkowych) i jednocześnie dający szybkie i ładne efekty.

Co tym myślicie? Dajcie znak w komentarzach!