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.
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.
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.
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ń().
Klasa będzie miała następujące zmienne pomocnicze:
(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.
W celu wygenerowania labiryntu należy przygotować zmienne, a następnie rozpocząć generowanie.
(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.
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.
(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.
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.
(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.
Wygenerowany labirynt można wypisać na konsolę używając polecenia Wypisz().
Poniższe zadania odnoszą się do grafiki SVG. Można o niej znaleźć w poradniku o grafice SVG.
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.
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.