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ęść druga

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 druga część artykułu.
Jak wygenerować labirynt w Javie - część druga

Zapraszam do drugiej części artykułu o generowaniu labiryntu w Javie. Jeśli nie znasz pierwszej, znajdziesz ją tutaj. A zatem. Wzorzec architektoniczny Model-View-Controller to produkt z końca lat siedemdziesiątych. Model labiryntu w naszym przypadku opisywany jest przez klasę MazeModel. W zasadzie jest to tablica elementów typu Components.

public class MazeModel  implements Serializable {
    public static  final long serialVersionUID = 19640519L;
    private  MazeComponents[][] maze= new MazeComponents[height][weight];
    public MazeModel(MazeComponents[][] maze) {
        this.maze = maze;
    }
    public MazeModel() {
    }
    public MazeComponents[][] getMaze() {
        return maze;
    }
    public void setMaze(MazeComponents[][] maze) {
        this.maze = maze;
    }
}


Klasa Components reprezentuje to, co jest zawartością labiryntu czyli ściany, wolne przestrzenie oraz (jeszcze) artefakty, które nie mają większego wpływu a z czasem zostaną usunięte. Artefakt ITEM2  reprezentowany na konsoli jako znak "+" pojawia się w pustych miejscach labiryntu z prawdopodobieństwiem 1%. Zdarza się, że artefakt znajduje się w "niedostępnym" miejscu labiryntu, ponieważ generuje sie zupełnie przypadkowo. Zdefiniowanie enum nie odbywa się na poziomie modelu, lecz będzie pokazane później.

public enum MazeComponents {
    WALL, EMPTY, ITEM1, ITEM2, ITEM3, ITEM4
}


Poziom trudności labiryntu definiowany jest poprzed prawdopodobieństwo wygenerowania się ścian w labiryncie. Co prawda w kodzie jest to napisane inaczej, ale logicznie można tak przyjąć. Prawdopodobieństwa te zdefiniowane są – w odróżnieniu od definicji komponentów labiryntów – juz na poziomie modelu i przedstawia się następująco:

public enum Level {
    EASY(0.1F), MEDIUM(0.2F), HARD(0.3F), EXTREME(0.44F), IMPOSSIBLE(0.46F);
    private final float level;
    private Level(final float level) {
        this.level = level;
    }
    public float getLevel() {
        return level;
    }
}


Pozwoliłem sobie dodać jeszcze jeden poziom trudności IMPOSSIBLE, który nie został jeszcze przetestowany ze wzglęu na długotrwałość obliczeń.

I to w zasadze wszystko, by narysować jakikolwiek labirynt. Niestety w większości przypadków może zdarzyć się, że nie bedzie można go pokonać ponieważ na tym poziomie nie jest sprawdzana przechodniość labiryntu. Są to jedynie przypadkowo umieszczone ściany i wolne przestrzenie, oczywiściem za wyjątkiem krawędzi labiryntu oraz wejścia i wyjścia. Wejście i wyjście ustawione jest na razie na stałe co widać na obrazkach z poprzedniego artykułu. 

Co to oznacza, że labirynt jest przechodni? Oznacza to, że będąc w miejscu wejścia przędej czy później osiągniemy punkt wyjścia. Najprostszym i obecnie tu zastosowanym algorytmiem jest zasada prawej ręki. Polega ona na tym, że zawsze powinnyśmy dążyć do tego by mieć ścianę z prawej strony. Opisać można to pojedynczym krokiem wykonania za pomocą następującyh warunków:

  1. Jeżeli mamy ścianę z prawej strony to badamy, czy możemy iść do przodu. Jeżeli nie możemy (mamy ścianę z prawej i na wprost) to skręcamy w lewo.
  2. Jeżeli możemy iść do przodu (tj. mamy ścianę z prawej strony i nie mamy na wprost) to wykonujemy krok. 
  3. Jeżeli zaś nie mamy ściany z prawej strony to skręcamy w prawo i wykonujemy krok.


Opisany tu krok należy wykonywać dotąd aż osiągnie się punkt wyjścia. Dokładniej to opiszę gdy bedę pisał o serwisach. Wtedy labirynt jest do przejścia. Jeżeli jednak wrócimy do punktu początkowego to znaczy, że labirynt nie jest do przejścia – jest on zamknięty. 

Rozwinięciem tego sposobu rozumowania, który według mnie przyspieszyłby badanie labiryntu stworzenie będzie dwóch wątków, które działały by równolegle w nastepujący sposób. 

  1. Pierwszy wątek wykonywałby to samo co opisywany przed chwilą.
  2. Drugi wątek miałby za zadanie działać w przeciwnym kierunku  tzn. wykonywać się na wyjściu a kończyć się na wejściu labiryntu. 


