Generator labiryntów i gra

Jak korzystać z generatora labiryntów

1. Ustaw Szerokość (kolumny) i Wysokość (rzędy), od 4 do 60 pól każda, i wybierz Algorytm. Kliknij Nowy labirynt.
2. Twoja pozycja to kropka w zielonym wejściu w lewym górnym rogu. Dotrzyj do czerwonego wyjścia w prawym dolnym rogu.
3. Poruszaj się strzałkami lub klawiszami WASD. Przytrzymaj Shift razem ze strzałką, aby pobiec korytarzem do najbliższego rozwidlenia. Na telefonie lub tablecie przesuń palcem po labiryncie, by pobiec w danym kierunku, albo dotykaj przycisków ze strzałkami pod nim, by robić pojedyncze kroki.
4. Stoper rusza z pierwszym ruchem i zatrzymuje się przy wyjściu. Za tobą rysuje się ślad; gdy się cofasz, ślad znika, więc zawsze pokazuje trasę, którą właśnie idziesz.
5. Nie wiesz, którędy dalej? Pokaż rozwiązanie rysuje najkrótszą drogę z miejsca, w którym stoisz, do wyjścia. Wróć na start przenosi cię z powrotem do wejścia i zeruje stoper.
6. Aby rozwiązywać labirynt na papierze, kliknij Drukuj lub Pobierz PDF. Jeśli chcesz mieć odpowiedź na drugiej stronie, najpierw zaznacz Dodaj stronę z rozwiązaniem.

Udostępnij labirynt za pomocą kodu

Każdy labirynt ma Kod labiryntu, na przykład b20x15-k3j9x2: literę algorytmu (b, p lub k), szerokość × wysokość i losowe ziarno. Ten sam kod zawsze odtwarza dokładnie ten sam labirynt na każdym urządzeniu, więc możesz rzucić znajomemu wyzwanie, by pobił twój czas na tym samym układzie. Wpisz lub wklej kod i kliknij Wczytaj kod albo użyj Kopiuj link, aby udostępnić adres, który od razu otwiera ten labirynt.

Trzy algorytmy generowania

Wszystkie trzy tworzą labirynt doskonały: do każdego pola da się dojść i między dowolnymi dwoma polami istnieje dokładnie jedna ścieżka, więc nie ma pętli ani odciętych obszarów. Różnią się charakterem labiryntu:

• Rekurencyjny backtracking (długie korytarze) wędruje losowo od pola do pola, burząc ściany, i cofa się, gdy trafi w ślepy zaułek. Daje długie, kręte przejścia z niewieloma odgałęzieniami: rozwiązanie jest zwykle długie i prowadzi przez większą część siatki.
• Prim (dużo krótkich ślepych zaułków) rozrasta labirynt na zewnątrz od losowego pola, za każdym razem dodając losowe pole z granicy. Powstaje mnóstwo krótkich bocznych odnóg, przez co labirynt wygląda na gęsty, ale główną drogę łatwiej dostrzec.
• Kruskal (równomierny, rozgałęziony) usuwa losowo wybrane ściany między polami, które nie są jeszcze połączone (śledzi to struktura union-find). Wynik jest równomiernie rozgałęziony w każdym miejscu, bez widocznego punktu startowego.

Wiersz nad labiryntem podaje rozmiar, długość najkrótszej ścieżki i liczbę ślepych zaułków, więc algorytmy można porównać na pierwszy rzut oka.

Jak znajdowane jest rozwiązanie

Rozwiązanie wyznacza przeszukiwanie wszerz (BFS): zaczynając od twojego pola, sprawdza wszystkich sąsiadów o jeden krok dalej, potem o dwa kroki i tak dalej, aż dotrze do wyjścia. Ponieważ każdy krok kosztuje tyle samo, BFS zawsze znajduje najkrótszą ścieżkę. W labiryncie doskonałym jest to też jedyna droga bez cofania się. Jeśli w trakcie przejścia rozwiązanie było pokazane, twój czas nie jest zapisywany jako najlepszy.

Wskazówki dotyczące drukowania

Wersja do druku i PDF ma wyraźne czarne ściany na białym tle, a kod labiryntu w tytule, dzięki czemu łatwo odnaleźć ten sam labirynt. Rozmiary około 15 × 15 są dobre dla małych dzieci; 30 × 30 i więcej to solidna łamigłówka dla dorosłych. Bardzo duże labirynty (50 × 60) mają na kartce A4 wąskie korytarze, więc drukuj je na całą stronę.