Подразделы

Другие разделы

Дата и время

21/11/2024 19:20:53

Авторизация

Пояснения к курсовой работе

Игра "Жизнь"

Жизнь диктует свои законы,
или
КЛЕТОЧНЫЕ АВТОМАТЫ И МАШИННАЯ ГРАФИКА

[Дополнительная информация из книг Гарднера](p44756/life.html)

Жизнь — это многоклеточное сообщество, населяющее пустыни
Флатландии. Пустыня представляет собой квадратную решетку,
каждая ячейка которой вмещает одну клетку Жизни. Мерой те-
течения времени служит смена поколений Жизни, приносящая в
колонию клеток смерть и рождение.

Чтобы проследить за историей развития колонии, разместим в
пустыне клетки Жизни в их начальном положении. Смена
поколений будет происходить по следующим правилам.

1. Соседями клетки считаются все клетки, находящиеся в
восьми ячейках, расположенных рядом с данной по горизонтали, вертикали или диагонали.

2. Если у некоторой клетки меньше двух соседей, она погибает
от одиночества. Если клетка имеет больше трех соседей, она
погибает от тесноты.

3. Если рядом с пустой ячейкой окажется ровно три соседние
клетки Жизни, то в этой ячейке рождается новая клетка.

4. Гибель и рождение происходят в момент смены поколений.
Таким образом, гибнущая клетка может способствовать рождению новой, но рождающаяся клетка не может воскресить
гибнущую, и гибель одной клетки, уменьшив локальную
плотность населения, не может предотвратить гибель другой.
Так, например, колония 3x1 превращается в следующем поколении в 1x3, а колония 2x2 должно быть, живет неподалеку от
района Палм-Спрингс, поскольку она вообще никогда не меняется.

*Тема.* Напишите программу, моделирующую колонию Жизни. Исходными данными служит начальное расположение клеток, а в
качестве результата нужно получить вид сверху всех поколений
колонии.

*Рекомендации исполнителю.* Хотя этого и не видно из примеров,
некоторые колонии разрастаются невероятным образом при весьма
скромных начальных размерах. Есть другие колонии, которые
медленно перемещаются по пустыне, переходя на все новые и но-
новые территории. Ваша программа должна обрабатывать большие
колонии без чрезмерной траты памяти или времени.
Многократный просмотр большого массива для построения следующих
поколений— это банальный подход; здесь программистская задача
состоит в выборе более экономичных структур данных и
алгоритмов. Вам, возможно, захочется испытать какой-либо метод,
отслеживающий только занятые квадраты. Растущая или движущаяся
колония может выйти из поля зрения, если его положение и
границы зафиксированы, поэтому, вероятно, понадобится еще и метод вывода, перемещающий нашу точку зрения вслед за изменениями колонии.

Один из способов сокращения памяти, требуемой для запоминания
позиций, состоит в том, чтобы хранить позицию в виде массива битов, отводя
для каждой клетки один бит (а не слово памяти). Как это ни странно,
такой способ позволяет также получить выигрыш во времени, если
воспользоваться командами поразрядных логических операций над векторами
битов, имеющихся в системах команд почти всех ЭВМ и в некоторых
языках программирования высокого уровня. Если обозна-
обозначить через `р` исходную позицию, через `р_1, р_2, ..., р_8` —
позиции, сдвинутые
на одну клетку в направлении всех соседей клетки, и через `r` —
новую позицию, то каждый бит r будет однозначно определяться битами с тем
же номером в позициях `р, р_1, ..., p_8`, т. е. будет логической функцией от
них. Всякую логическую функцию можно, как известно, записать с
помощью элементарных логических операций: И, ИЛИ, исключающее ИЛИ и отрицание.
Задача состоит в том, чтобы выразить `r` через `р, p_1 ..., р_8` экономно,
с использованием возможно меньшего числа операций. Необходимое число
операций удается уменьшить до 29 (и это, вероятно, не предел), что при
размере машинного слова в 64 бита (над всеми битами слова логические
операции выполняются параллельно) составляет чуть менее половины
логической операции на обработку одной ячейки.

История колонии Жизнь зачаровывает, если ее просматривать как
фильм, но она будет еще увлекательней, если предстанет в цвете.
Каждой клетке при рождении может быть приписан некоторый
цвет, определяемый, возможно, ее поколением или генами,
переданными ей родителями. Циклические, но при этом движущиеся
колонии (а таких немало) великолепны в своем сверкающем
многоцветном наряде.

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Пояснения к курсовой работе

Игра "Жизнь"