Automaty kom≤rkowe

WstΩp

Wszyscy chyba wiemy, co to s▒ fraktale. Te piΩkne, kolorowe obrazy i algorytmy do ich tworzenia s▒ bardzo znane. Niewielu jednak wie, ┐e obok nich istnieje jeszcze wiele innych r≤wnie fascynuj▒cych dziedzin grafiki komputerowej. Jedn▒ z nich s▒ tzw. automaty kom≤rkowe (cellular automats). Po dw≤ch latach eksperyment≤w z nimi postanowi│em napisaµ artyku│ o tej grupie algorytm≤w.

Automat kom≤rkowy to specjalny algorytm oraz struktura danych, na kt≤rej on operuje. S│u┐y do generowania grafiki 2D. Jak sama nazwa wskazuje, owa struktura danych sk│ada siΩ z kom≤rek. Deklarujemy wiΩc tablicΩ:

var
Tab: array[0..TabWidth-1, 0..TahHeight-1] of TCell;

Mo┐e ona byµ kwadratowa lub prostok▒tna. Typ TCell to typ danych, jakie przechowuje ka┐da kom≤rka. BΩdzie o tym mowa ni┐ej. Czy ka┐da kom≤rka tablicy reprezentuje jeden piksel? Mo┐e, ale nie musi. Czasami efekt bΩdzie lepszy, je┐eli ka┐da z nich bΩdzie odrysowywana na ekranie jako kwadrat o wymiarach kilku pikseli.

Czym jest ≤w algorytm, kt≤ry na tej tablicy operuje? Mo┐e on wygl▒daµ naprawdΩ bardzo r≤┐nie. Og≤lnie chodzi o to, ┐eby w pΩtli przetwarzaµ wszystkie lub niekt≤re kom≤rki (w okre╢lonej kolejno╢ci) zmieniaj▒c odpowiednio ich warto╢µ. Da to w efekcie pewien trudny do przewidzenia efekt graficzny. Ciekaw▒ cech▒ wsp≤ln▒ automat≤w kom≤rkowych i fraktali jest, ┐e proste algorytmy potrafi▒ generowaµ ca│kiem skomplikowane wzory. Poni┐ej przedstawiam 2 znane mi typy automat≤w kom≤rkowych.

Automat kom≤rkowy 1

Ka┐da kom≤rka bΩdzie typu logicznego:

var
Tab: array[0..TabWidth-1, 0..TahHeight-1] of Boolean;

Znaczy to, ┐e mo┐e byµ w jednym z 2 stan≤w. Na ekranie bΩdziemy to przedstawiali jako kom≤rka wygaszona (o kolorze t│a np. czarna) lub za╢wiecona (o zdefiniowanym kolorze np. bia│a). W tej grupie algorytm≤w najlepiej ka┐d▒ kom≤rkΩ na ekranie prezentowaµ jako ma│y kwadracik o wymiarach kilka na kilka pikseli robi▒c miΩdzy kom≤rkami jednopikselowe odstΩpy.

Na pocz▒tku inicjalizujemy tablicΩ zupe│nie losowymi warto╢ciami:

Randomize;
for Y := 0 to TabHeight-1 do
for X := 0 to TabWidth-1 do
Tab[X, Y] := (Random(2) = 0);

Mo┐esz te┐ spr≤bowaµ rozmie╢ciµ warto╢ci pocz▒tkowe wg jakiego╢ okre╢lonego algorytmu. Ja tego nie pr≤bowa│em. Mo┐e otrzymasz jakie╢ ciekawe efekty?

G│≤wny algorytm to pΩtla, w kt≤rej wykonywane s▒ kolejne cykle obliczeniowe. W ka┐dym takim cyklu przetwarzane s▒ wszystkie kom≤rki. Nie jest przy tym wa┐na kolejno╢µ tzn. czy s▒ przetwarzane od g≤ry czy od do│u, od lewej czy od prawej strony.

for I := 0 to CycleCount-1 do
for Y := 0 to TabHeight-1 do
for X := 0 to TabWidth-1 do
ProcessCell(X, Y);

