Strona główna » Algorytmy » Artykuły » Tworzenie Labiryntu
 

Tworzenie Labiryntu

https://mattomatti.com/a0086
· Gra · Tworzenie ·

Wstęp

Tworzenie labiryntu to nie lada wyzwanie. Należy zapewnić, że do miejsca docelowego istnieje dokładnie jedna droga, a po drodze jest mnóstwo dróg, które po pewnym czasie okazują się być ślepe.

Algorytm

Przyjmujemy, że generujemy labirynt o kwadratowych polach i pewnych określonych wymiarach. Na początku należy poprawdzić pewną ścieżkę losowo wybierając kolejne pola. Warunkiem jest tutaj wybór pola stojącego obok poprzednio wybranego. Moża się zdarzyć, że przez to zabraknie pól. Jednak jeśli jest jeszcze jakiekolwiek wolne pole tj. nie połączone to należy wybrać nie podłączone pole, ale, które leży obok już wybranego, połączyć i ponownie rozpocząć proces rysowania.

Następnie trzeba wybrać pole startowe i końcowe. Istnieje tutaj wiele możliwości. Jedną z nich jest wybór lewego, górnego pola ora prawego, dolnego, ale to nie zawsze jest najlepszy wybór, ponieważ może istnień proste połączenie pomiędzy nimi. Innym pomysłem, choć trudnym do zrobienia ręcznie, polega na obraniu punktu początkowego i znalezienia punktu do któego prowadzi nadłuższa ścieżka. Istnieje wtedy największe prawdopodobieństwo, że osoba rozwiązująca może się zgubić i nadłożyć trochę drogi do punktu końcowego.

Implementacja

Strategia

Zostanie napisana klasa Labirynt, która wygeneruje dwuwymiarową tablicę dotyczącą położenia ścian dla każdego pola algorytmem opisanym wcześniej. Będzie ona potrzebować dwie dodatkowe struktury Punkt, która przetrzyma współrzędne oraz PunktK, która prócz współrzędnych będzie mogła mieć określony kierunek w którą stronę nastąpić ma przesunięcie.

  1. struct Punkt {
  2.   public int x, y;
  4.   public Punkt(int _x, int _y) {
  5.     x = _x; y = _y;
  6.   }
  7. }

Struktura PunktK, która prócz współrzędnych będzie mogła mieć określony kierunek w którą stronę nastąpić ma przesunięcie. Do tego będzie służyć polecenie Przesuń().

  1. struct PunktK {
  2.   public int x, y, k;
  4.   public PunktK(int _x, int _y, int _k) {
  5.     x = _x; y = _y; k = _k;
  6.   }
  8.   public void Przesuń() {
  9.     switch (k) {
  10.       case 0: y--; break;
  11.       case 1: x++; break;
  12.       case 2: y++; break;
  13.       case 3: x--; break;
  14.     }
  15.   }
  16. }

Klasa Labirynt

Zmienne

Klasa będzie miała następujące zmienne pomocnicze:

  1. int w, h;
  2. bool[,,] ściany;
  3. bool[,] wybrany;
  4. List<PunktK> aktualnie;
  5. Random r;

(1.) Zmienne w i h będą przetrzymywać szerokość i wysokość labiryntu. (2.) Dla każdego punktu ściany będą przechowywać informację o ścianach (true = ściana istnieje). W celu wygenerowania labiryntu tablica (3.) wybrany będzie pamiętać, które pola zostały odwiedzone, (4.) aktualnie - to lista możliwych przesunięć, a (5.) r posłuży do generowania losowych wartości.

Inicjalizacja

W celu wygenerowania labiryntu należy przygotować zmienne, a następnie rozpocząć generowanie.

  1. public Labirynt(int w, int h) {
  2.   this.w = w;
  3.   this.h = h;
  5.   ściany = new bool[w, h, 4];
  6.   wybrany = new bool[w, h];
  7.   aktualnie = new List<PunktK>();
  8.   r = new Random();
  10.   for (int x = 0; x < w; x++)
  11.     for (int y = 0; y < h; y++)
  12.       for (int k = 0; k < 4; k++)
  13.         ściany[x, y, k] = true;
  14.   for (int x = 0; x < w; x++)
  15.     for (int y = 0; y < h; y++)
  16.       wybrany[x, y] = false;
  17.   wybrany[0, 0] = true;
  18.   while (Szukaj())
  19.     aktualizujŚciany(aktualnie[r.Next(0, aktualnie.Count)]);
  20. }

(2. - 3.) Zapisz wymiary i (5. - 8.) przygotuj zmienne do pracy. Początkowo (10. - 13.) wszystkie ściany istnieją i (14. - 16.) żadne pole nie zostało wybrane. Następnie w celu rozpoczęcia generowania (17.) określamy punkt początkowo i (18. - 19.) dopóki jest to możliwe wybieramy kolejne przejścia ścieżki.

Szukanie

