🏗️ Generator labiryntów

To program, który przekształca siatkę komórek w połączoną sieć przejść i ścian. Ta wersja tworzy idealne labirynty, co oznacza, że między dowolnymi dwoma punktami istnieje dokładnie jedna ścieżka i nie ma zamkniętych pętli. Wynik jest matematycznie drzewem rozpinającym narysowanym na siatce.

DFS z cofaniem wykuwa długie, kręte korytarze; losowa metoda Prima rośnie od granicy i daje krótkie, rozgałęzione odnogi; Kruskal łączy losowe rozłączne regiony, tworząc jednolitą strukturę; a Wilson tworzy bezstronny labirynt, w którym każdy możliwy układ jest tak samo prawdopodobny. Wszystkie budują ten sam rodzaj labiryntu, ale o zupełnie innym charakterze wizualnym.

Kliknięcie Rozwiąż uruchamia przeszukiwanie wszerz (BFS) od komórki startowej (lewy górny róg) na zewnątrz, zapisując poprzednika każdej komórki. Ponieważ BFS eksploruje w kolejności odległości, gdy po raz pierwszy dotrze do wyjścia (prawy dolny róg), znalazł najkrótszą ścieżkę, która jest następnie odtwarzana wstecz i rysowana na zielono.

Rozmiar siatki ustawia zarówno szerokość, jak i wysokość kwadratowego labiryntu, od 5×5 do 60×60 komórek, więc łączna liczba komórek to ta wartość podniesiona do kwadratu. Prędkość odpowiada harmonogramowi kroków na klatkę (1, 1, 2, 4, 8, 15, 30, 60, 150, 500), pozwalając spowolnić wykuwanie do minimum lub ukończyć duży labirynt niemal natychmiast.

Idealny labirynt jest w pełni połączony i nie zawiera pętli, więc istnieje dokładnie jedna trasa między dowolną parą komórek. W ujęciu teorii grafów jest to drzewo rozpinające grafu siatki: każda komórka jest osiągalna, a usunięcie dowolnego przejścia rozłączyłoby labirynt.

Algorytm Wilsona wykorzystuje błądzenia losowe z usuwaniem pętli: idzie losowo od nieodwiedzonej komórki, aż trafi na istniejący labirynt, usuwając po drodze wszelkie utworzone pętle. Ta procedura losuje jednostajnie spośród wszystkich możliwych drzew rozpinających, więc każdy labirynt danego rozmiaru jest tak samo prawdopodobny. David Wilson opublikował go w 1996 roku.

Zaczyna od komórki, oznacza ją jako odwiedzoną i wielokrotnie przechodzi do losowego nieodwiedzonego sąsiada, wykuwając ścianę między nimi i odkładając komórkę na stos. Gdy komórka nie ma nieodwiedzonych sąsiadów, algorytm cofa się, zdejmując element ze stosu. Ta eksploracja w głąb daje długie, wijące się korytarze typowe dla labiryntów DFS.

Każda komórka przechowuje jednobajtową maskę bitową, w której bity reprezentują otwarte przejścia na północ, wschód, południe i zachód (wartości 1, 2, 4 i 8). Wykucie ściany ustawia odpowiedni bit w obu sąsiadujących komórkach. Renderer odczytuje te bity, aby narysować łączące mosty między komórkami, a solver odczytuje je, aby wiedzieć, które ruchy są dozwolone.

Tak. Każdy algorytm jest zaimplementowany wiernie: DFS z jawnym stosem, Prim z losową granicą, Kruskal z przetasowaną listą krawędzi i strukturą union-find, a Wilson z prawdziwymi błądzeniami losowymi z usuwaniem pętli. Solver BFS to standardowe przeszukiwanie najkrótszej ścieżki, więc podświetlona trasa zawsze jest optymalna dla idealnego labiryntu.

Algorytm Kruskala tasuje każdą ścianę i rozpatruje je pojedynczo, wykuwając ścianę tylko wtedy, gdy dwie oddzielane przez nią komórki należą do różnych regionów. Struktura union-find (zbiorów rozłącznych) śledzi, które komórki są już połączone, dzięki czemu algorytm może unikać tworzenia pętli podczas łączenia siatki w jedno drzewo.

Pojawiają się w generowaniu poziomów gier wideo i lochów, narzędziach do proceduralnego generowania treści oraz jako klasyczne przykłady dydaktyczne przeszukiwania grafów i drzew rozpinających. Te same idee rozciągają się na robotykę i trasowanie sieci, gdzie znalezienie połączonej, wolnej od pętli ścieżki przez przestrzeń ma kluczowe znaczenie.