Katedra Systemów Mikroelektronicznych, Wydział Elektroniki, Telekomunikacji i Informatyki, Politechnika Gdańska

 

 

Powrót do strony głównej

 

 

Laboratorium z przedmiotu Programowalne Układy Cyfrowe - zadanie na ocenę 5,5 (jedno do wyboru)

 

Zadanie 1  -  Gra „Life”

 

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

 

 

 

Zadanie 2  -  System mikroprocesorowy

 

Dostępne wkrótce.