Języki programowania - program na zaliczenie

Temat: Zmodyfikowana gra w życie.

Opis.

1. Założenia ogólne.
Dany jest świat jako obszar prostokątny, składający się z r wierszy po c komórek w każdym wierszu (r i c nie są z góry znane - należą one do parametrów problemu). Każda komórka może być albo pusta, albo może zawierać osobnika pewnego gatunku. Gatunki oznaczane są literami alfabetu i zbiór gatunków również nie jest z góry znany. Osobniki każdego gatunku mogą się rozmnażać, mogą również pożerać osobniki innego gatunku. Symulacja podzielona jest na rundy. W każdej rundzie każdy osobnik może wykonać co najwyżej jedną czynność: może albo się rozmnożyć, albo pożreć osobnika innego gatunku (zasady rozmnażania i pożerania zostały opisane niżej). Jeśli sytuacja danego osobnika jest taka, że może zarówno pożreć, jak i się rozmnożyć, decyzja o wykonywanej czynności podejmowana jest w sposób losowy - prawdopodobieństwo wyboru każdej z czynności jest identyczne (wynosi 0.5). Każdy osobnik posiada czas życia, który wynosi z rund. Jeśli osobnik w danej rundzie pożre osobnika innego gatunku, jego czas życia wzrasta o jedną rundę. Zatem jeśli pewien osobnik pojawił się na świecie w rundzie k, w wyniku rozmnożenia innych osobników w rundzie k-1, to o ile nie pożre innego osobnika w rundach k, k+1,...,k+z-1, nie będzie go już na świecie począwszy od rundy k+z. Oczywiście osobnik pożarty znika ze świata począwszy od następnej rundy. W szczególnym przypadku dany osobnik może żyć wiecznie, jeśli w każdej rundzie uda mu się pożreć osobnika innego gatunku.
Stan świata w rundzie k+1 generowany jest na podstawie stanu świata w rundzie k, jednak stan w rundzie k jest stały. Oznacza to, że jeśli w rundzie k osobnik X zostanie pożarty przez osobnika Y, to mimo to może on jeszcze brać udział w rozmnażaniu lub pożeraniu w rundzie k.

2. Zasady pożerania i rozmnażania.
Osobik X gatunku A może się rozmnożyć (utworzyć nowego osobnika Z gatunku A) jeśli w danej rundzie w jednej z sąsiednich komórek świata (przez komórkę sąsiednią rozumiemy komórkę położoną powyżej, poniżej, po lewej i po prawej stroniej komórki zajętej przez X, ale nie komórki położone po skosie typu lewo-góra czy prawo-góra) znajduje się osobnik Y tego samego gatunku. Jeśli osobnik X rozmnożył się w rundzie k przy pomocy osobnika Y, to osobnik Y nie może już rozmnażać się w rundzie k (może jednak w tej rundzie pożerać). Dodatkowym warunkiem rozmnażania jest istnienie co najmniej jednej pustej komórki świata w sąsiedztwie (przez sąsiedztwo rozumiemy tutaj znowu komórkę powyżej, poniżej, po lewej i po prawej, ale nie na skos) rozmnażającego się osobnika. Jeśli taka komórka nie istnieje, osobnik nie może się rozmnożyć. Nowo powstały osobnik zajmuje jedną z wolnych komórek sąsiednich swojego rodzica (jeśli jest więcej niż jedna wolna komórka, zajmuje którąkolwiek z nich - można np. wylosować którą komórkę ma zająć).
Aby osobnik X gatunku A mógł pożreć osobnika Z gatunku B, muszą być spełnione następujące warunki:

1. Z musi znajdować się w komórce sąsiedniej do tej zajmowanej przez X (sąsiednie komórki definiujemy tak jak przy rozmnażaniu).
2. W innej komórce sąsiadującej z tą zajmowaną przez pożeranego osobnika Z musi znajdować się inny osobnik Y gatunku A (pożerającego).

Dany osobnik może być pożarty tylko raz. Oznacza to, że jeśli X i Y (tego samego gatunku) sąsiadują z Z (innego gatunku), oraz  X pożarł Z wykorzystując do tego obecność Y, to Y nie może już ponownie pożreć Z, wykorzystując do tego obecność X.
Powyższe reguły dopuszczają sytuację, w której w pewnej rundzie osobnik X pożre Z i Z pożre X. Godzimy się na taki paradoks aby dodatkowo nie komplikować reguł.
Jeśli jakaś sytuacja nie została uwzględniona w powyższym opisie, można dla niej przyjąć dowolny sposób postępowania.