Oczywi╢cie ┐eby widzieµ jak automat dzia│a, warto co jaki╢ czas pokazaµ na ekranie bie┐▒cy stan tablicy. W toku kolejnych cykli oblicze± zupe│nie losowy na pocz▒tku uk│ad kom≤rek zaczyna siΩ porz▒dkowaµ tworz▒c pewne wzory i motywy. Kolejne cykle zmieniaj▒ w obrazie ju┐ coraz mniej. Trwa to a┐ ca│o╢µ osi▒gnie swoisty stan r≤wnowagi, w kt≤rym kolejne przeliczenie nie zmieniaj▒ ju┐ nic lub prawie nic. Stanie siΩ tak po ok. kilku lub kilkunastu cyklach. W zasadzie za efekt dzia│ania automatu uznaµ nale┐y obraz wygenerowany po tych cyklach, po kt≤rych nic ju┐ siΩ w nim nie zmienia. Samo powstawanie tego obrazu jest jednak na tyle ciekawe i efektowne, ┐e warto r≤wnie┐ sam ten proces obserwowaµ. Co jest charakterystyczne: za ka┐dym razem otrzymujemy inny obraz (bo zale┐y on od danych pocz▒tkowych, kt≤re s▒ przecie┐ losowane), ale zawsze wystΩpuj▒ w nim te same motywy i ma on ten sam, jakby, wz≤r (bo ten zale┐y od algorytmu). Za pomoc▒ tej kategorii algorytm≤w mo┐na otrzymaµ np. wz≤r przypominaj▒cy │aty niepopularnego ostatnio zwierzΩcia, jakim jest krowa.

Co robi procedura ProcessCell? Przetwarza pojedyncz▒ kom≤rkΩ. Przetwarza j▒ wg pewnego algorytmu. To on w│a╢nie stanowi istotΩ automatu. I tu jest co╢ naprawdΩ wspania│ego: mo┐esz w zasadzie wymy╢laµ dowolne algorytmy, a ka┐dy z nich da w efekcie inny wz≤r. Obliczaj▒c nowy stan dla przetwarzanej aktualnie kom≤rki pod uwagΩ mo┐esz wzi▒µ m.in.:

  • Stan kom≤rki przetwarzanej przed jej przetworzeniem.
  • Stany kom≤rek s▒siaduj▒cych (tylko w poziomie i w pionie lub tak┐e na ukos). Mo┐esz np. zliczaµ, ile s▒siednich kom≤rek jest w stanie True i na tej podstawie podejmowaµ jakie╢ dzia│anie. UwzglΩdnij tylko co bΩdzie, je╢li rozpatrywana kom≤rka le┐y na skraju tablicy (┐eby nie by│o Access Violation).

Ja wymy╢li│em 3 algorytmy:

Algorytm 1

var
Count: Integer;
begin
//OBLICZENIA
Count := 0;
//Powy┐ej
if Y > 0 then
if Tab[X, Y-1] = True then
Inc(Count);
//Poni┐ej
if Y < TabHeight-1 then
if Tab[X, Y+1] = True then
Inc(Count);
//Z lewej
if X > 0 then
if Tab[X-1, Y] = True then
Inc(Count);
//Z prawej
if X < TabWidth-1 then
if Tab[X+1, Y] = True then
Inc(Count);

//Zasada I
//L + 3H = H
if Count = 3 then
Tab[X, Y] := True;

//II zasada
//H + 1H = L
if Count = 1 then
Tab[X, Y] := False;

//III zasada
if Count = 4 then
Tab[X, Y] := False;

Zliczana jest liczba kom≤rek w stanie True, z jakimi s▒siaduje kom≤rka przetwarzana w pionie oraz w poziomie. Je╢li ta liczba wynosi 1 lub 4 - kom≤rka przechodzi w stan False. Je╢li wynosi 3 - w stan True. Je╢li za╢ 2 - pozostaje bez zmian. Zauwa┐, ┐e nie jest tu brane pod uwagΩ, jak▒ warto╢µ mia│a poprzednio kom≤rka przetwarzana.

Algorytm 2

var
Count: Integer;
begin
//OBLICZENIA
Count := 0;
//Powy┐ej
if Y > 0 then
if Tab[X, Y-1] = True then
Inc(Count);
//Poni┐ej
if Y < TabHeight-1 then
if Tab[X, Y+1] = True then
Inc(Count);
//Z lewej
if X > 0 then
if Tab[X-1, Y] = True then
Inc(Count);
//Z prawej
if X < TabWidth-1 then
if Tab[X+1, Y] = True then
Inc(Count);

//Z lewej - u g≤ry
if (X > 0) and (Y > 0) then
if Tab[X-1, Y-1] = True then
Inc(Count);
//Z prawej - u g≤ry
if (X < TabWidth-1) and (Y > 0) then
if Tab[X+1, Y-1] = True then
Inc(Count);
//Z lewej - u do│u
if (X > 0) and (Y < TabHeight-1) then
if Tab[X-1, Y+1] = True then
Inc(Count);
//Z prawej - u do│u
if (X < TabWidth-1) and (Y < TabHeight-1) then
if Tab[X+1, Y+1] = True then
Inc(Count);

//Zasada I
if Count > 4 then
Tab[X, Y] := True;

//II zasada
if Count < 4 then
Tab[X, Y] := False;

