W tym poście dla odmiany zaprezentuję kilka pseudokodów na tworzenie labiryntow. W założeniu wszystkie pola w prostokącie mają być dostępne, co najwyżej przedzielone ścianami. Zatem rozmiar tablicy na labirynt jest iloczynem dwu liczb dodatnich nieparzystych, a do każdego z pól o obu współrzędnych parzystych można dotrzeć -- indeksowanie pól od zera. Nie ma większych sal, oraz labirynt gęsto pokrywa dostępny obszar.
Klasycznie podaje się labirynt generowany za pomocą stosu -- jako przykład zastosowania stosu. Taki labirynt jest drzewem. I to jest najczęściej spotykana przeze mnie implementacja w wielu źródłach.
W takim labiryncie trudno o sekretne przejścia czy cykle. Trzeba je specjalnie tworzyć.
Labirynt oparty na liście dostępnych pól ze ścianami już podczas generowania może wygenerować ściany mogące być sekretnymi przejsciami, a nawet cykle - korytarze po których obchodzimy w kółko jakiś filar. Listę inicjujemy tylko częścią pól -- tylko tam gdzie są ściany do wyburzenia, a przy odwiedzaniu usuwamy pole z listy. Ten sposób wymaga resetów przy tworzeniu.
A pseudokody? Okazuje się, że modyfikacje są tak nieznaczne, że można opisywać je równocześnie...
Założenia: Wypełniamy obszar labiryntu ścianami, które będziemy burzyć podczas odwiedzania. Potrzebna jest dodatkowa funkcja zwracająca wektor lub pole bitowe pól odległych o dwa, czyli dwa pola obok w pionie, poziomie jako następne do zwiedzania. Wektor zwraca, czy ściany występują (pola nieodwiedzone), czy też już wyburzone (pole odwiedzone). Dlaczego nie sąsiednie? Ponieważ potrzebujemy miejsce na ewentualną ścianę, która też jest polem prostokąta. Inaczej z labiryntu utworzy się plac wypełniajacy cały obszar.
Obszar to tablica wypełniona liczbami o interpretacji np. 0 ściana widoczna, 1 ściana niewidoczna ukryta w mgle, 2 przejście widoczne, 3 przeście niewidoczne, 4 sekret nieodkryty, 5 sekret niewidoczny nieodkryty, 6 sekret odkryty widoczny...
Przy rysowaniu mapy wyświetlane tylko pola z wartościami parzystymi, a zmniejszaniem o 1 zajmie się osoba wędrująca po labiryncie odkrywajac go równocześnie.
1) Start. dla stosu oraz podczas pierwszego resetu dla list wchodzimy na pole początkowe, które odwiedzamy
2) Jesteśmy na odwiedzonym polu, odkładamy je na stos albo, w przypadku listy tuż po resecie, szukamy na liście pola, które przylega (krokiem 2) do już odwiedzonego pola. Łączymy je korytarzem, któremu można nadać status ukrytego przejścia
3) Wywołujemy funkcję zwracajacą zabudowę okolicznych pól dystansu 2
4) Losujemy kierunek, w którym pójdziemy. W przypadku stosu ograniczamy się tylko do nieodwiedzonych pól, o ile istnieją, wtedy czasem wyboru nie ma -- ślepy zaułek;
W przypadku listy z możliwymi cyklami przebijamy korytarz w wylosowanym kierunku zanim sprawdzimy wartość funkcji z 3). W końcu programistyczny kilof w garści jest labirynt[pozycja]=dostęp...
5) Gdy wylosowany kierunek wskazuje nieodwiedzone pole, odwiedzamy je niszcząc także ścianę je przedzielajacą;
gdy jednak jesteśmy na już odwiedzonym polu, w przypadku stosu zabieramy element ze szczytu by wrócić pole wcześniej; zaś w przypadku list następuje reset.
Sprawdzamy także warunek końca algorytmu: stos ma być opróżniony albo lista pól do odwiedzenia pusta, czyli albo punkt 6), albo 2) gdy coś jeszcze zostało do wyburzenia / sprawdzenia
6) Stos pusty albo lista pusta -- cały obszar jest wypełniony labiryntem.
Można dołożyć drobiazgi czyli mgła na polach (np. wartość+1), skarby, NPC, oponenci.
Kiedy implementowałem labirynty listą, okazało się, że są generowane nieco szybciej niż stosem, gdyż ten po wypełnieniu całego obszaru zwykle zawiera dużo pól. Nieodwiedzone pola wyznaczane z list były podłączane znacznie wcześniej. I nawet resetów nie było zbyt dużo.
Zaś w jednym wylosowanym przypadku napotkałem korytarz, whodzę -- sekret, mijam, kolejny sekret, i tak powstał długi korytarz wypełniony sekretnymi przejściami, widocznych już wcześniej na mapie labiryntu, ale dostępnych dopiero po znalezieniu przejścia daleko w przeciwnej części obszaru. W sam raz na znalezienie NPCa lub ukrywajacego się bandyty.
Miłego zwiedzania...
