Algorytm proceduralnej mapy 2D z połączonymi ścieżkami

Problem do rozwiązania: Wygeneruj losową mapę lochów 2D dla gry opartej na kafelkach, w której wszystkie pokoje są połączone.

Szukam lepszych rozwiązań niż obecnie.

Moje obecne rozwiązanie polega na tym, że uruchamiam dwa algorytmy. Pierwszy generuje loch z pokojami. Po drugie upewnij się, że wszystkie pokoje są połączone. Jestem ciekawy, jakie mogą być inne rozwiązania. Szybsze i / lub łatwiejsze itp. Prędkość nie jest tak naprawdę problemem, ale jeśli prędkość można uzyskać bez rzeczywistych kosztów, to dobrze. Ważniejsze jest to, że ja i inni, którzy czytają, mogę nauczyć się różnych sposobów podejścia i rozwiązania problemu.

Poniżej moja obecna implementacja. Pokoje obecnie nie mają wyjść ani wyjść w żadnym 2, 3 lub 4 kierunkach.

Generowanie pokoi w lochach

Ustawienia: Ustaw bieżący pokój w lewym górnym rogu.

1. Zdobądź prawidłowy typ pokoju dla pokoju (gdzie prawidłowy typ pokoju to typ bez wyjść z lochu i który ma wyjścia pasujące do wyjść z pokoju powyżej i pokoju po lewej stronie. Wystarczy sprawdzić powyżej i do pozostawione z powodu kroku 2 poniżej).
2. Opuść pokój i przesuń współrzędną X o krok. Jeśli współrzędna x przekracza szerokość lochu, ustaw współrzędną x na 0 i przesuń współrzędną y o jeden krok. Jeśli współrzędna y przekroczy wysokość lochu, jesteśmy skończeni.
3. Powtórz od # 1.

Następnie sprawdzam, czy wszystkie pokoje są połączone. Jeśli nie wszystkie są połączone, uruchamiam drugi algorytm, który w nieseksualny, ale zdecydowanie wystarczająco dobry sposób, jeśli chodzi o układ lochów, przechodzi przez pokoje i zmienia je tak, że wszystkie kończą się być połączonym.

Sprawdzanie, czy wszystkie pokoje są połączone

Konfiguracja: Utwórz mapę 2D liczb całkowitych reprezentujących ścieżki i zainicjuj wpisy na wartość „nieprzetworzona” (jeszcze nie przetrawiona), -1. Ustaw liczbę całkowitą indeksu ścieżki początkowej, która śledzi bieżącą ścieżkę na 1. Ustaw bieżący pokój w lewym górnym rogu, dodając go do stosu pokoi do sprawdzenia.

1. Jeśli stos zawiera pokoje do sprawdzenia, należy ustawić indeks ścieżki pokoju na bieżący indeks ścieżki. Jeśli stos nie zawiera żadnych pokoi, zwiększ indeks ścieżki i spróbuj uzyskać pokój, przesuwając kolumnę po kolumnie, rząd po rzędzie, aż otrzymamy pokój, który nie został jeszcze przetworzony. Jeśli nie można znaleźć miejsca, jesteśmy skończeni.
2. Sprawdź, czy pokój ma wyjście po lewej stronie. Jeśli ma dodać lewy pokój do stosu, jeśli jeszcze go tam nie ma.
3. Powtórz krok 2 dla kierunków w dół, w prawo iw górę (ponieważ używamy stosu, co oznacza, że ​​pokoje przechodzą w kolejności zgodnej z ruchem wskazówek zegara, zaczynając od górnego kierunku).
4. Powtórz od kroku 1.
5. Jeśli liczba ścieżek jest większa niż jeden, pokoje są rozłączone.

Jeśli są rozłączone pokoje, grupuję je według indeksu ścieżki, uzyskuję indeks największej ścieżki i łączę wszystkie inne pokoje z tymi pokojami. To jest praca w toku, ale moim (obecnym, „brutalnym”) planem jest przejście przez każdy pokój w grupie pokoi (z wyjątkiem pierwszego), aby sprawdzić, czy istnieje pozioma lub pionowa ścieżka do dużej grupy pokoi, i jeśli tak, utwórz tam poziomą / pionową ścieżkę, wstrzykując / aktualizując pomieszczenia między nimi. Wypłukać i powtórzyć. Brzydkie, tak, ale jest to coś, co nie będzie zauważalne pod względem wzorca wizualnego, więc działa w tym sensie.

