Клеточный автомат — это система, состоящая из клеток с численными значениями в сетке, а также из правил, определяющих поведение этих клеток. Многократно применяя правило к каждой клетке сетки параллельно с визуализацией сетки, часто можно получить эффект некоего эволюционирующего организма со сложным и замысловатым поведением, даже если правила относительно просты.
Клеточные автоматы имеют различные формы, виды и размерности. Наверно, самым знаменитым клеточным автоматом является конвеевская игра «Жизнь» (Conway's Game of Life, GOL). Она состоит из двухмерной сетки, в которой каждая клетка содержит двоичное значение (живая или мёртвая). Сопутствующие правила на основании состояния соседних клеток определяют, должна ли клетка быть мёртвой или живой. Правила гласят, что живая клетка умирает от одиночества, если вокруг неё меньше 2 живых клеток. Если живы больше трёх соседних клеток, она погибает от перенаселённости. Другими словами, клетка «выживает», если вокруг неё ровно 2 или 3 живых соседних клеток. Чтобы мёртвая клетка ожила, у неё должно быть ровно 3 живых соседних клеток, в противном случае она остаётся мёртвой. Пример автомата GoL, итеративно проходящий несколько состояний, показан ниже.
Ещё один знаменитый вариант клеточного автомата одномерен; он называется элементарным клеточным автоматом (Elementary Cellular Automaton, ECA). Именно его мы реализуем в этом посте.
Читать полностью »