Game of Life

Wstęp.

O grze w życie słyszał na pewno każdy, a przynajmniej powinien. Kto nie zna tego zagadnienia odsyłam na początek do samej wiki: LINK. W skrócie można powiedzieć, że gra w życie (mowa o wariancie Conway'a) to rodzaj automatu komórkowego. Automat komórkowy to zespół pojedynczych komórek, których życie (lub stan) w kolejnych generacjach zdefiniowany jest w postaci pewnych reguł. W zależności od konstrukcji tych reguł można uzyskiwać przeróżne "formy życia", które niejednokrotnie cechują się niebywałymi właściwościami. Prócz bycia ciekawostką algorytmiczną, automaty komórkowe mogą służyć do chociażby symulowania procesów fizycznych. Nie da się też ukryć, że całość po prostu efektownie wygląda. Wartościowe opracowanie traktujące bardzo poważnie o AK można znaleźć np. tutaj: LINK.

Jednym z najlepszych filmów prezentujących grę w życie w pełnej okazałości jest to:

Uważam, że "epic" w tytule filmu jest całkowicie uzasadnione.

Z racji charakteru symulacji kolejnych generacji, który dla dużych populacji i bardziej rozbudowanych algorytmów potrafi być bardzo zasobożerny, aż prosi się aby proces wyznaczania kolejnych stanów komórek zrównoleglić. Stąd zrodził się w mojej głowie pomysł aby na tym przykładzie sprawdzić w jaki sposób w C# realizowana jest wielowątkowość. Była to też dobra lekcja pokory, bo kto próbował chociaż choć raz zrobić coś większego, wielowątkowego wie, że na styku wątków potrafią dziać się cuda. Oczywiście zdaję sobie sprawę, że C# niekoniecznie musi nadawać się do ciężkich obliczeniowo problemów...

Implementacja w Unity 3D

Tak się szczęśliwie złożyło, że jakiś czas temu stałem się autorem posta na blogu Aliasing Games dotyczącego właśnie gry w życie: Game of Life Unity implementation. Dla osób, które interesują się własnie Unity polecam zajrzeć bo być może znajdą one coś ciekawego dla siebie. Wersja przygotowana na bloga była dosyć prosta i uboga. Postanowiłem ją nieco rozbudować o jakiś interfejs użytkownika oraz dodać opcje takie jak definiowanie rozmiaru gry. Działanie aplikacji można podejrzeć tutaj:

Jeśli ktoś chciałby osobiście potestować aplikację, można ją odpalić tutaj: Game of Life Unity 3D, zaś cały projekt jest do ściągnięcia tutaj: Download.

Implementacja w C# (WinForms)

Cechy stworzonej przeze mnie aplikacji to:

  • rysowanie mapy z użyciem BitMapy i pictureBoxa,
  • tryb ciągłej symulacji, symulacji zadanej ilości generacji, symulacji bez rysowania,
  • możliwość modyfikacji generacji z użyciem podstawowego "malowania" po mapie,
  • zrównoleglenie wyznaczania stanu komórek w kolejnych generacjach na dowolną ilość wątków,
  • możliwość prześledzenia historii generacji,
  • pomiar wydajności (powiedzmy, że może to służyć jako prosty benchmark procesorów).

Jednym z większych problemów na jaki natrafiłem pisząc aplikację jest wydajność rysowania całej mapy. Podejmowałem próby wykorzystania w tym celu OpenGLa czy DirectXa (były nawet próby z XNA), ale okazało się, że malowanie będzie najbardziej bolesnym wąskim gardłem całości. Ostatecznie wybrałem rozwiązanie najprostsze, czyli malowanie z użyciem BitMapy, którego niestety w żaden sposób nie udało mi się zrównoleglić. Samo uaktualnianie stanu jest z kolei zrealizowane z użyciem BackgroundWorkera, który uruchamia podrzędne wątki i z użyciem odpowiednich obiektów monitoruje ich pracę (konieczne jest minimum synchronizacji). Ostatecznie, pomimo sporej ilości braków w funkcjonalności, którą chciałbym docelowo w aplikacji zamieścić, efekt symulacji AK, można zobaczyć na filmie poniżej:

W planach mam jeszcze powrót do tego projektu w celu wprowadzenia pewnych zmian, zarówno w interfejsie jak i samej funkcjonalności. Chciałbym też dorzucić nieco funkcjonalności w postaci możliwości bezpośredniego zgrywania zawartości mapy do gifów czy możliwość bardziej efektywnego modyfikowania generacji. Dokończenia wymaga też silnik symulacji bazujący na podwójnym buforowaniu. Dlatego póki co projektu swojego nie zamieszczam publicznie ale jeśli ktoś byłby zainteresowany, proszę o kontakt!