3. Sposób przeprowadzenia symulacji.
Stan początkowy symulacji powinien obejmować rozmiar świata, liczbę gatunków oraz stan świata w rundzie 1. Rozmiar świata i liczba gatunków zawsze będą określane przez użytkownika, natomiast początkowy stan świata powinien być albo generowany w sposób losowy (użytkownik określa, jaki procent komórek świata ma być zajęty przez osobniki, a program generuje zawartość poszczególnych komórek losując gatunek, z którego osobnik zajmie konkretną komórkę; alternatywnie można wylosować ciąg osobników określonej długości, a następnie losowo przydzielić osobnikom komórki, które będą zajmować), albo program powinien umożliwić wczytanie początkowego stanu świata z pliku tekstowego. W pliku takim znak '.' (kropka) oznacza pustą komórkę, a oznaczenie literowe ('a','b',...) oznacza komórkę zajętą przez osobnika danego gatunku. Zakładamy, że plik będzie zawierał r wierszy, po c znaków w każdym wierszu i że gatunki zawsze będą oznaczane kolejnymi, małymi,  literami alfabetu, począwszy od 'a'.
Następnie przeprowadzamy symulację świata, wyliczając stan następnej rundy po wciśnięciu klawisza przez użytkownika. Po określeniu stanu świata w danej rundzie należy przestawić go na ekranie, drukując r wierszy tekstu, po c znaków w każdym wierszu, oznaczając kropką puste komórki, a odpowiednią literą osobniki danego gatunku. W momencie wyliczania stanu świata należy dodatkowo drukować informację o wykonanych czynnościach (typu: "osobnik gatunku a z komórki (2,1) pożarł osobnika gatunku c z komórki (3,1)").
Symulacja kończy się po wciśnięciu przez użytkownika określonego klawisza (np. 'q').
Wyliczając stan świata w rundzie k+1 na podstawie stanu w rundzie k należy po kolei sprawdzić sytuację każdego osobnika. Ponieważ jednak kolejność, w której będziemy "przetwarzać" osobniki może mieć wpływ na nowy stan świata, należy przyjąć kolejność losową. Metoda określenia takiej kolejności może być następująca (jest to tylko sugestia):

1. Mając dany wektor n osobników, utwórz nowy wektor, zdolny pomieścić n osobników.
2. Dla i=1,2,...,n do komórki i-tej nowego wektora wstaw osobnika wylosowanego spośród n-i+1 osobników ze starego wektora, po czym usuń wylosowanego osobnika ze starego wektora (długość starego wektora zmniejszy się o 1).

4. Wymagania co do konstrukcji programu.
Każdy osobnik powinien być reprezentowany przez obiekt określonej klasy (np. Osobnik). Świat również ma być reprezentowany przez obiekt (np. klasy Swiat). Obiekt-świat powinien zawierać aktualny stan "mapy" świata, oraz udostępniać metody, za pomocą których obiekty-osobniki będą mogły ten stan sprawdzać. Każdy obiekt-osobnik odpowiada za zachowanie pojedynczego osobnika. Funkcjonalność obiektów-osobników powinna zawierać opisane wyżej reguły dotyczące czasu życia, rozmnażania i pożerania (zatem osobnik sam powinien decydować np. o swojej śmierci, powiadamiając świat że taki fakt nastąpił). Obiekt-świat powinien zawierać również metody generujące stan w kolejnej rundzie oraz wyświetlające stan świata na konsoli. Procedura kontrolująca symulację powinna w zasadzie wyłącznie wywoływać kolejno odpowiednie metody obiektu-świata, które to metody z kolei powinny korzystać kolejno z odpowiednich metod obiektów-osobników (które mogą ponownie korzystać z metod obiektu-świata w celu określenia lokalnego otoczenia danego osobnika, umożliwiając mu w ten sposób podjęcie decyzji o wykonywanej w danej rundzie czynności). Zatem obiekt-świat powinien posiadać wskaźniki (referencje) do wszystkich obiektów-osobników, natomiast każdy obiekt-osobnik powinien posiadać wskaźnik (referencję) do świata, w którym żyje. Wygodnie będzie określić interfejsy osobnika i świata jako interfejsy (Java, C#) lub klasy abstrakcyjne (C++) i posługiwać się wskaźnikami (referencjami) do tych interfejsów w kodzie implementującym klasę świata i osobników. W ten sposób unikniemy zapętlonych referencji (świat-osobnik-świat) i skorzystamy z polimorfizmu. Proszę traktować tą uwagę jako wymaganie. Oczywiście w programie mogą być wykorzystane również obiekty innych klas (pomocniczych), jeśli okaże się to potrzebne, jednak wariant minimalny to: interfejs osobnika, interfejs świata, implementacja osobnika, implementacja świata.


Sposób zaliczenia programu.

Programy zaliczane będą na ćwiczeniach 21 maja 2007r. Każdy autor programu zaprezentuje działanie swojego dzieła i będzie zobowiązany do udzielenia odpowiedzi na kilka pytań dotyczących kodu źródłowego. Dodatkowo program zostanie sprawdzony na spreparowanych wcześniej stanach początkowych świata, pod kątem zgodności z opisanymi regułami postępowania.

Program można wykonywać w parach, jednak w takim przypadku należy wyraźnie podzielić się rolami (np. jedna osoba implementuje klasę świata, a druga klasę osobnika) i poinformować przy zaliczaniu programu jaki był zakres odpowiedzialności danego współautora.