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ć.
- Generowanie połączonych ze sobą pokoi
- Generowanie wejścia do poziomu (miejsce startowe)
- Generowanie wyjścia z poziomu (przejście na kolejny niższy poziom)
- 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.
Be First to Comment