Nasza strona używa cookies. Korzystając ze strony, wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki. Rozumiem

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

Sławomir Ciecierski Administrator systemów w obiektach zagłębionych / Ministerstwo Obrony Narodowej
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.
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.

Rozpocznij dyskusję

Lubisz dzielić się wiedzą i chcesz zostać autorem?

Podziel się wiedzą z 160 tysiącami naszych czytelników

Dowiedz się więcej

Zobacz jakie firmy chcą Ci płacić więcej.

Ile teraz zarabiasz?

Podpowiedzieliśmy już razy.

Mamy ponad 1200 ofert pracy. Zobacz o ile więcej możesz zarabiać. » [zamknij]