Nie wyobrażam sobie lepszej zachęty do nauki automatów komórkowych niż analiza niedawno wydanej gry Noita, której twórcy szczycą się, że każdy piksel na ekranie jest animowany i podlega prawom fizyki. Oznacza to tyle, że mimo oprawy w stylu “retro”, jeśli strzelimy w szklaną butlę z wodą to ta pęknie, a woda realistycznie się z niej wyleje przy okazji gasząc ogień i zamieniając się w kamień w zetknięciu z lawą.

W Noita takich zależności jest o wiele więcej; przykładowo, poza wyżej wspomnianą wodą mamy kwas, który wchodzi w reakcję z innymi cząsteczkami, łatwopalny proch czy choćby… whiskey, które również ma swoje unikalne właściwości (wszyscy wiemy jakie hehe). Pikselowa oprawa graficzna – choć piękna – może uśpić naszą czujność, jednocześnie wprawiając w zadyszkę nawet całkiem mocne procesory, które muszą przecież wyliczyć ruch i reakcję tysięcy pikseli na ekranie. 

Innym, nieco prostszym przykładem użycia automatów komórkowych w branży będzie Terraria, która korzysta z omawianych technik do symulacji cieczy.  

Mechanizm, który wprawia w ruch te kwadratowe prawa fizyki to właśnie Automat Komórkowy, którego zadaniem jest definicja relacji (i reakcji) między wszystkimi możliwymi elementami (komórkami) w naszej grze. Taką właśnie komórką jest każdy piksel w Noita, blok w Terrarii lub Minecrafcie. Jeśli komórka wody zetknie się z komórką ognia, powstanie komórka pary, a jeśli komórka wody nie ma pod sobą żadnej innej komórki – spadnie, imitując grawitację w prawdziwym świecie. 

Historia Automatów Komórkowych sięga lat 40 ubiegłego wieku, jednak do popularyzacji tego zagadnienia poza środowisko akademickie przyczynił się brytyjski matematyk, John Conway, który to opracował Grę w Życie. Jest to z pozoru prosty automat komórkowy, gdzie każda komórka może być “żywa” (czarna) lub “martwa” (biała). Oprócz tego mamy zbiór zasad, które decydują o ich życiu lub śmierci:

• Każda martwa komórka, która sąsiaduje z dokładnie trzema żywymi komórkami również staje się żywa, co symuluje reprodukcję w społeczeństwie.
• Każda żywa komórka, która ma dwóch lub trzech żywych sąsiadów przeżywa. 
• Każda żywa komórka, która ma mniej niż dwóch sąsiadów umiera (z samotności). Nie rozumiem tej komórki, ja bym się cieszył z małej ilości sąsiadów.
• Każda żywa komórka, która ma więcej niż trzech sąsiadów umiera z przeludnienia.

Zabawa polega na tym, że „co turę” przechodzimy przez wszystkie pola na planszy, i zamieniamy żywe i martwe komórki wedle powyższych zasad. Oczywiście robienie tego na fizycznej planszy zajęłoby dużo czasu, więc powstało wiele programów do Gry w Życie.

Wcześniej napisałem, że Gra w Życie to pozornie prosty automat. Choć jego zasady nie są skomplikowane, daje ogromne możliwości co pokazuje grono sympatyków ścigających się w tworzeniu coraz to bardziej skomplikowanych układów i plansz. Świetnie obrazuje to EPICKI film epic conway’s game of life. Przykład Gry w Życie daje do myślenia jak potężne mogą być systemy oparte na prostych zasadach, a co dopiero bardziej skomplikowane, takie jak te użyte choćby w Noita. 

Jeśli masz wątpliwości czy Gra w Życie faktycznie jest popularna, a powyższy film dalej Cię nie przekonał, to Google po wpisaniu “Gra w Życie” włącza ją w tle 🙂

Definicja

Wróćmy jednak do definicji. Automat komórkowy to system, który składa się z:

1. Sieci komórek, która stanowi obszar (planszę) automatu komórkowego. Może to być tablica 1,2 lub n-wymiarowa.  
2. Zbioru stanów komórek, czyli innymi słowy wszystkich możliwych stanów w jakich dana komórka może się znajdować.
3. Funkcji przejścia określającej warunki zmiany stanu komórki, czyli zasady naszego wirtualnego świata. Przykładowo tutaj znajdzie się reguła mówiąca, że jeśli woda zetknie się z ogniem to powstaje para

Nie jest to oczywiście super-formalna definicja. Jeśli interesują Cię bardziej uniwersyteckie treści, możesz rzucić okiem na inne materiały dostępne w sieci, choćby na Wikipedię: (https://pl.wikipedia.org/wiki/Automat_kom%C3%B3rkowy) 

Przykład:

Prostym automatem komórkowym może być system spadających klocków. Naszym obszarem działania, czyli siecią, będzie tablica 2-wymiarowa o rozmiarach 2×2. Oczywiście mogłaby być większa.

Komórka może być albo pusta, albo może znajdować się na niej “klocek” – czyli posiada dwuelementowy zbiór stanów – {klocek, pusto}.

Na ogół grawitacja działa tak, że jeśli pod przedmiotem nic się nie znajduje to on spada. Tak właśnie będzie działała nasza funkcja przejścia:

dla każdej komórki i:
	jeśli komórka i jest pusta & nad komórką i jest klocek j:
		komórka i = klocek
		komórka j = pusto

Czyli klocek “spadnie”. Na poniższym rysunku zilustrowalem 4 iteracje tej funkcji przejścia, przy pewnym początkowym rozmieszczeniu klocków.

I tyle. Na tej samej zasadzie opierają się wszystkie automaty komórkowe. Oczywiście większość z nich jest bardziej skomplikowana, ale ich trudność nie opiera się na żadnego rodzaju magii, a na większych sieciach komórek (nawet milionowych!), większym zbiorze stanów oraz bardziej skomplikowanych funkcjach przejścia. Niewiele trudniejszym przykładem automatu komórkowego będzie symulacja wody gdzie zbiorem stanów będzie {ściana, woda, pusto}, a funkcja przejścia będzie określać zachowanie poszczególnych komórek wody tak aby razem sprawiały wrażenie cieczy.

Również wcześniej omawiana Notia działa w ten dokładnie sposób, tyle, że na większą skalę. Warto zaznaczyć, że często problemem nie jest sama implementacja automatu komórkowego co optymalizacja – przetwarzanie tysięcy czy milionów komórek potrafi być kłopotliwe dla procesora, a wielowątkowość bywa problematyczna – co gdy dwa sąsiadujące bloki trafią do osobnych wątków? Przed takimi problemami stanęli właśnie twórcy gry Noita, co świetnie wytłumaczyli w zamieszczonym na YouTube filmie “Exploring the Tech and Design of Noita”, który serdecznie polecam. 

Mam nadzieję, że już rozumiesz czym są automaty komórkowe i jak ogólnie działają. W innym artykule zastosujemy powyższą teorię i stworzymy swój własny automat komórkowy.