Задание 1. Клеточные автоматы

Авторы задания:
Анна Дегтярева (annooshca@bk.ru)
Алла Масленникова (prozerpina@newmail.ru)

Цель задания

Познакомиться со средой программирования Windows. Реализовать визуализацию клеточного автомата.

Описание задания

Общая теория

Клеточные автоматы являются дискретными динамическими системами, поведение которых полностью определяется в терминах локальных взаимозависимостей их состояний. Клеточные автоматы образуют общую парадигму параллельных вычислений, подобно тому, как это делают машины Тьюринга для последовательных вычислений.

Клеточный автомат представляет собой равномерную n-мерную сетку (конечную или бесконечную), каждая ячейка (клетка) которой может принимать состояние из некоторого набора состояний; время идет дискретными шагами, а законы развития (изменения состояний клеток) выражаются единственным для всех ячеек набором правил, например небольшой справочной таблицей, по которой любая ячейка на каждом шаге вычисляет свое новое состояние по состояниям ее близких соседей. Работа клеточного автомата начинается с некоторого начального состояния - начальные состояния задаются для каждой ячейки сетки. На каждом такте автомат меняет свое состояние - каждая ячейка вычисляет свое новое состояние по заданному набору правил.

Механизм клеточных автоматов может быть сформулирован по-другому. Если с каждой клеткой, находящейся в некотором состоянии, ассоциировать некий объект (в каждый момент времени объект знает, с какой клеткой он ассоциирован, то есть в какой клетке он "находится"), то развитие клеточного автомата может быть переформулировано как "жизнедеятельность" этого объекта. Если автомат имеет более двух состояний, то все кроме одного (нулевого состояния) считаются состояниями объекта, а нулевое состояние считается отсутствием объекта в клетке. Объект может двигаться и менять свое состояние.

На каждом такте объект осматривает своих соседей - есть ли в соседних клетках другие объекты и есть ли пустые соседние клетки - и в зависимости от количества объектов в соседних клетках, наличия пустых клеток и своего состояния решает по заданному набору правил, оставаться ли ему на месте либо двигаться (и в каком направлении) и менять ли ему свое состояние (и на какое). На каждом такте все объекты такой системы передвигаются одновременно, т.е. система тактируема.

Если задан подходящий набор правил, то такой механизм достаточен для поддержания целой иерархии структур и явлений. Клеточные автоматы дают полезные модели для многих исследований в естественных науках - моделирование химических и физических процессов, исследование биологических процессов, проведение исследований по "Искусственной жизни" (Artificial Life).

Общие правила построения клеточных автоматов можно сформулировать следующим образом:

• Набор состояний ячеек (или объектов) конечен (0, 1, … , N).
• Соседями являются ограниченное число ячеек, часто это ближайшие ячейки.
• Правила, задающие динамику развития клеточного автомата, обычно имеют простую функциональную форму и зависят от решаемой проблемы (обычно представляют собой инструкции типа "если состояние этой ячейки (объекта) равно N, состояние ячейки (объекта) справа равно M, а состояние ячейки (объекта) слева равно K, то поменять состояние ячейки на L").
• Клеточный автомат является тактируемой системой, т.е. смена состояний ячеек (объектов) происходит одновременно.

Клеточные автоматы различаются количеством состояний клеток, размерностью сетки и правилом изменения состояний клеток. Мы рассмотрим некоторые разновидности автоматов с двумерной сеткой. В двумерных автоматах соседями клеток обычно считаются 5 клеток - сама клетка и 4 ее непосредственных недиагональных соседа (окрестность фон Неймана), или 9 клеток - сама клетка и 8 ее непосредственных соседей, включая диагональные клетки (окрестность Мура).

Состояние клеточного автомата на двумерной сетке может быть описано матрицей, например:

Здесь состояния клеток записываются в соответствующих ячейках матрицы. (Если говорить в терминах объектов, то ячейки, помеченные 0 - пустые, а ячейки, помеченные 1 - содержат объект).

