Generator labiryntów algorytmów Ellera

Algorytm Ellera to algorytm generowania labiryntów, który wydajnie generuje idealne labirynty (labirynty bez pętli i z pojedynczą ścieżką między dwoma dowolnymi punktami) przy użyciu podejścia wiersz po wierszu. Tworzy labirynty podobne do algorytmu Kruskala, ale robi to, generując tylko jeden wiersz na raz, bez potrzeby przechowywania całego labiryntu w pamięci. Dzięki temu jest przydatny do generowania bardzo dużych labiryntów w bardzo ograniczonych systemach i do proceduralnego generowania treści.

Idealny labirynt to labirynt, w którym istnieje dokładnie jedna ścieżka z dowolnego punktu w labiryncie do dowolnego innego punktu. Oznacza to, że nie można kręcić się w kółko, ale często napotyka się ślepe zaułki, które zmuszają do zawrócenia.

Wygenerowane tutaj mapy labiryntu zawierają domyślną wersję bez pozycji początkowej i końcowej, więc możesz sam o tym zdecydować: będzie rozwiązanie z dowolnego punktu w labiryncie do dowolnego innego punktu. Jeśli chcesz się zainspirować, możesz włączyć sugerowaną pozycję początkową i końcową - a nawet zobaczyć rozwiązanie między nimi.

O algorytmie Ellera

Algorytm Ellera został wprowadzony przez Davida Ellera.

Algorytm ten wyróżnia się wydajnym podejściem wiersz po wierszu do generowania labiryntów, co czyni go idealnym do nieskończonych labiryntów lub labiryntów generowanych w czasie rzeczywistym. Jest on często cytowany w literaturze na temat proceduralnego generowania treści i generowania labiryntów, ale nie udało mi się znaleźć źródeł pierwotnych szczegółowo opisujących jego oryginalną publikację.

Jak działa algorytm Ellera w generowaniu labiryntów

Algorytm Ellera przetwarza jeden wiersz na raz, utrzymując i modyfikując zestawy połączonych komórek. Zapewnia łączność, unikając pętli i skutecznie rozszerza labirynt w dół.

Teoretycznie można go używać do generowania nieskończonych labiryntów, jednak aby mieć pewność, że wygenerowany labirynt będzie rzeczywiście rozwiązywalny, w pewnym momencie konieczne jest przełączenie się na logikę „ostatniego wiersza”, aby dokończyć labirynt.

Krok 1: Zainicjuj pierwszy wiersz

• Przypisz każdej komórce w wierszu unikalny identyfikator zestawu.

Krok 2: Połącz sąsiadujące komórki poziomo

• Losowo scal sąsiadujące komórki, ustawiając je na ten sam identyfikator zestawu. Zapewnia to, że istnieją poziome przejścia.

Krok 3: Utwórz połączenia pionowe z następnym rzędem

• W każdym zestawie pojawiającym się w rzędzie co najmniej jedna komórka musi być połączona w dół (aby zapewnić łączność).
• Wybierz losowo jedną lub więcej komórek z każdego zestawu, aby połączyć je z następnym wierszem.

Krok 4: Przejdź do następnego wiersza

• Kontynuuj połączenia pionowe, przypisując ten sam identyfikator zestawu do odpowiednich komórek poniżej.
• Przypisz nowe identyfikatory zestawów do wszystkich nieprzypisanych komórek.

Krok 5: Powtarzaj kroki 2–4, aż dotrzesz do ostatniego rzędu

• Kontynuuj przetwarzanie wiersz po wierszu.

Krok 6: Przetwórz ostatni rząd

• Upewnij się, że wszystkie komórki w ostatnim wierszu należą do tego samego zestawu, łącząc wszystkie pozostałe oddzielne zestawy.