/langtons-ant

Python implementation of cellular automaton - Langton's Ant.

Primary LanguagePython

SYMULATOR MRÓWKI LANGTONA

Autor: ŁUKASZ STANISZEWSKI

SPIS TREŚCI:

ROZDZIAŁ I. OPIS PROJEKTU

WSTĘP

Projekt polega na implementacji automatu komórkowego, tzw. Mrówki Langtona.

Rys 1 - trasa mrówki po wykonaniu 7000 kroków

ZASADY DZIAŁANIA

  1. Mrówka porusza się na planszy o określonych wymiarach, podzielonej na kwadratowe komórki (pola) w dwóch możliwych kolorach: czarnym i białym
  2. Jeśli mrówka znajduje się na polu białym to obraca się w lewo (o kąt prosty), zmienia kolor pola na czarny i przechodzi na następną komórkę.
  3. Jeśli mrówka znajduje się na polu czarnym to obraca się w prawo (o kąt prosty), zmienia kolor pola na biały i przechodzi na następną komórkę.
  4. Jeśli mrówka doszła do końca planszy i próbuje za nią wyjść to przechodzi na losowo wybraną sąsiednią komórkę, która leży na planszy (np. jeśli mrówka znajduje się w dolnym lewym rogu planszy i próbuje przejść jedną komórkę w dół, to powinna wykonać losowy ruch w górę, lub w prawo).

WYMAGANIA PROJEKTU

  1. Mrówka porusza się po obrazie, którego wartość początkowa to jedna z następujących możliwości:
    • biały obraz o wymiarach podanych przez użytkownika,
    • obraz ładowany przez użytkownika (powinien być czarno-biały),
    • czarno-biała obraz, gdzie czarne piksele zostały losowo wygenerowane z zadanym prawdopodobieństwem.
  2. Wyjściem programu jest zapisana seria obrazów obrazująca wynik 'spaceru' mrówki - jeden obraz na każdy ruch. Liczba kroków określona jest przez użytkownika.

ROZDZIAŁ II. STRUKTURA PROJEKTU

OGÓLNY PODZIAŁ

Strukturę omawianego projektu najwygodniej podzielić na kilka punktów:
  1. DOKUMENTACJA – folder doc
  2. TESTY – folder tests i zawarte w nim testy (czyt. rozdział IV)
  3. WYJĄTKI – pliki ConsoleExceptions.py i GuiExceptions.py
  4. KLASY ODPOWIEDZIALNE ZA SYMULACJE – pliki Ant.py, BoardReader.py i Simulator.py
  5. FUNKCJE KONWERTUJACE NA LINII PROJEKT-OBRAZ – pliki ImageInput.py i ImageOutput.py
  6. CZĘŚĆ INTERFEJSOWĄ – folder gui_files, plik LangtonGui.py
  7. FOLDER WYNIKOWY – folder Steps

Rys 2 - końcowy wygląd folderu z projektem

SCHEMAT DZIAŁANIA

Schemat działania projektu obrazuje lista kroków:

  1. Uruchom projekt
  2. Wybierz opcje
  3. Wprowadź potrzebne dane
  4. Program wykonuje symulacje
  5. KONIEC

NAJWAŻNIEJSZE UŻYTE BIBLIOTEKI

Użyte w projekcie biblioteki:

  1. Numpy - korzystanie z klas do wygodnej pracy z wektorami dwuwymiarowymi
  2. Pillow - biblioteka do obsługi obrazów
  3. Pygame – biblioteka do tworzenia interfejsu graficznego
  4. Dodatkowo częściej spotykane biblioteki typu time, os, math czy sys

STRUKTURA MODUŁÓW I KLAS

Rys 3 - struktura klas

NAJISTOTNIEJSZE FUNKCJE

  1. Ant.go(kierunek) – porusza mrowke w dany kierunek
  2. BoardReader.create_board_from_picture(obrazek) – tworzy tablice dwuwymiarowa z danego obrazka
  3. ImageOutput.create_picture_from_board(tablica) – tworzy obrazek z danej tablicy
  4. Simulator.take_step() – funkcja odpowiedzialna za pojedynczy krok symulacji

