Dungeon generation algorithms

Algorytmów generujących lochy jest mnóstwo. Istnieją wręcz całe połacie algorytmów pasących się na rozległych równinach internetów.

Od prostych generujących liniowy układ pokojów jeden za drugim, po skomplikowane systemy z wbudowaną sztuczną inteligencją.

Jednakże zwykle po wybraniu konkretnego algorytmu trzeba go odpowiednio dopasować do tworzonego systemu. Dlatego traktuje się je bardziej jako podstawę/podejście niż gotowe rozwiązanie.

Zanim jednak przejdziemy do szczegółów zastanówmy się co w ogóle taki generator ma robić.

1. Generowanie połączonych ze sobą pokoi
2. Generowanie wejścia do poziomu (miejsce startowe)
3. Generowanie wyjścia z poziomu (przejście na kolejny niższy poziom)
4. Wszystkie pomieszczenia muszą być osiągalne przez gracza

Punkt 4 jest tu szczególnie ważny. Pokoje muszą być sensownie połączone – czysta losowość odpada z miejsca.

Omówmy zatem kilka popularnych podejść:

• Losowanie gotowych fragmentów
• Automat komórkowy
• Binary space partitioning

Losowanie gotowych fragmentów

Bardzo popularny pomysł. Najczęściej występuje w kombinacji z innymi algorytmami.
Idea polega na stworzeniu X – elementowego zestawu gotowych pokoi, wylosowaniu określonej liczby z nich a następnie połączeniu ich razem.

Najbardziej to widać w gatunku hack’n’slash – Diablo 3 będzie tu świetnym przykładem.

Automat komórkowy

Pomysł zaczerpnięty z popularnej gry w życie opartej na automatach komórkowych.
Plansza jest podzielona na komórki gdzie każda z nich ma taki sam zestaw zachowań.
Komórka ginie jeżeli ma za dużo żyjących sąsiadów bądź za mało.

Zachowania możemy modelować dowolnie; komórki mogą ginąć, rodzić się itp..
Następnie ustawiamy liczbę przebiegów algorytmu i w każdym z nich sprawdzamy wszystkie komórki względem zasad.

Przy odpowiedniej konfiguracji możemy wymodelować zachowanie przypominające normalne układy skalne. Czyli komórki z małą ilością sąsiadów giną a te z dużą zaczynają się powiększać.
Generuje nam to wtedy:


Binary space partitioning

Jeden z prostszych algorytmów.
Polega on na rekursywnym dzieleniu pomieszczeń.

Główne pomieszczenie dzielimy na 2. Potem każde z nich znów na 2 i tak dalej.
Generuje nam się z tego ładne drzewo pokoi. Aby je połączyć wystarczy poprowadzić korytarze pomiędzy dziećmi (A1, A2) a potem pomiędzy A i B.

A jakie algorytmy będą implementowane w RL Engine?

Dobrze by było mieć wszystkie 🙂
Myślę, że zaczniemy od BSP a potem się zobaczy.