Намного интереснее представить состояние не в виде матрицы, а в виде изображения, где каждый пиксел соответствует ячейке, и текущий цвет пиксела определяется состоянием ячейки.

Конкретные примеры клеточных автоматов

• Тьюрмиты
  

  Начальное состояние автомата - на сетке присутствует единственный объект в произвольной ячейке сетки, остальные ячейки пусты. Этот единственный объект назовем тьюрмитом. В каждый момент времени тьюрмит знает свое положение (текущую активную ячейку), цвет и состояние. В зависимости от этих трех параметров тьюрмит на каждом такте может поменять свое положение, цвет и состояние в соответствии с правилами. Ячейки, в которых тьюрмита нет, не могут менять свой цвет (если тьюрмит перекрасил ячейку, от она остается такого цвета, в какой ее перекрасили, до тех пор пока ее не перекрасят еще раз).

  Правила записываются в виде:
  
  <текущее состояние><текущий цвет><новый цвет><направление перемещения><новое состояние>

  Состояния принято обозначать латинскими буквами; цвета - числами от 0 до 15 (16-ти цветовая палитра), причем начальный цвет черный (это не жесткое ограничение, при желании цветовую гамму можно обогатить и придумать свои обозначения); направление перемещения изменяется относительно текущего курса тьюрмита, обозначается числами -1 (повернуть налево), 1 (повернуть направо), 0 (прямо).

  Например, правило А 0 15 0 В означает, что если тьюрмит находится в состоянии А и стоит на черной клетке, то он должен покрасить ее в белый цвет, продвинуться на одну клетку в текущем направлении и перейти в состояние В.

  Таким образом, если А - начальное состояние тьюрмита, 0 - начальный цвет, то набор правил тьюрмита должен содержать правило А 0 _ _ _.

  Состояние такого автомата после нескольких сот итераций выглядит вот так:
  
  Лабиринт
  

  Состояние автомата

  Набор правил A   0   1   -1   A A   1   2   -1   A A   2   3   -1 A A   3   4   -1 A A   4   5   -1 A A   5   6   1 B B   0   1   1 A B   5   6   -1 B B   6   7   -1 B B   7   8   -1 B B   8   9   -1 B B   9   10   -1 B B   10   11   -1 B B   11   12   -1 B B   12   13   -1 B B   13   14   -1 B B   14   15   -1 B B   15   0   -1 B

  
  Остров невезения
  

  Состояние автомата

  Набор правил A   0   1   -1   B A   1   2   -1   B A   2   3   -1   B A   3   4   -1   B A   4   5   1   B A   5   6   1   B A   6   7   1   B A   7   8   1   B A   8   9   -1   B A   9   10   -1   B A   10   11   -1   B A   11   12   -1   B A   12   13   1   B A   13   14   1   B A   14   15   1   B A   15   0   1   A B   0   1   1   B B   1   2   1   A B   2   3   1   A B   3   4   1   A B   4   5   -1   A B   5   6   -1   A B   6   7   -1   A B   7   8   -1   A B   8   9   1   A B   9   10   1   A B   10   11   1   A B   11   12   1   A B   12   13   -1   A B   13   14   -1   A B   14   15   -1   A B   15   0   -1   A

  
  Вертушка
  

  Cостояние автомата

  Набор правил A   0   2   0   C A   2   0   0   B B   2   2   1   A B   15   2   1   A C   2   0   -1   A C   0   15   -1   A C   15   2   -1   A

  
  Желтый квадрат
  

  Состояние автомата

  Набор правил A   0   14   0   B B   0   14   0   C C   0   14   0   E E   0   14   0   F F   0   14   0   J J   0   13   -1   A A   14   13   0   A A   13   14   0   A J   14   13   0   A J   13   14   1   A