ALGORYTMIKA

FAZA WSTĘPNA

Omówmy teraz dokładniej całe działanie projektu. Użytkownik uruchamiając plik run.py włącza symulator. W zależności od parametru w pliku run.py może uruchomić grę za pomocą:

  • KONSOLI
  • GRAFICZNEGO INTERFEJSU UŻYTKOWNIKA (GUI)

Teraz ma do wyboru wybranie 1 z 3 opcji:

  • STWORZENIA BIAŁEGO OBRAZKA (podaje wysokość i szerokość oczekiwanej grafiki)
  • ZAŁADOWANIA SWOJEGO OBRAZKA O MAX WIELKOSCI 300x300 (podaje ścieżkę do niego)
  • STWORZENIA BIAŁEGO OBRAZKA Z PRAWDOPODOBIENESTWEM WYSTAPIENIA CZARNYCH PIXELI NA NIM (zarówno wysokość i szerokość jak i prawdopodobieństwo jest podawane przez użytkownika)

Dodatkowo w każdej z 3 tych opcji musi podać również liczbę kroków jaką ma wykonać mrówka (jeżeli poda więcej niż 30000, mrówka wykona 30000 kroków). Następnie program sprawdza poprawność wprowadzonych danych – odpowiednie typy, wielkości itd. Gdy nie wystąpi żaden wyjątek, przechodzimy do następnej fazy projektu.

FAZA SYMULACJI

Fazę tę rozpoczyna program od skonwertowania wygenerowanego obrazka do tablicy dwuwymiarowej. Przedstawia ona plansze po jakiej się mrówka porusza – to właśnie w jej centrum zostaje umieszczona mrówka. W pętli wykonującej się N-krotnie (N – liczba kroków podana przez użytkownika we wcześniejszej fazie) mrówka robi kolejne kroki według algorytmu zawartego w I rozdziale dokumentacji. W międzyczasie każdy stan planszy jest przerabiany za pomocą odpowiedniej funkcji na czarno-biały obrazek, który jest zapisywany do folderu Steps z odpowiednia nazwa w postaci step_[nr kroku]. Po wykonaniu pętli, następuje koniec programu.

Rys 4 – fragment przykładowego wyglądu folderu Steps po zakończonym

ROZDZIAŁ III. INSTRUKCJA UŻYTKOWNIKA

WSTĘP

Aby uruchomić program, należy wejść do folderu z projektem, za pomocą edytora tekstowego otworzyć plik run.py i w funkcji start() wpisać odpowiednio 1 lub 2:

ImageInput.start(1)   # open in gui
ImageInput.start(2)   # open in console

START KONSOLOWY

Następnie po zapisaniu pliku run.py możemy go uruchomić. W konsoli powita nas ekran taki jak na zdjęciu.

Rys 5 - ekran startowy w wersji konsolowej

START GUI

Po uruchomieniu pliku run.py z parametrem 1, pojawi nam się następujące okno.

Rys 6 - ekran startowy w wersji gui

OPCJA TWORZENIA PLIKU

Pierwszą z wybranych opcji, jest opcja tworzenia białego obrazka. Po wybraniu jej, należy wpisać odpowiednie dane, tak jak na obrazkach. Dane mają też swoje ograniczenia:

  1. Wysokość [height] obrazka powinna być liczbą całkowitą z zakresu 0-300
  2. Szerokość [width] obrazka powinna być liczbą całkowitą z zakresu 0-300
  3. Liczba kroków [steps] powinna być liczbą z zakresu 1-30000

Rys. 7.1 - ekran 1 opcji w gui

Rys. 7.2 - ekran 1 opcji w konsoli

OPCJA ŁADOWANIA PLIKU

