algorytm.org

Automaty komórkowe

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Automaty komórkowe
Ocena użytkowników:***** / 10
SłabyŚwietny 
Wpisany przez Tomasz Nędza, 28 lipca 2005 18:44

Automat komórkowy jest to obiekt składający się z sieci komórek, które posiadają pewien stan z określonego zbioru, oraz algorytmu (zbioru reguł), który określa stan danej komórki, najczęściej w zależności od stanów komórek sąsiednich. Brzmi to skomplikowanie, ale okaże się za chwilę, że w praktyce w prosty sposób osiągnąć będzie można zadziwiające efekty.

Automaty komórkowe miały być początkowo przydatne do symulacji procesów fizycznych, w których bierze udział wiele oddziałujących ze sobą elementów. Później automaty komórkowe wykorzystano także między innymi do generowania grafiki (głównie tekstur).

Przejdźmy jednak do praktyki.
Pewnie zastanawiacie się, czym dokładnie jest ten algorytm, o którym wspomniałem na początku. W zasadzie wystarczy, aby przetwarzał on w odpowiedniej kolejności komórki zmieniając w ustalony sposób ich wartości (stany). W zależności od wyboru algorytmu i stanów początkowych osiągniemy inny, trudny do przewidzenia efekt.

Najsłynniejszym chyba automatem komórkowym jest LIFE ("gra w życie"), który jest modelem żyjącego środowiska. Każda z komórek może posiadać dwa stany: żywy i martwy. Autor tego automatu, angielski matematyk John Conway, założył następujące reguły:
  • żywa komórka umiera z samotności, gdy posiada jednego lub żadnego sąsiada (inną żywą komórkę)
  • żywa komórka posiadająca dwóch lub trzech sąsiadów podtrzymuje życie
  • żywa komórka umiera, gdy posiada więcej niż trzech sąsiadów
  • martwa komórka posiadająca 3 sąsiadów ożywa
Poniżej zamieszczam 3 kolejne fazy wygenerowane przez załączony program (algorytm 1.1):
ImageImageImage
Należy pamiętać, aby zainicjalizować siatkę komórek pewnymi początkowymi wartościami. Ja we wszystkich przedstawionych algorytmach tablicę wypełniam w sposób losowy, ale można to robić według jakiegoś algorytmu.
Już po pierwszym przykładzie widać, że przy obliczaniu stanu komórki brać pod uwagę można na przykład stan komórki przetwarzanej oraz stany komórek sąsiadujących (w pionie i/lub w poziomie i/lub na ukos).
Inny algorytm może być następujący:
Zliczana jest liczba komórek w stanie "1", z jakimi sąsiaduje komórka w pionie i w poziomie. Jeśli liczba ta wynosi 1 lub 3, to komórka przechodzi w stan "0", jeśli 4 - pozostaje bez zmian. Natomiast jeśli wynosi ona 2, to komórka przyjmuje stan "1". (algorytm 1.2)
W kolejnym algorytmie ponownie zliczamy liczbę sąsiednich komórek ze stanem "1", ale tym razem bierzemy pod uwagę także te leżące po ukosie. Jeśli liczba ta jest mniejsza od 4, to komórka przechodzi w stan "0", gdy większa od 4 - w stan "1". W przeciwnym wypadku, czyli gdy komórka ma dokładnie czterech sąsiadów o stanie "1", stan danej komórki pozostaje bez zmian.
I tym razem przedstawiam rysunki uzyskane po 3 kolejnych cyklach (algorytm 1.3):
ImageImageImage
We wszystkich dotychczas opisanych algorytmach komórki mogły posiadać tylko 2 stany. Teraz przedstawię algorytmy operujące na 256-stanowych komórkach, choć łatwo można je rozszerzyć do 16- czy 32-bitowych stanów.
Oczywiście można zadziałać podobnie jak w poprzednich przykładach - stan komórki będzie określany przez stan sąsiednich komórek. Zupełnie inna będzie jednak druga rodzina algorytmów. Zamiast cykli obliczeniowych, w których przetwarzane są wszystkie komórki, tutaj obraz rysować będzie "robak", który porusza się po siatce i modyfikuje każdą komórkę, na której się znajdzie. Poza algorytmem zmieniającym stan komórki należy pamiętać o algorytmie poruszającym "robakiem". Można to robić w sposób losowy lub też użyć zmiennego azymutu, czyli zmiennej określającej aktualny zwrot "robaka" - kierunek, w którym przemieści się on w kolejnym kroku. Nie będę opisywał użytych przeze mnie algorytmów, ponieważ są one wymyślone podczas pisania programu i przystosowane do tego, aby wynik działania był "atrakcyjny" pod względem wygenerowanej grafiki. Poniżej zamieszczam kilka przykładowych obrazków.
Algorytm 2.1 (po 1000, 2000 i 4000 kroków, współczynnik=100)
ImageImageImage
Algorytm 2.2 (po 500, 2000 i 3000 kroków, współczynnik=20)
ImageImageImage
Algorytm 2.3 (po 10000 kroków, współczynnik=1000)
Image
Algorytm 2.4 (po 15000 kroków, współczynnik=100)
Image
Algorytm 2.5 (po 10000 kroków, współczynnik=50)
Image
Algorytm 2.6 (po 3000 kroków, współczynnik=20)
Image
Algorytm 2.7 (po 3000 kroków, współczynnik=500)
Image
Mam nadzieję, że zainteresował Was ten temat. Dla szczególnie ciekawych dołączam kod program, dzięki któremu wygenerowałem wszystkie przykłady.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz NędzaDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 11 czerwca 2011 14:28
Dodaj komentarz