Jeżeli których z tych wątków dojdzie do swojego zakończenia (pierwszy wątek z miejsca wejścia osiągnie miejsce wyjścia, a drugi wątek z miejsca wyjścia osiągnie miejsce wejścia labiryntu) albo chociaż w jednym miejscu trasy wątków się zetkną, to oznaczało by, że labirynt jest do przejścia. Jeśli zaś pierwszy lub drugi wątek wrócą do swoich punktów początkowych oznacza to, że labirynt jest nieprzechodni. Kolejnym rozszerzeniem było by zastosowanie jednoczesnie dwóch algorytmów tj. zasady prawej i lewej ręki – również od strony wejścia jak i wyjścia z labiryntu. Wymagało by to zsynchronizownia czterech wątków oraz być może stworzenia modelu danych reprezentujących trasę jako listę współrzędnych.

Na obecnym etapie zastosowano jedynie algorytm posługujący się zasadą prawej ręki. Do tego celu posłużyłem się następującym modelem danych:

public class Coordinates {
    private int h, w;
    private Azimuth azimuth;
    public Coordinates(int h, int w, Azimuth a) {
        this.h = h;
        this.w = w;
        this.azimuth=a;
    }
    public Coordinates() { }
    public int getH() {
        return h;
    }
    public void setH(int h) {
        this.h = h;
    }
    public int getW() {
        return w;
    }
    public void setW(int w) {
        this.w = w;
    }
    public Azimuth getAzimuth() {
        return azimuth;
    }
    public void setAzimuth(Azimuth azimuth) {
        this.azimuth = azimuth;
    }
}


Klasa Coordinates zawiera dane które zawierają współrzędne miejsca pobytu. Ale to nie wszystko. Musimy posiadać wiedzę w którym kierunku "patrzymy" by wiedzieć jak zmienią się koordynaty, gdy np. wykonamy krok w przód, albo np. obrócimy się w prawo i wykonamy krok w przód. Kierunek, w którym jesteśmy zwróceni reprezentuje następujący enum.

public enum Azimuth {
    NORTH, EAST, SOUTH, WEST
}


Myślę, że to już cały model w bieżącej wersji programu.

Teraz zademonstruję niektóre z kontrolerów z zaimplementowanych według wzorca Model-View-Controller.

Kontrolery implementują interfejs ControllerInterface, który w zasadzie jest interfejsem funkcyjnym, ale nie na razie nie bedziemy korzystać z dobrodziejstw interfejsu funkcyjnego i problem wielu kontrolerów rozwiążemy w inny sposób. Nie jest jednak powiedziane, że nie wrócimy do tego zagadnienia, gdy spełnimy wszystkie wymagania funkcjonalne aplikacji i wrócimy do refaktoringu lub podczas code rewiev.

import pl.ciecierski.model.MazeModel;
 
public interface ControllerInterface {
    void act(MazeModel mazeModel);
}


1. ControllerRandom

Jest pierwszym kontrolerem, który zaimplementowałem. Jego głównym przeznaczeniem było przetestowanie funcjonalności prawidłowego generowania i wyświetlania się labiryntu na ekranie. To wtedy dowiedziałem się, że zalecany najmniejszy rozmiar labiryntu to h=3 i w=7 oraz największy powinien być ograniczony do maksymalnych warości typu int. Kontroler implementuje metodę act(), która z kolei korzysta z serwisów. 

public class ControllerRandom implements ControllerInterface {
    public ControllerRandom(MazeModel mazeModel) {
        this.mazeModel = mazeModel;
    }
    MazeModel mazeModel;
    MazeGenerator mazeGenerator = new MazeGenerator();
    @Override
    public void act(MazeModel mazeModel) {
        System.out.println("ControllerRandom");
        mazeGenerator.printMaze(mazeGenerator.makeMaze(mazeModel));
    }
    
}


Jedynym zadaniem jakie ma instancja klasy ControllerRandom to wydrukowanie (metoda mazegenerator.printMaze) wygenerowanego (metoda mazeGenerator.makeMaze()) labiryntu. Metoda makeMaze generuje i zwraca obiekt klasy MazeModel, który to jest parametrem mentody printMaze(), która wyświetla zmienną mazeModel na ekranie.


2. ControllerFile