Drugą z możliwych opcji do wybrania jest ładowanie własnego pliku. Ładowany plik warto umieścić w folderze load, specjalnie do tego przeznaczonym. Nie ma wymogów co do kolorów na obrazku – zostanie on przekonwertowany na czarno-biały obiekt. Istotny jest jednak rozmiar obrazka. Ładowany obrazek nie może mieć szerokości lub wysokości większej niż 300 pixeli.

Rys. 8.1 - ekran 2 opcji w gui

Rys. 8.2 - ekran 2 opcji w konsoli

OPCJA TWORZENIA PLIKU Z PRAWDOPODOBIEŃSTWEM

Trzecią z możliwych opcji do wybrania jest tworzenie własnego pliku z prawdopodobieństwem wystąpienia czarnego pixela na nim. Poza atrybutami pojawiającymi się w opcji 1, występuje tu również atrybut probability – wymaga podania liczby rzeczywistej z zakresu (0, 1).

Rys. 9.1 - ekran 3 opcji w gui

Rys. 9.2 - ekran 3 opcji w konsoli

WYNIK SYMULACJI

Po zakończeniu symulacji, należy wejść do folderu steps. Własnie tam znajduje się wynik całej symulacji w postaci serii obrazków, tak jak pokazane to zostało na rys 4.

ROZDZIAŁ IV. PRZEPROWADZONE TESTY

TESTY JEDNOSTKOWE

Projekt ten zawiera liczne testy, sprawdzające prawidłowe działanie zawartych w nim klas, metod, funkcji czy atrybutów. Zaczynając od sprawdzenia pozycji mrówki na planszy aż po całe jej załadowanie z pliku.

Rys. 10 - wszystkie przeprowadzone testy (działają!)

Rys. 11 - pliki z testami

WAŻNY PRZYKŁAD

Istotną właściwością mrówki Langtona jest trasa, jaką wykonuje ona po zrobieniu 10000 kroków. Tworzy ona wtedy charakterystyczny kształt nazwany „autostradą”, nie inaczej jest w tym projekcie.

Rys 12 - droga wykonana przez mrówkę po 11000 krokach

TEST SYMULACJI

Podjąłem w projekcie próbę przeprowadzenia krótkiej symulacji na małym obrazku (np. o wymiarach 5x3), w której mogłem przewidzieć pierwsze 4 kroki mrówki. Następny krok program ze względu na mały obszar wybiera już losowo (stąd dalsze testy nie mają sensu – nie da się przewidzieć następnego kroku).

Rys 13. - test symulacji

Rys 14.1 - załadowany obrazek jako tablica 0-1

Rys 14.2 - zmiana pozycji środkowego pixela

Rys 14.3 - mrówka skręca w lewo, idzie na pixel w 3 kolumnie i 2 wierszu

Rys 14.4 - mrówka skręca w lewo, idzie na pixel w 3 kolumnie i 3 wierszu

Rys 14.5 - mrówka skręca w prawo, idzie na pixel w 2 kolumnie i 3 rzędzie

Podobne symulacje przeprowadziłem również dla ładowanego obrazka 5x5 (4 kroki) i stworzonego białego obrazka 5x5 (10 kroków). Wszystkie symulacje wyszły prawidłowo.

ROZDZIAŁ V. EWENTUALNY ROZWÓJ

Projekt można by było udoskonalić w możliwość pojawienia się kilku mrówek naraz na obrazie. O ile założenie te zostałoby sformułowane już w początkowej fazie projektowania (a tak naprawdę to w fazie planowania algorytmiki), zaimplementowanie pomysłu mogłoby dojść do skutku. Na obecnym etapie wdrożone algorytmy stworzone są z przeznaczeniem dla automatu jednej mrówki i ewentualna modyfikacja spowodowałaby zmianę struktury większości programu. Dlatego też kwestię tą postanowiłem umieścić w tym rozdziale dokumentacji.

ROZDZIAŁ VI. WYKORZYSTANE ZASOBY

Icons made by Freepik from www.flaticon.com