//III zasada
if Count = 4 then
Tab[X, Y] := Tab[X, Y];

W tym algorytmie zliczana jest ilo╢µ aktywnych (True) kom≤rek s▒siaduj▒cych z rozpatrywan▒ tak┐e na ukos. Mo┐e wiΩc ich byµ od 0 do 8. Je╢li ich liczba jest mniejsza od 4 - kom≤rka przetwarzana przechodzi w stan False. Je╢li wiΩcej od 4 - w stan True. Je╢li za╢ wynosi dok│adnie 4 - warto╢µ kom≤rki pozostaje bez zmian.

Algorytm 3

var
Count: Integer;
begin
//OBLICZENIA
Count := 0;
//Powy┐ej
if Y > 0 then
if Tab[X, Y-1] = True then
Inc(Count);
//Poni┐ej
if Y < TabHeight-1 then
if Tab[X, Y+1] = True then
Inc(Count);
//Z lewej
if X > 0 then
if Tab[X-1, Y] = True then
Inc(Count);
//Z prawej
if X < TabWidth-1 then
if Tab[X+1, Y] = True then
Inc(Count);

//Zasada I
if Count < 2 then
Tab[X, Y] := False;

//II zasada
if Count > 2 then
Tab[X, Y] := True;;

Tu zliczane s▒ tylko kom≤rki s▒siaduj▒ce w pionie i w poziomie. Je╢li ich liczba jest mniejsza od 2 - kom≤rka przechodzi w stan False. Je╢li wiΩksza - w stan True. Je╢li jest r≤wna 2 - pozostaje bez zmian.

ZachΩcam do samodzielnego eksperymentowania z t▒ klas▒ automat≤w kom≤rkowych - naprawdΩ warto. Z pewno╢ci▒ uda Ci siΩ wymy╢liµ jeszcze lepsze, │adniejsze, ciekawsze algorytmy. Nie jest to trudne. ZachΩcam tak┐e wszystkich, kt≤rzy ciekawi s▒ jak to wygl▒da do ╢ci▒gniΩcia i zainstalowania wygaszacza ekranu mojego autorstwa - ProgrameX Cellular Automat Screensaver.

Automat kom≤rkowy 2

Tutaj ka┐da kom≤rka tablicy reprezentuje jeden piksel. W zasadzie to mo┐e byµ zar≤wno typu Boolean (2 kolory), Byte (256 odcieni szaro╢ci - te┐ ca│kiem fajnie wychodzi), jak i TColor (16 milion≤w kolor≤w). Tyle ┐e tablica nie jest obrazem samym w sobie. Mo┐e mieµ ca│kiem ma│e wymiary - jak np. 20 x 20. Cech▒ charakterystyczn▒ tego automatu jest, ┐e generuje on tekstury, kt≤re s▒ rozk│adalne s▒siaduj▒co tzn. roz│o┐one jedna obok drugiej daj▒ jednolity wz≤r i nie s▒ widoczne │▒czenia miΩdzy nimi. TablicΩ t▒ inicjalizujemy warto╢ci▒ 0, czyli kolorem czarnym.

Inny jest zupe│nie algorytm - tu nie ma cykli, w kt≤rych przeliczane by│yby wszystkie kom≤rki po kolei. Jest natomiast "robaczek". Chodzi on sobie po tablicy i modyfikuje ka┐dy piksel, na kt≤rym stanie. »eby tekstura by│a rozk│adalna s▒siaduj▒co, kiedy robaczek wyjdzie za tablice musi tym samym wr≤ciµ z drugiej strony. Opisuj▒ go 3 zmienne: bie┐▒ca pozycja na X i na Y oraz tzw. azymut. Ta ostatnia to liczba z zakresu od 0 do 7 opisuj▒ca bie┐▒cy zwrot robaka - a wiΩc kierunek, w kt≤rym przemie╢ci siΩ on w nastΩpnym kroku. Dla przyk│adu: 0 mo┐e oznaczaµ zwrot do g≤ry, 1 po skosie do g≤ry na prawo, 2 w prawo, 4 na d≤│, 6 w lewo itd. Oczywi╢cie mo┐esz sobie napisaµ tak, ┐eby zwrot m≤g│ byµ tylko do g≤ry, w d≤│, w prawo lub w lewo - bez 4 kierunk≤w po skosie. Ja tego nie pr≤bowa│em.

