Gra w życie

Miesiąc temu zajmowaliśmy się cykloidą i jej odmianami. Naszym celem było uzyskanie efektownych grafik, zbudowanych z czegoś w rodzaju szprych toczących się kół. Temat był stosunkowo łatwy i jeszcze przez miesiąc oczekujemy na Państwa prace. Dzisiaj porozmawiamy o automatach komórkowych i słynnej ich implementacji, historycznie zwanej grą w życie.

Miesiąc temu zajmowaliśmy się cykloidą i jej odmianami. Naszym celem było uzyskanie efektownych grafik, zbudowanych z czegoś w rodzaju szprych toczących się kół. Temat był stosunkowo łatwy i jeszcze przez miesiąc oczekujemy na Państwa prace. Dzisiaj porozmawiamy o automatach komórkowych i słynnej ich implementacji, historycznie zwanej grą w życie.

Grę w życie wymyślił w 1968 roku matematyk John H. Conway. Reguły są proste, ale praktyczna realizacja na tyle złożona, że wymaga zastosowania komputera.

Automat komórkowy jest kolonią oddziałujących na siebie komórek, mogących przyjmować różne stany. W tym zagadnieniu komórki będziemy nazywać organizmami, oddziaływanie między nimi sformułujemy jako reguły narodzin i umierania, a ich stany będziemy zaznaczać odpowiednimi kolorami.

Wyobraźmy sobie świat zamieszkany przez pewną liczbę bliżej nieokreślonych organizmów. I wyobraźmy też sobie cztery proste, surowe reguły rządzące życiem i śmiercią w tym świecie:

  • Niech organizm umrze z samotności, gdy ma mniej niż 2 sąsiadów.

  • Niech organizm umrze z przeludnienia, gdy ma więcej niż 3 sąsiadów.

  • Niech narodzi się nowy organizm, gdy dookoła znajduje się nie mniej niż 3 sąsiadów.

  • Niech narodzi się nowy organizm, gdy dookoła znajduje się nie więcej niż 3 sąsiadów.

Reguły te określają kolejno: dolną granicę umierania, górną granicę umierania, dolną granicę narodzin i górną granicę narodzin.

Zapewne reguły można sformułować w ładniejszy sposób (np. dwie ostatnie za jednym zamachem - niech organizm się urodzi, gdy dookoła jest 3 sąsiadów). Jednak zależy nam na zaakcentowaniu tych czterech nierówności, bo zaraz nabiorą one ścisłego, algorytmicznego charakteru.

Widoczne w regułach parametry 2, 3, 3, 3 będą najważniejszymi współczynnikami gry w życie - właśnie one definiują grę. Na początek ich wartości podajemy za Conwayem, choć zaraz chętnie je zmienimy, otrzymując zupełnie różne społeczeństwa.

W przyszłości - opisując jakieś społeczeństwo - będziemy podawać czwórkę liczb w rodzaju 2333. Mając taką czwórkę, taki zwarty opis, należy odwołać się do przed chwilą wypisanych czterech reguł i właściwie je sformułować, aby poznać najważniejsze zasady społeczne w danym świecie.

Nośnikiem życia będzie kwadratowa plansza (tablica) - powiedzmy, o boku złożonym ze 100 elementów, zawierająca same zera, ale gdzieniegdzie znajdą się też jedynki - żywe organizmy. Wielokrotnie będziemy stosować nasze cztery reguły życia i śmierci, zmieniając rozkład zer i jedynek w tablicy. Wokół każdej komórki zliczymy jedynki, czyli podsumujemy otaczających ją żywych sąsiadów, i na podstawie reguł podejmiemy decyzję o jej losie. Taki cykl podliczania wszystkich sąsiadów dla wszystkich komórek i zmieniania ich stanów nazwiemy pokoleniem. Gra będzie składała się z dowolnej liczby pokoleń.

Już widać, dlaczego w życie trudno grać bez komputera. W zasadzie można na planszy rozstawić pionki, ale bezustanne zliczanie ich sąsiadów i stosowanie reguł jest zadaniem beznadziejnie żmudnym.

Po tym wstępie zacznijmy implementować odpowiednie algorytmy. Na początek weźmy na warsztat planszę do gry. Niech planszą będzie duża tablica o boku określonym stałą ROZM, mogąca przechowywać zera i jedynki:

const int ROZM = 100;

int Plansza[ ROZM][ ROZM];

Typ całkowity int może być zbyt obszerny - do przechowania zer i jedynek wystarczy typ jednobajtowy. Unikajmy jednak typu logicznego o wartościach true i false, bo podliczanie sąsiadów za chwilę zrealizujemy, sumując po prostu okoliczne zera i jedynki. Podsumowując - niech to będzie tablica najkrótszych typów numerycznych.

Musimy zadbać, żeby życie nie wyszło poza planszę. Nie chcemy przy tym wbudowywać instrukcji warunkowych, baczących na brzegi, bo mogłyby istotnie spowolnić pracę algorytmów. Zrobimy tak - skrajne wiersze i kolumny zostaną wyłączone z obliczeń i zawsze będą zawierały zera. Nie zmodyfikujemy życia na obrzeżach tablicy, choć będą one dostępne dla algorytmu zliczającego sąsiadów. Będą dostępne, ale niewykorzystane - mamy nadzieję w ten prosty sposób uzyskać dużą szybkość i przejrzystość programu (porównaj rysunek 1).

Plansza musi zostać wstępnie przygotowana do gry, czyli wypełniona zerami w obszarach pozbawionych życia i jedynkami w tych miejscach, gdzie znajdują się żywe organizmy. Najefektywniejszym algorytmem wydaje się wstępne wyzerowanie całej tablicy, a potem gdzieniegdzie rozrzucenie życia. Układ widoczny na rysunku 1 uzyskamy w następującym procesie:

for( i = 0; i < ROZM; ++i)

{

for( j = 0; j < ROZM; ++j)

{

Plansza[ i][ j] = 0; //nie ma życia

}

}

Plansza[ 3][ 3] = 1; //jest życie

Plansza[ 4][ 4] = 1;

Plansza[ 5][ 4] = 1;


Zobacz również