Организация ассоциативной среды для реализации алгоритма «Игра в жизнь»

Широко известны различные реализации алгоритма «Игры в жизнь», который позволяет решать различные нечисловые задачи. По своей структуре, игра «Игра в жизнь» представляет некую клеточную матрицу, которая может быть двух и более размерностей.

 Ассоциативная среда [1, с. 27] использующаяся для реализации различных методов эффективности не числовой обработки данных и организации управления. По своей структуре ассоциативные среды могут быть многокоординатными и способными реализовывать алгоритмы одновременной обработки всей хранимой в ассоциативной среде информации. По своим потенциальным возможностям ассоциативная среда может использоваться для алгоритмов, используемых в «Игре в жизнь».

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

В данной статье предлагается такая ассоциативная среда.

Особенностью ее является многоуровневая организация, которая основана на представлении ассоциативных ячеек, образующих общий уровень, как состоящих из ассоциативных элементов, образующих свой уровень [2, с. 72].

Ассоциативные ячейки образуют матрицу ассоциативных ячеек (см. рисунок 1).

Рисунок 1 – Ассоциативная матрица.

Ячейки ассоциативной среды соответствуют отдельным клеткам поля, реализующим алгоритм «Игра в жизнь».

Правила функционирования этого поля:

• Каждая клетка (ассоциативная ячейка) на этом поле может находиться в двух состояниях: быть «живой» или быть «мёртвой» (пустой).

• Клетка имеет восемь соседей.

• Распределение живых клеток в начале игры называется первым поколением.

• Каждое следующее поколение рассчитывается на основе предыдущего по следующим правилам:

  • Правило рождения – если в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;

  • Правило выживание - если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить;

  • Правило гибели -  в противном случае (если соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости»)

  • Игра прекращается, если на поле не останется ни одной «живой» клетки, если при очередном шаге ни одна из клеток не меняет своего состояния

На рисунке 2 приведен пример реализации ассоциативной ячейки, на основе ассоциативных элементов. 

Рисунок 2 - Ассоциативная ячейка (клетка), состоящая из 13 ассоциативных элементов для «Игры в жизнь»

Ассоциативная ячейка представляет группу из 13 ассоциативных элементов следующих видов:

• из восьми элементов взаимодействия (ЭВЗ);

• из четырех логических элементов (ЛЭ);

• одного элемента памяти (ЭП).

Разработанные для реализации ассоциативные ячейки могут быть организованы в двухмерную и трехмерную структуру. В трехмерной структуре ассоциативная ячейка выглядит как на рисунке 3.

Рисунок 3 - Ассоциативная ячейка, состоящая из 13 ассоциативных элементов «Игры в жизнь». Многомерное представление.

Трехмерная структура ячейки составляет многомерную ассоциативную среду, что позволяет организовать:

• иерархическую организацию ассоциативной среды;

• однородную структуру;

• возможность многокоординатного доступа к ячейкам.

Общий (плоский) вид этой среды представлен на рисунке 4. 

Рисунок 4 - Пример организации ассоциативного поля в «Игре в жизнь»

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

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

Литература

1. Огнев И. В., Борисов В. В. «Ассоциативные среды». - Радио и связь, Москва 2000г. -312 стр.

2. Полячков А. В. «Сетевые контроллеры на основе ассоциативной среды с совмещением функций управления, хранения и обработки информации».  Диссертация на соискание учёной степени кандидата технических наук по специальности «Элементы и устройства вычислительной техники и систем управления». – Москва «МЭИ» 2003г. – 149 стр.