🏰 Proceduralny generator lochów

Generowanie BSP rekurencyjnie dzieli prostokątny obszar na dwa mniejsze prostokąty, na przemian stosując cięcia poziome i pionowe, aż każdy region będzie wystarczająco mały, by pomieścić jedną komnatę. Komnata jest następnie umieszczana wewnątrz każdego węzła liścia, a komnaty są łączone prostymi lub L-kształtnymi korytarzami zgodnie z kolejnością ich utworzenia. Daje to lochy o naturalnej, drzewiastej strukturze i niewielu nakładających się komnatach, a technika ta jest jedną z najczęściej stosowanych w roguelike'ach, ponieważ gwarantuje niepokrywające się komnaty bez sprawdzania kolizji.

Generator wielokrotnie proponuje komnatę o losowej szerokości i wysokości w losowej pozycji, a następnie sprawdza ją względem każdej wcześniej umieszczonej komnaty, wykorzystując nakładanie się prostokątów osi zgodnych (z jednokafelkowym buforem). Jeśli nakłada się na istniejącą komnatę, próba jest odrzucana i podejmowana jest nowa, aż do ograniczonej liczby prób. Gdy istnieje wystarczająco dużo niepokrywających się komnat, są one łączone zachłannym łańcuchem najbliższego sąsiada — na każdym kroku najbliższa jeszcze niepołączona komnata jest dołączana do rosnącej sieci L-kształtnym korytarzem, podobnie w duchu do budowania minimalnego drzewa rozpinającego.

Jaskinia zaczyna jako siatka losowo wypełniona ścianami w wybranym procencie (35–60%). Jest następnie wygładzana przez kilka przebiegów: w każdym przebiegu każdy kafelek liczy, ile z jego 8 otaczających sąsiadów to ściany, i sam staje się ścianą, jeśli 5 lub więcej sąsiadów to ściany, w przeciwnym razie staje się podłogą. Powtarzanie tego kilka razy usuwa izolowany szum i przekształca małe skupiska ścian w gładkie, organiczne ściany jaskiń — ta sama zasada stoi za grą w życie Conwaya, zastosowaną tutaj do generowania poziomów zamiast symulowania żywych komórek.

Symulacja używa liniowego generatora kongruentnego (LCG): prostego wzoru, który wielokrotnie przekształca wewnętrzny 32-bitowy stan za pomocą mnożenia i dodawania ze stałymi współczynnikami, produkując deterministyczny strumień liczb pseudolosowych. Ponieważ generator jest resetowany do tej samej wartości ziarna za każdym razem, gdy naciśnięty zostaje przycisk „Generate”, wpisanie tego samego ziarna z tym samym algorytmem i parametrami zawsze produkuje identyczny układ lochu, dlatego pole ziarna i przycisk „New seed” pozwalają zapisać lub odtworzyć konkretną mapę.

Po wygenerowaniu lochu symulacja uruchamia przeszukiwanie wszerz (BFS) od jednego kafelka podłogi, by znaleźć najdalej osiągalny kafelek, a następnie uruchamia drugie BFS z tego kafelka, by znaleźć rzeczywistą średnicę połączonego regionu — to klasyczna technika „podwójnego BFS” do znajdowania najdłuższej najkrótszej ścieżki w nieważonym grafie. Dwa punkty końcowe stają się znacznikami startu i wyjścia, długość ścieżki między nimi jest pokazywana jako „Longest path”, a „Connectivity” pokazuje, jaki procent wszystkich kafelków podłogi jest osiągalny ze startu, co sygnalizuje, czy jaskinia lub loch ma izolowane, nieosiągalne kieszenie.