Automat kom≤rkowy tej kategorii charakteryzuj▒ 2 algorytmy. Pierwszy to obliczanie, jaki azymut ma byµ nadany naszemu robaczkowi do ruchu w nastΩpnej turze. I w│a╢nie tu jest co╢ wspania│ego - aby go obliczyµ, mo┐esz u┐yµ praktycznie dowolnych danych. Oto moje pomys│y:

  • Kolor piksela, na kt≤rym robaczek stoi (jako ca│o╢µ b▒d╝ jedna ze sk│adowych)
  • Licznik, kt≤rego warto╢µ bΩdzie zwiΩkszana po ka┐dym kroku
  • Jaka╢ sta│a liczba zdefiniowana dla ca│ej operacji
  • Warto╢µ losowa (ta bardzo du┐o zmienia - bez jej u┐ycia tekstura ma kszta│t regularny i uporz▒dkowany, po jej zastosowaniu wygl▒da na chaotyczn▒ i jest za ka┐dym wygenerowaniem trochΩ inna)
  • Poprzednia warto╢µ azymutu (czyli nie nadawaµ mu nowej warto╢ci, ale modyfikowaµ j▒ wzglΩdem poprzedniej).

Mo┐esz te dane wykorzystywaµ w dowolny spos≤b - dowolnie przetwarzaµ ich warto╢ci za pomoc▒ operacji bitowych, arytmetycznych czy trygonometrycznych i dowolnie │▒czyµ ze sob▒ tworz▒c niezliczone ilo╢ci r≤┐nych algorytm≤w. Ka┐dy z nich da w efekcie zupe│nie inny obraz. Ciekawym rozwi▒zaniem jest te┐ stworzenie wg jakiego╢ algorytmu tablicy, w kt≤rej ka┐dej warto╢ci jednego parametru bΩd▒ przypisane odpowiednie warto╢ci dla wyniku operacji.

Zauwa┐, ┐e nawet niewielka zmiana szeroko╢ci lub wysoko╢ci obrazka czy sta│ej (je╢li taka jest u┐ywana w algorytmie) spowoduje zupe│n▒ zmianΩ obrazu. Pomy╢l wiΩc: ilo╢µ r≤┐nych ich kombinacji jest praktycznie niesko±czona!

Drugi algorytm opisuje, w jaki spos≤b modyfikowany ma byµ piksel, na kt≤rym robaczek stoi. Mo┐e to byµ zwyk│e rozja╢nianie - np. dla obrazu w grayscale. Dla obrazu kolorowego mo┐esz zrobiµ co╢ takiego: wykonaµ tych kilka (-dziesi▒t? -set?) tysiΩcy krok≤w dla ka┐dej ze sk│adowych RGB za ka┐dym razem modyfikuj▒c jedn▒ z nich. Albo - po prostu operowaµ na warto╢ci liczbowej koloru piksela jako ca│o╢ci. Jedno jest pewne - musisz uwzglΩdniaµ kolor, jaki mia│ piksel przed dokonaniem na nim operacji. Mo┐esz np. rozja╢niaµ czy jako╢ inaczej modyfikowaµ - ale zawsze wzglΩdem poprzedniej warto╢ci. Jest to konieczne dlatego, ┐e na ka┐dy piksel robaczek staje po kilkaset albo nawet kilka tysiΩcy razy.

Nie bΩdΩ tu kopiowa│ kodu ╝r≤d│owego procedur - zamiast tego do│▒czam do artyku│u plik CAdemo.rar. My╢lΩ, ┐e kod dla wszystkich oka┐e siΩ czytelny i zrozumia│y. Zwr≤µ uwagΩ na jedn▒ rzecz: taki prosty program (jeden ma│y modu│) potrafi generowaµ tak r≤┐norodne i ciekawe tekstury. W zasadzie mo┐na je podzieliµ na 2 grupy: te zawieraj▒ce regularne geometryczne wzory (bez u┐ycia warto╢ci losowej) oraz plazmoidalne struktury o charakterze raczej nieregularnym (z u┐yciem warto╢ci losowej). Oto przyk│ady:

Zako±czenie

Tak w│a╢nie prezentuj▒ siΩ efekty mojej pracy z automatami kom≤rkowymi oraz m≤j aktualny stan wiedzy o nich. Nie masz chyba po tym wszystkim ju┐ w▒tpliwo╢ci, ┐e jest to dziedzina grafiki komputerowej 2D r≤wnie fascynuj▒ca jak fraktale i inne algorytmy? Mo┐na te┐ znale╝µ dla niej ogromne zastosowanie. Pomy╢l: po co zapisywaµ r≤┐ne tekstury w plikach graficznych, jak mo┐na je sobie za ka┐dym razem wygenerowaµ?

Literatura:

  1. "Wirtualne ┐ycie" - PC Shareware Nr 04/99 str. 15
  2. "Kurs C++ czΩ╢µ 7" - CD-Action Nr 11/2000 str. 125

Adam Sawicki
sawickiap@poczta.onet.pl