Kontroler ten również korzysta z metody mazeGenerator.makeMaze(), z tym że zadaniem kontrolera jest oprócz wygenerowania labiryntu zapisanie go na dysku poprzez zserializowanie obiektu klasy MazeModel. Dodatkowo kontroler potrafi zdeserializować obiekt z dysku i wyświetlić go na ekranie. Zserializowanie pojedynczego labiryntu, a potem już tylko oddzielna deserializacja (czyli pozbycie się funkcji generowania i serializacji nowego labiryntu) i pokazywanie na ekranie pozwoliło uzyskać posługiwanie się wciąż jednym i tym samym labiryntem do testowania róznych funkcjonalności, jak np. sprawdzanie algorytmu przechodniości labiryntu. Oto kontroler wraz z roboczymi komentarzami:

public class ControllerFile implements ControllerInterface {
    public ControllerFile(MazeModel mazeModel) {
        this.mazeModel = mazeModel;
    }
    MazeModel mazeModel;
    MazeGenerator mazeGenerator = new MazeGenerator();
    FileServices fileServices = new FileServices();
    @Override
    public void act(MazeModel mazeModel) {
        System.out.println("ControllerFile");
        String fileName = "";
// tworzy nowy labirynt i serializuje do pliku
        for (int i = 0; i < quantity; i++) {
            Instant instant=Instant.now();
            instant.toEpochMilli();
//            nazwa pliku powinna zawierać dodatkowo rozmiar labiryntu i level
            fileName ="f:" +i+"maze"+instant.toString().substring(20)+".txt";
            fileServices.serializeMaze(mazeGenerator.makeMaze(mazeModel), 								fileName);
//        deserializuje z pliku i pokazuje na ekranie
            mazeGenerator.printMaze(fileServices.deserializeMaze(fileName));
        }
 
    }
}


Jak widać w komentarzu, to, co miało być zrobione, nie zostało jeszcze wykonane. Uwagę tę uwzględniono już w kolejnym kontrolerze.


3. ControllerJSON

Działa podobnie jak poprzedni tylko serializuje dane do formatu JSON.

 
public class ControllerJSON implements ControllerInterface {
    MazeModel mazeModel;
    MazeGenerator mazeGenerator = new MazeGenerator();
    FileServices fileServices = new FileServices();
    JSONFileServices jsonFileServices = new JSONFileServices();
    public ControllerJSON(MazeModel mazeModel) {
        this.mazeModel = mazeModel;
    }
    @Override
    public void act(MazeModel mazeModel) {
        System.out.println("controllerJSON");
        String fileName = "";
        for (int i = 0; i < quantity; i++) {
            Instant instant=Instant.now();
            instant.toEpochMilli();
//       nazwa pliku JSON powinna zawierać dodatkowo rozmiar labiryntu i level
            fileName ="f:\\projects\\maze-json\\" +level+"-"+i+"-maze-h"+height+"-w"+weight+"-"+instant.toString().substring(20)+".json";
 jsonFileServices.serializeJSONMaze((mazeGenerator.makeMaze(mazeModel)), fileName);
 
//        deserializuje z pliku JSON i pokazuje na ekranie
            /*
      mazeGenerator.printMaze(jsonFileServices.deserializeJSONMaze(fileName));
            */
        }
    }
}


W obecnie działającej wersji opcja deserializacja z formatu JSON oraz wyświetlania - po przetestowaniu funkcjonalności - została wyłączona. Kontroler w takiej postaci dostarcza labirynty do wspomnianego uprzednio repozytorium maze-generator-results.

Planowane jest wykonanie kontrolera dostarczającego API. Ze względu na długość obliczeń generowanie labiryntów na poziomie EXTREME nie będzie prawdopodobnie wykonalne na słabym sprzęcie. Prawdopodobnie trzeba będzie pokusić się o rozwiązania chmurowe. W zamyśle jest również wykonanie zapisu labiryntów do bazy danych (np. MongoDB).

Jako ciekawostkę napiszę, że właśnie wygenerowało mi się 5 labiryntów w wersji EXTREME o wielkości h=180 i w=180. Proces trwał od godziny 07:15 do 15:02, ale zastanawiające jest rozbieżność czasów wykonania niektórych. Pierwszy np. generował się 4 godziny a trzeci "tylko" 7 minut. Przy czym pierwszy wygenerował prawie 9 milionów, zaś trzeci tylko ponad 300 tysięcy nieprawidłowych labiryntów. Szczegóły w opisie commita we ww. repozytorium.

Link do wspomnianego pierwszego labiryntu w repozytorium.

W kolejnej części opiszę serwisy, z których korzystały wyżej wymienione kontrolery.

Rozpocznij dyskusję

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

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

Dowiedz się więcej