Proceduralne Komnaty: Drzewa BSP, Jaskinie Celularne i Zaszowane Chaos

Dlaczego poziomy "losowe" wymagają ziarna

Każda proceduralna loch zaczyna się od liczby. Ta liczba, ziarno, zasila generator liczb pseudolosowych — szybki, deterministyczny algorytm, taki jak mulberry32 lub xorshift32, który generuje długą sekwencję liczb wyglądających losowo, ale w pełni odtworny z tej samej początkowej wartości. Generatory nie korzystają z prawdziwej entropii systemu operacyjnego, ponieważ prawdziwa losowość unieważniłaby cel: wpisz to samo ziarno dwa razy i powinieneś otrzymać dokładnie tę samą loch, korytarz po korytarzu, pokój po pokoju.

Ta odtworzalność jest tym, co umożliwia dzielenie się ziarnem między graczami, co pozwala na codzienne wyzwanie, aby wszyscy otrzymali ten sam układ, oraz co pozwala deweloperowi odtworzyć raport o błędzie, wystarczy poprosić o ziarno, które go spowodowało. Każda decyzja dalsza — jak region jest dzielony, gdzie ląduje pokój, który wskaźnik sąsiedztwa powoduje zmianę komórki na poziom — to naprawdę kilka kolejnych liczb pobranych z tego jednego deterministycznego strumienia.

Podział Przestrzeni Binarny: Pokój z Drzewa

Podział przestrzenny binarny (BSP) rozpoczyna się od jednego dużego prostokąta reprezentującego całą mapę i rekurencyjnie dzieli go na dwie części linią współosiową, skierowaną w losowym kierunku – czasem pionową, czasem poziomą, w losowo dobranym położeniu. Każda z tych połówek jest ponownie dzielona, i tak dalej, aż obszar staje się zbyt mały, aby go podzielić, lub zostanie osiągnięty stały głębokości rekursji. Rezultatem jest drzewo binarne składające się z wkloszterowanych prostokątów, a każdy liść tego drzewa staje się pokojem: zwykle nieregularny prostokąt wyrzeźbiony nieco mniejszy niż jego obszar liścia, tak aby pokoje nie dotykały dokładnie granic ich podziału.

Połączoność wynika z tej samej struktury drzewa. Wracając wstecz od dowolnych dwóch liści-braci do ich wspólnego węzła rodzica, otrzymujemy parę pomieszczeń, które należy połączyć, więc wyżłubiono korytarz pomiędzy nimi – zwykle prosty kształt litera 'L', z jednym prostym odcinkiem poziomo i jednym pionowo. Ponieważ każdy liść jest dostępny od korzenia dzięki konstrukcji, dungeon BSP jest gwarantowany w pełni połączony i nigdy nie ma nakładających się pomieszczeń, bez konieczności sprawdzania tego aspektu.

Losowe pokoje i drzewo rozgałęzione

Luźniejszy sposób polega na rozsypaniu ustalonej liczby prostokątnych pomieszczeń bezpośrednio na mapie, w losowych rozmiarach i pozycjach, odrzucając i ponownie próbując każdego pokoju, który nakłada się na już istniejący. Po utworzeniu wystarczającej liczby pomieszczeń nadal potrzebne są korytarze, więc generator traktuje środek każdego pokoju jako węźle grafu i buduje strukturę łączącą je – dwuwymiarne trójkątanie Delauna lub po prostu minimalne drzewo rozgałęzione przechodzące przez wszystkie odległości między nimi. Następnie wyżyna się korytarz w kształcie litery L wzdłuż każdej przetrwałej krawędzi.

Czyste drzewo rozgałęzione łączy wszystko przy użyciu minimalnej liczby korytarzy, co oznacza również, że loch jest pojedynczym drzewem bez pętli – każdy szlak jest ślepym zauwój lub drogą przez tunel bez alternatywnych opcji. Generatory często dodają kilka dodatkowych krawędzi z trójkątania, które odrzuciło drzewo rozgałęzione, tworząc okazjonalne pętle, aby gracze nie byli wciągani do jednego liniowego korytarza przez cały poziom.

Automaty komórkowe: jaskinie rosnące jak żywe

Jaskinie generowane za pomocą automatów komórkowych rozpoczynają się od czystego szumu: każda komórka na siatce jest niezależnie oznaczona jako podłoga z pewnym początkowym prawdopodobieństwem, zwykle około 45%, a reszta jako ściana. Następnie stosowana jest reguła wygładzania do całej siatki jednocześnie, raz na każde pokolenie, przez kilka pokoleń - to zasadniczo ta sama idea co Gra Życia Conwaia, ale dostrojona z progiem, który sprawia, że ​​siatka zbliża się do gładkich skupień zamiast oscylować w nieskończoność.

Dla każdego pokolenia od 1 do N: dla każdej komórki (x, y) na siatce: liczba = liczba komórek PODŁOGI spośród 8 sąsiadów komórki (x, y) jeśli liczba > 4: newGrid[x][y] = PODŁOGA else if liczba < 4: newGrid[x][y] = ŚCIANA else: newGrid[x][y] = grid[x][y] // niezmienione w przypadku remisu grid = newGrid Po czterech lub pięciu generacjach szum ustabilizuje się, tworząc zaokrąglone, organicznie wyglądające jaskinie. Samo to правило nie gwarantuje, że wynik będzie jednym ciągłym obszarem - często pozostawia kilka małych, odizolowanych kieszeni - dlatego po tym wykonuje się wypełnienie strumieniem, aby znaleźć wszystkie połączone obszary, zachować tylko największy i wypełnić resztę ścianą.

for generation in 1..N:
  for each cell (x, y) in grid:
    count = number of FLOOR cells among the 8 neighbours of (x, y)
    if count > 4:
      newGrid[x][y] = FLOOR
    else if count < 4:
      newGrid[x][y] = WALL
    else:
      newGrid[x][y] = grid[x][y]   // unchanged on a tie
  grid = newGrid

Wybór metody: kontrola vs. chaos

Żaden z trzech metod nie jest w zasadzie lepszy – każda inaczej wymienia kontrolę na naturalność. Drzewo BSP gwarantuje połączenie i generuje regularne, architektonicznie sensowne pokoje, co sprawia, że nadaje się do jaskiń, budynków i stacji kosmicznych, gdzie proste ściany mają sens. Automaty komórkowe całkowicie rezygnują z tego rodzaju kontroli architektonicznej w zamian za organiczne, przypominające jaskinię kształty, których żaden człowiek nie zaprojektowałby ręcznie, ale wymagają dodatkowej operacji zapewniającej połączenie. Losowe pokoje o strukturze drzewa rozpinającego znajdują się pomiędzy nimi: nieregularne kształty i położenia pomieszczeń, jak w jaskini, ale z wyraźnym gwarantem połączenia, takim jak Drzewo BSP – rozsądny domyślny wybór, gdy ani geometria, ani szum nie spełniają dokładnie potrzeb poziomu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.