|
Katedra Systemów Mikroelektronicznych, Wydział
Elektroniki, Telekomunikacji i Informatyki, Politechnika Gdańska
|
|
Zadaniem jest implementacja gry „Life” w układzie FPGA. Gra
została wymyślona w 1970 roku przez matematyka dr Johna Conwaya. „Life” nie
jest grą w konwencjonalnym sensie, jest eksperymentem matematycznym dotyczącym
zachowania się „sztucznego życia” w określonym środowisku; może być też
traktowana jako implementacja pewnego automatu komórkowego.
Gra toczy się na prostokątnej planszy o wymiarach zadanych
przez prowadzącego laboratorium (wymiar poziomy i pionowy wybrany z zakresu od
50 do 80, wymiar poziomy powinien być większy od pionowego). Na planszy
rozmieszcza się „żyjątka”. Następnie uruchamia się algorytm gry.
Gra polega na obliczeniu kolejnego kształtu populacji (część
żyjątek przeżyje, niektóre żyjątka zginą, a inne narodzą się na wolnych
pozycjach). Na życie żyjątek ma wpływ ich bezpośrednie otoczenie (tj. 8
sąsiednich pozycji – zaznaczonych na niebiesko na poniższym rysunku).
Reguły obliczania
populacji następnego pokolenia:
1.
Jeżeli w bezpośrednim sąsiedztwie żyjątka znajdują się dwa
lub trzy inne żyjątka, to w następnym kroku żyjątko pozostaje na swoim miejscu,
w przeciwnym wypadku ginie (z samotności lub przeludnienia).
2.
Jeżeli w bezpośrednim sąsiedztwie pustego miejsca znajdują
się dokładnie trzy żyjątka, to w następnym kroku rodzi się w tym miejscu nowe
żyjątko, w pozostałych przypadkach miejsce pozostaje puste.
Przykłady:
Śmierć żyjątka z powodu „przeludnienia”:
Śmierć żyjątka z powodu „samotności”:
Żyjątko pozostaje przy życiu:
Narodziny nowego żyjątka:
Pola brzegowe w wynikowych okienkach mają wpisane znaki
zapytania ponieważ plansza jest większa (pokazano tylko wycinek) więc na tych
polach narodziny i śmierć żyjątek zależą od stanu pól które znajdują się poza
przedstawionym dla przykładu wycinkiem.
Realizacja:
Plansza gry powinna być wyświetlana na monitorze VGA. Symbol
„żyjątka” może być dowolny ale powinien być czytelny.
Dodatkowo powinno być możliwe wyświetlanie siatki pól – włączane
i wyłączane za pomocą wybranego przełącznika na płytce prototypowej lub
klawisza klawiatury PS/2.
Aktualny tryb pracy powinien być ustawiany za pomocą
wybranych klawiszy klawiatury PS/2. Należy obsługiwać trzy tryby pracy: ręczny,
automatyczny wolny, automatyczny szybki oraz dwa tryby wprowadzania: z
klawiatury PS/2 oraz z portu RS232. W trybie ręcznym – za pomocą wybranego
klawisza klawiatury PS/2 – wymusza się obliczenie następnej populacji. W trybie
automatycznym następna populacja obliczana jest samoczynnie z określoną
częstotliwością. Aktualny tryb pracy (wprowadzanie żyjątek z klawiatury,
wprowadzanie żyjątek z RS232, tryb ręczny - krokowy, tryb automatyczny wolny,
tryb automatyczny szybki) powinien być wyświetlany na wyświetlaczu LED (np.: Ent,
SEr, StEP, SLO, FASt). Szybkości trybów automatycznych powinny być następujące:
tryb wolny – 1 populacja na sekundę, tryb szybki – 5 populacji na sekundę.
Zmiany trybu nie powinny powodować zmian pamięci planszy gry.
Obsługa warunków brzegowych: należy zaimplementować dwa
sposoby tej obsługi (przełączane za pomocą wybranego przełącznika na płytce
prototypowej lub klawisza klawiatury PS/2):
1.
Granica występuje, pola poza zakresem są traktowane jako
puste.
2.
Granica nie występuje, pola ostatnie i pierwsze z punktu
widzenia algorytmu sąsiadują ze sobą (w obu wymiarach).
Aktualny stan mechanizmu obsługi warunków brzegowych
powinien być wyświetlany na wybranej diodzie LED: np.: zgaszona – tryb 1 (z
granicą), zapalona - tryb 2 (z zapętleniem).
Wprowadzanie danych początkowych gry (układu żyjątek):
1.
Wprowadzanie z klawiatury PS/2 (klawisze kursorów i inny
wybrany jako klawisz „toggle” – na wybranej przez kursor pozycji „zapala” lub
„gasi” żyjątko). Symbol kursora może być dowolny – ale powinien być widoczny i
migać.
2.
Wprowadzania przez interfejs RS232 pliku tekstowego w którym
linie oznaczają kolejne wiersze planszy gry, a w liniach tych znak * oznacza
żyjątka (każdy inny znak oznacza brak żyjątka na danej pozycji). Napotkanie
znaku LF (kod 10) powoduje przejście do następnego wiersza planszy (pozostała
część wiersza w pamięci pozostaje bez zmian). Pozostałe znaki o kodach < 32
powinny być ignorowane. Po wprowadzeniu całego wiersza dalsze znaki aż do LF
powinny być ignorowane. Po wprowadzeniu wszystkich wierszy planszy dalsze dane
z wejścia RS232 powinny być ignorowane. Jeżeli nie wszystkie wiersze zostaną
wprowadzone – system nie może się zawiesić, a zawartość pozostałych wierszy
które nie zostały wprowadzone pozostaje bez zmian. Parametry komunikacyjne
interfejsu: 115200 bps, 8 bitów danych, 1 bit stopu, brak parzystości.
Powinien być także zaimplementowany systemowy reset
(wykorzystując wybrany przycisk na płytce prototypowej) – który przywróci stan
początkowy (tryb wprowadzania z klawiatury, siatka wyświetlona, tryb obsługi
warunków brzegowych - z granicą) oraz wyczyści pamięć planszy gry.
Zadanie będzie weryfikowane przez prowadzącego za pomocą
kilku typowych populacji o znanych właściwościach.
Poniższe linki zawierają więcej informacji o grze „Life”, a
także przykłady populacji i programów implementujących grę:
http://www.math.com/students/wonders/life/life.html
http://en.wikipedia.org/wiki/Conway's_Game_of_Life
http://www.ies.co.jp/math/java/misc/life_game/life_game.html
Dostępne wkrótce.