Diversity w polskim IT
Sławomir Ciecierski
Sławomir CiecierskiAdministrator systemów w obiektach zagłębionych @ Ministerstwo Obrony Narodowej

Jak wygenerować labirynt w Javie - część pierwsza

Dowiedz się, jak krok po kroku stworzyć w Javie aplikację konsolową, która będzie generowała labirynty. Jest to część pierwsza cyklu artykułów.
28.04.20213 min
Jak wygenerować labirynt w Javie - część pierwsza

Celem tego cyklu artykułów jest opisanie prostej aplikacji konsolowej do generowania labiryntów w języku Java. Czytelnik z pewnością zastanawia się, po co komu labirynty. Na pomysł ten wpadłem, czytając książkę o tworzeniu światów w Unity. Aczkolwiek nie doczytałem się w książce, że Unity w wersji podstawowej obsługuje wprost Javę, ale od czego mamy taki standard wymiany danych jak JSON.

Zadaniem aplikacji będzie wygenerowanie labiryntu do pliku (na razie do pliku) w standardzie JSON. Inne założenia to: wyświetlanie labiryntu na ekranie, serializowanie obiektu javowego labiryntu do i deserializowanie z pliku oraz generowanie labiryntu w formie API za pomocą metody get http. Czy będzie to REST? Zobaczymy. Zakładam, że czytelnik posiada podstawową wiedzę z zakresu języka Java oraz... wyobraźnię.

I tu chciałem rozpocząć trochę nietypowo, bo od końca. Otóż moja bieżąca implementacja już generuje labirynty, serializuje i deserializuje do obiektu Javy oraz do JSONa. Niektóre wygenerowane przez program labirynty JSON znajdują się w tym repozytorium

Na kilku obrazkach poniżej pokazuję wygenerowane labirynty w 4 różnych poziomach trudności. Wnętrze labiryntu generowane jest losowo, po czym następuje rozpoznanie, czy da się go przejść. W stopniu trudności EASY prawdopodobnieństwo pojawienia się ścian (nie wliczam krawędzi labiryntu) wynosi zaledwie 0.1.

Ze względu na szybki czas wygenerowania się typ ten można wystawić przez API. Niezbyt nadaje się jako labirynt 2D, można ewentualnie zastanowić się, czy nie użyć we ww. Unity, który wygenerowałby go jako labirynt 3D. W obecnej wersji program potrafi wygenerować inne obiekty oprócz ścian i wolnej przestrzeni. Na rysunku pokazane są jako znaki "+" ale sporządzanie tego typu "artefaktów" można zostawić ewentualnym twórcom gry, więc prawdopodobnie w następnych wersjach aplikacji usunę tę możliwość.


Kolejny rysunek przedstawia labirynt o tych samych wymiarach o stopniu trudności MEDIUM, co oznacza, że prawdopodobieństwo pojawienia się ściany wynosi 0.2. Generuje się szybko (czasy rozpoczęcia i zakończenia pokazane są na rysunku) i również niezbyt nadaje się jako labirynt 2D. 


Przejście labiryntu 2D o stopniu trudności HARD (prawdopodobieństwo 0.3, że pojawi się ściana) może już być trochę zajmujące. Rozmiar ten generuje się również szybko, aczkolwiek nie jest to regułą, o czym świadczyły przeprowadzane przeze mnie testy. 


Poziom EXTREME nadaje się zarówno jako labirynt 2D jak i 3D. Czas wykonania należy liczyć już w sekundach, ale uzyskany wynik pokazany na rysunku jest dosyć optymistyczny. Prawie 200 tysięcy wygenerowanych poprzednio algorytm odrzucił ze względu na to, że były nieprzechodnie.

Z doświadczenia powiem, że wygenerowanie 50 tego typu labiryntów zajmuje całą noc. W ciągu doby nie udało mi się wygenerować takiego typu labiryntu o wymiarach h=500 i w=500. Dlatego też zdecydowałem się te szczególnie ekstremalne labirynty umieszczać w repozytorium. Poziom EXTREME mówi, że prawdopodobieństwo pojawienia się ściany wynosi 0.44. Nie udało mi się wygenerować labiryntu z prawdopodobieństwiem 0.45, aczkolwiek teoretycznie  możliwe jest wygenerowanie o jeszcze większych współczynnikach. 


Tyle tytułem wstępnego artykułu. W następnej części napiszę, dlaczego zdecydowałem się na wzorzec architektoniczny MVC i co z tego wynikło, jak wygląda model labiryntu oraz opiszę algorytm badania przechodniości labiryntu i co w tym algorytmie mógłbym ulepszyć. Napiszę też, gdzie możliwe było by zastosowanie przetwarzania wielowątkowego i czy to bardzo przyspieszyłoby te obliczenia.

<p>Loading...</p>