Jednym z najlepszych i najczęściej używanych algorytmów jest generowanie lochów za pomocą partycjonowania przestrzeni binarnej.

Najlepsze ogólne wyjaśnienie, które przeczytałem, znajduje się w The Chronicles of Doryen (załączonym na końcu w celu wykonania kopii zapasowej), ponieważ wyjaśnia procedurę bez wchodzenia w kod, pozostawiając implementację czytelnikowi.

Dwa inne samouczki na ten sam temat z kodem można znaleźć na stronie

• Jak korzystać z drzew BSP do generowania map gier
• Generowanie lochów przy użyciu drzew BSP

Budowanie drzewa BSP

Zaczynamy od prostokątnego lochu wypełnionego komórkami ściany. Zamierzamy podzielić rekurencyjnie ten loch, dopóki każdy z lochów nie będzie miał wielkości pokoju. Podział lochów używa tej operacji:

• Wybierz losowy kierunek: podział poziomy lub pionowy
• Wybierz losową pozycję (x dla pionu, y dla poziomego)
• Podziel loch na dwa lochy

Teraz mamy dwa pod-lochy A i B. Możemy zastosować tę samą operację do obu z nich.

Wybierając pozycję podziału, musimy uważać, aby nie być zbyt blisko granicy lochu. Musimy być w stanie umieścić pokój w każdym wygenerowanym pod-lochu. Powtarzamy, aż najniższe sub-lochy będą miały w przybliżeniu wielkość pomieszczeń, które chcemy wygenerować.

Budowanie lochu

Teraz tworzymy pokój o losowym rozmiarze w każdym liściu drzewa. Oczywiście pomieszczenie musi znajdować się w odpowiednim lochu. Dzięki drzewku BSP nie możemy mieć dwóch nakładających się pokoi.

Aby budować korytarze, przeplatamy wszystkie liście drzewa, łącząc każdy liść z jego siostrą. Jeśli dwa pokoje mają twarze w twarz, możemy skorzystać z prostego korytarza. W przeciwnym razie musimy skorzystać z korytarza w kształcie litery Z.

Teraz wstajemy o jeden poziom w drzewie i powtarzamy proces dla podregionów ojca. Teraz możemy połączyć dwa podregiony łączem między dwoma pokojami lub korytarzem a pokojem lub dwoma korytarzami.

Powtarzamy ten proces, dopóki nie połączymy pierwszych dwóch pod-lochów A i B.

Metoda BSP jest najwyraźniej najpopularniejszą metodą generowania lochów, ale nie tylko.

Dla kompletności wyjaśnię generator, który działał dla mnie . Muszę przyznać, że nie pamiętam gdzie czytałem na ten temat, więc powiem tylko, że to nie jest mój wynalazek (an old artykuł przez Jamis Buck brzmi bardzo znajomo).

Labirynt z pokojami

Podstawową ideą jest to, że loch to labirynt z pokojami. Pierwszym krokiem dla tego algorytmu jest wygenerowanie labiryntu :

Następnym krokiem jest uczynienie go rzadkim (usuwanie ślepych zaułków):

Krok numer 3 polega na dodaniu kilku pętli ( spraw, by nie był idealny ), ale pominę obraz, ponieważ jest ledwo zauważalny (nie potrzebowałem idealnego labiryntu, więc skorzystałem z kilku skrótów algorytmu generowania labiryntu, więc już miał pętle do tego momentu).

Następnie w kroku 4 musimy usunąć izolowane komórki:

W tym momencie skończyliśmy z korytarzami i jesteśmy gotowi do dodania pokoi. W tym celu wykonujemy następujące czynności:

1. Wygeneruj zestaw pokoi (szerokość i wysokość)
2. Dla każdego pokoju iterujemy wszystkie możliwe lokalizacje i wybieramy najlepszą lokalizację.
   • Najlepszą lokalizację oblicza się, dodając wagę do warunków (takich jak sąsiedztwo korytarza).
3. Umieszczamy pokoje.

Do tej pory nasz loch wyglądałby tak:

Ostatnim krokiem jest dodanie dekoracji.

Kilka ostatnich myśli

• Użyłem uproszczonej wersji algorytmu Ellera .
• Różne algorytmy labiryntu mogą powodować różne tekstury. Możesz preferować inny algorytm. Na przykład poniższy obraz pokazuje różne tekstury wynikające z „drzewa binarnego” (ukośne ukosowanie) i odmianę algorytmów „podziału rekurencyjnego” (długie korytarze):