Algorytm generowania labiryntu 2d [zamknięty]

Jakiego algorytmu używałeś w przeszłości do generowania prostego labiryntu 2D?

Istnieje wiele różnych sposobów tworzenia labiryntów. Jest ich ogromna lista i ich opisy tutaj: http://www.astrolog.org/labyrnth/algrithm.htm

Myślę, że użyłem tego opisanego pod „Perfect”.

Wolę ciasno zwinięte labirynty, które tworzy Algorytm Kruskala.

Standardowy opis algorytmu Kruskala jest nieodpowiedni, ponieważ nie rozróżnia on lokalizacji na wykresie od grup lokalizacji, opierając się na grze słów o wyborze struktury danych, co prowadzi do dwuznaczności opisu, które dezorientują nowicjuszy. Dlatego odrzucam terminologię Kruskala.

Użyję następujących terminów:

• Wykres
  • sam labirynt.
• Węzeł
  • lokalizacja w labiryncie. W kwadratowym labiryncie jest to kwadratowa komórka.
• Brzeg
  • połączenie między dwoma węzłami. W kwadratowym labiryncie jest to pasek o długości 1.
• Grupa drzew
  • zestaw węzłów, które mogą być puste, ułożone w formie drzewa

Z nich otrzymujemy:

1. Utwórz grupę GTG dla Graph Tree Group , zawierającą grupy drzew
2. Wypełnij GTG jedną grupą drzew zawierającą jeden węzeł dla każdej lokalizacji w labiryncie
3. Utwórz zestaw krawędzi E
4. Wypełnij E każdą ważną krawędzią w swoim labiryncie
5. Podczas gdy w GTG jest więcej niż jedna grupa i podczas gdy E nie jest puste:
6. Wybierz losową krawędź rE z E
7. Zidentyfikowanie punktów końcowych P1 i P2 z rE
8. Usuń RE z E.
9. Sprawdź, do których grup należą p1 i p2 (odpowiednio p1g i p2g ).
10. Jeśli p1g i p2g są różne, dołącz do grupy drzew p1g i p2g w p1 -> p2 i przepisz całą własność grupy jednego drzewa do drugiego, łącząc w ten sposób drzewa.
11. Wróć do kroku 5.
12. Jeśli nie masz żadnych krawędzi, ale więcej niż jedno drzewo, wykres nie jest połączony lub występuje błąd.
13. Jeśli masz tylko jedno drzewo, masz kompletny labirynt bez pętli.

Wikipedia ma świetny zasób na temat generowania labiryntu . Korzystam z algorytmu losowych prymów ze świetnymi wynikami. Algorytm podziału wygląda interesująco, ale nigdy go nie użyłem.

Oto przykład Wikipedii z Prim's w pracy.

Jednym prostym sposobem jest sporządzenie listy ścian północnych i zachodnich, a następnie ich permutację. Nadaj każdemu pokojowi numer. Następnie wysadź jedną ze ścian na liście, o ile dwa pokoje nie mają tego samego numeru, a następnie propaguj jeden z numerów do wszystkich innych pokoi o tym samym numerze. Idź dalej, aż zabraknie ci ścian. Działa to w przypadku prostokątnych labiryntów lub, w rzeczywistości, każdego innego labiryntu, w którym można podać listę „potencjalnie połączonych pokoi”. Ponadto programowanie jest dość proste.

Przyjrzałbym się również niektórym algorytmom używanym w rozwoju Roguelike. W Rogue Basin jest dobry zasób początkowy

Dobry bieg tutaj: https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

Podstawowe kroki to:

• Umieść pokoje
• Wypełnij puste miejsce labiryntem
• Połącz pokoje z labiryntem
• Wytnij ślepe zaułki

Kod tutaj: https://github.com/munificent/hauberk/blob/db360d9efa714efb6d937c31953ef849c7394a39/lib/src/content/dungeon.dart

Zapytałeś, którego użyłem, więc postaram się na nie odpowiedzieć. Użyłem rekurencyjnego algorytmu cofania w mojej labiryncie w Rootbeer Games .

Jest to dowód na to, że użyłem algorytmu, nie traktuj go jako reklamy mojej pracy.