• Кристаллы
  

  Кристаллы - это разновидность монохромного клеточного автомата. Каждая ячейка сетки может принимать одно из двух состояний - либо 0, либо 1. Начальное состояние автомата - единственная ячейка с ненулевым состоянием.

  На каждом такте для всех ячеек автомата состояние считается следующим образом.

  1. Посчитать количество ненулевых соседей. Используется окрестность из 5 ячеек.
  2. В зависимости от того, является ли текущее состояние клетки 0 или 1, используем различные наборы правил вычисления нового состояния

  Правила могут иметь следующий вид:

  текущее состояние	количество ненулевых соседей	новое состояние
  0	0	0
  0	1	1
  0	2	0
  0	3	0
  0	4	0
  1	0	1
  1	1	1
  1	2	1
  1	3	1
  1	4	0

  Первые два столбца фиксированы - в них задаются все возможные комбинации текущего состояния и количества соседей. Третий столбец уникален для каждого конкретного автомата-кристалла.
  Если фиксировать порядок записи в первых двух столбцах (для всех автоматов такой, как показано в таблице), то третий столбец можно рассматривать как двоичный код некоторого числа. Число 0100011110 - это двоичный код числа 286. Таким образом любое число от 0 до 1023 однозначно задает правила построения кристалла. Состояния автомата, построенного по правилу 286, выглядят вот так (цифрой обозначен номер итерации):

  
  

  Другие примеры кристаллов:
  
  Салют
  Правило 324
  Состояния:
  
  Ромбики
  Правило 465
  
  
  Оренбургский пуховый платок
  Правило 501
  
  
  Бабушкино вязанье
  Правило 471
  
  
  

Требования к программе

Оценка

Оформление

Оформление не отличается от обычного.

ZIP-архив с исходными текстами и исполняемыми файлами, названный по схеме GZV_nnnnnnnn.zip (где G - последняя цифра номера группы, Z - номер задания, V - номер версии задания, nnnnnnnn - номер студенческого билета) присылайте на assign1@graphics.cs.msu.su

Например, студент 206 группы с номером студенческого билета 06529042, сдающий обновленную (вторую) версию программы по первому заданию, должен прислать архив с именем 612_06529042.zip.

Также смотрите здесь, какие файлы нам присылать и как их оформить Советуем очень внимательно прочитать весь FAQ

Не забудьте положить в архив файл readme.txt. В файле описать интерфейс програмы (алгоритм работы с программой, пункты меню, управляющие клавиши) и указать следующие подзадания:

!Внимание: обратите внимание на правильное именование и структуру архива с работой, а также на содержание файла readme.txt. Если ваша работа не будет соответствовать требованиям, баллы могут быть снижены.

Результаты работы

Результаты смотрите в интернете и/или на стенде около комнаты 703
Все вопросы и комментарии присылать авторам и проверяющим или задавать в форуме. Ответы на наиболее часто задаваемые вопросы будут отражены в разделе ЧаВо по заданию

Примечания

1. Задание выполняется строго индивидуально. За совместную работу или обмен кусками кода ставится ноль баллов всем участникам, если факт командной работы не был указан в readme.txt заданий.
2. Рекомендуется написание программы под семейство ОС Windows. Написание под другие операционные системы нежелательно и может вызвать задержки с проверкой таких работ.

Я не умею программировать под ОС Windows, а в задании сказано, что писать нужно под эту операционную систему. Что делать?

Учиться, тем более что к курсу прилагаются материалы по программироваю под Win32 для начинающих. Также в магазинах очень много книг, а интернете - много информации, а учиться не составляет большой проблемы. Но не откладывайте это на потом. Первые задания достаточно легкие и предполагают изучение. В дальнейшем у вас может просто не хватить времени.
В библиотеке курса вы можете найти подробное пособие по программированию под ОС Windows - вот прямая ссылка. К пособию прилагаются примеры кода простейших программ, написанных в средах Visual C++ 6.0, Delphi 5 и CBuilder 5.

Что значит "тьюрмит поворачивает налево/направо"?

Допустим, тьюрмит движется на восток. На картинке темно-серым цветом обозначено, где тьюрмит был на предыдущем такте, красным - текущее положение тьюрмита, а светло-серым - где он окажется на следующем такте при движении налево (верхний вариант), направо (нижний вариант) или прямо (средний вариант).