Funkcja Szukaj() służy do sprawdzenia czy istnieje jeszcze jakiś niepodłączony element w labiryncie. Jeśli taki jest to zostaje określone jego podłączenie, a następnie od niego jest prowadzona nowa ścieżka. Argument max - pomaga filtrować wybór punktu połączenia tak, aby było jak najmniej pól, którego nie mają ani jednej ściany.

  1. bool Szukaj(int max = 2) {
  2.   if (max >= 4)
  3.     return false;
  4.   int xp = r.Next(w), yp = r.Next(h);
  5.   int x = xp, y = yp;
  6.   do {
  7.     if (!wybrany[x, y]) {
  8.       if (x > 0 && wybrany[x - 1, y])
  9.         DodajŚciany(new PunktK(x - 1, y, 1), max);
  10.       if (y > 0 && wybrany[x, y - 1])
  11.         DodajŚciany(new PunktK(x, y - 1, 2), max);
  12.       if (aktualnie.Count != 0)
  13.         return true;
  14.       if (x < w - 1 && wybrany[x + 1, y])
  15.         DodajŚciany(new PunktK(x + 1, y, 3), max);
  16.       if (y < h - 1 && wybrany[x, y + 1])
  17.         DodajŚciany(new PunktK(x, y + 1, 0), max);
  18.       if (aktualnie.Count != 0)
  19.         return true;
  20.     }
  21.     x++;
  22.     if (x == w) {
  23.       x = 0;
  24.       y++;
  25.       if (y == h)
  26.         y = 0;
  27.     }
  28.   } while (x != xp || y != yp);
  29.   return Szukaj(max + 1);
  30. }

(2. - 3.) Rekurencyjne wywołanie funkcji Szukaj() jest ograniczone przez maksymalną ilość ścian. Na początku szukania nowego pola do podłączenia (4. - 5.) losujemy dowolną pozycję, a następnie (6. - 30.) filtrujemy wszystkie pola po kolei. Jeśli (7.) zostanie natrafione nie wybrane pole to (8. - 20.) generowane są jego możliwe podłączenia do labiryntu. Jeśli podłączenie spełnia kryteria to jest ono akceptowane i rozpoczyna się generowanie ścieżki.

Filtrowanie polega na (2. - 5.) policzeniu ile ścian ma pole, a potem (6. - 7.) dodanie możliwych przejść do tego punktu.

  1. void DodajŚciany(PunktK p, int max) {
  2.   int ile = 0;
  3.   for (int i = 0; i < 4; i++)
  4.     if (!ściany[p.x, p.y, i])
  5.       ile++;
  6.   if (ile < max)
  7.     DodajŚciany(p);
  8. }

Generowanie ścieżki

Wszystkie aktualne przejścia są przetrzymywane w zmiennej aktualnie z której dopóki nie jest pusta losowane są kolejne przejścia, a po przejściu lista połączeń zostaje zaktualizowana.

  1. void aktualizujŚciany(PunktK p) {
  2.   aktualnie.Clear();
  3.   ściany[p.x, p.y, p.k] = false;
  4.   p.Przesuń();
  5.   ściany[p.x, p.y, (p.k + 2) % 4] = false;
  6.   wybrany[p.x, p.y] = true;
  7.   DodajŚciany(p);
  8. }

(2.) Wyczyść aktualne podłączenia i (3.) usuń ściane na aktualnym polu, a potem (4.) przejdź do następnego pola i (5.) usuń odpowiednią ściane przypisaną temu polu. Następnie (6.) potwierdź, że pole zostało już wybrane i (7.) dodaj połączenia z tego pola.

Dodanie ścian polega na sprawdzeniu współrzędnej punktu oraz sprawdzeniu, że pole w którym sugerowane jest przesunięcie nie jest polem już wybranym.

  1. void DodajŚciany(PunktK p) {
  2.   if (p.x > 0 && !wybrany[p.x - 1, p.y])
  3.     aktualnie.Add(new PunktK(p.x, p.y, 3));
  4.   if (p.x < w - 1 && !wybrany[p.x + 1, p.y])
  5.     aktualnie.Add(new PunktK(p.x, p.y, 1));
  6.   if (p.y > 0 && !wybrany[p.x, p.y - 1])
  7.     aktualnie.Add(new PunktK(p.x, p.y, 0));
  8.   if (p.y < h - 1 && !wybrany[p.x, p.y + 1])
  9.     aktualnie.Add(new PunktK(p.x, p.y, 2));
  10. }

Testowanie funkcji

Wygenerowany labirynt można wypisać na konsolę używając polecenia Wypisz().

  1. static void Main(string[] args) {
  2.   Labirynt labirynt = new Labirynt(5, 5);
  3.   labirynt.Wypisz();
  4.   Console.ReadKey();
  5. }
  1. ###########
  2. #         #
  3. # ##### ###
  4. #     #   #
  5. # ####### #
  6. # #     # #
  7. # # # ### #
  8. # # # #   #
  9. # ### # ###
  10. #     #   #
  11. ###########

Zadania

Informacje do zadania 1, 2

Poniższe zadania odnoszą się do grafiki SVG. Można o niej znaleźć w poradniku o grafice SVG.

Zadanie 1

Napisz funkcję Zapisz() jako część klasy Labirynt tak, aby możliwe było zapisanie do pliku SVG wygenerowanego labiryntu. Oto przykładowy zapis:

Zakładamy, że punkt początkowy zawsze znajduje się w polu (0, 0) i został zaznaczony zielonym kółkiem, a punkt końcowy czerwonym i jest to pole, które jest najdalej od punktu początkowego.

Zadanie 2

Dodaj do funkcji Zapisz() możliwość włączenia wskazówek, które będą pokazywać jaka jest najmniejsza odległość od punktu początkowego do dodanego pola.