Generator labiryntów algorytmów Ellera

Algorytm Ellera to algorytm generowania labiryntów, który efektywnie generuje idealne labirynty (labirynty bez pętli i z pojedynczą ścieżką między dowolnymi dwoma punktami) za pomocą podejścia wiersz po wierszu. Generuje on labirynty podobnie jak algorytm Kruskala, ale robi to poprzez generowanie tylko jednego wiersza na raz, bez konieczności przechowywania całego labiryntu w pamięci. Dzięki temu jest przydatny do generowania bardzo dużych labiryntów w bardzo ograniczonych systemach oraz 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ę efektywnym podejściem do generowania labiryntów wiersz po wierszu, co czyni go idealnym do tworzenia labiryntów nieskończonych lub generowanych w czasie rzeczywistym. Jest on często cytowany w literaturze poświęconej proceduralnemu generowaniu treści i generowaniu labiryntów, ale nie udało mi się znaleźć źródeł źródłowych szczegółowo opisujących jego oryginalną publikację.

Jak działa algorytm Ellera w generowaniu labiryntów

Algorytm Ellera przetwarza wiersz po wierszu, utrzymując i modyfikując zestawy połączonych komórek. Zapewnia łączność, unikając pętli i efektywnie 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 zakoń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 im ten sam identyfikator zestawu. Gwarantuje to istnienie przejść poziomych.

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 rzędu

• Aby zachować połączenia pionowe, przypisz 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ż dojdziesz 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.

Dalsza lektura

Jeśli podobał Ci się ten wpis, mogą Cię zainteresować również poniższe sugestie:

• Rekurencyjny generator labiryntu Backtracker
• Generator labiryntu algorytmów Kruskala
• Generator Labiryntu Polowanie i Zabijanie