Игра Жизнь
В процессе обучения по специальности программная инженерия, меня интересовали различные интересные математические и прогнаммные задачки.
Одной из таких задачек заинтересовавших меня была математическая игра Жизнь
. Игра Жизнь
– клеточный автомат, придуманный
английским математиком Джоном Конвеем в 1970 году.
Происхдение
Джон Конвей заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом, который пытался создать
гипотетическую машину, которая может воспроизводить сама себя. Джону фон Нейману удалось создать математическую модель такой машины с
очень сложными правилами. Конвей попытался упростить идеи, предложенные Нейманом, и в конце концов ему удалось создать правила, которые
стали правилами игры «Жизнь». Впервые описание этой игры было опубликовано в октябрьском (1970 год) выпуске журнала Scientific American,
в рубрике Математические игры
Мартина Гарднера (Martin Gardner) [1].
Правила игры
Место действия этой игры – это размеченная на клетки поверхность или плоскость безграничная, ограниченная, или замкнутая.
Каждая клетка на этой поверхности может находиться в двух состояниях: быть живой
или быть мёртвой
. Клетка имеет восемь
соседей (окружающих клеток).
Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам [1]:
- в пустой клетке, рядом с которой ровно три живые клетки, зарождается жизнь;
- если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости»).
Эти простые правила приводят к огромному разнообразию форм, которые могут возникнуть в игре. Игрок не принимает прямого участия в игре, а лишь расставляет или генерирует начальную конфигурацию «живых» клеток, которые затем взаимодействуют согласно правилам уже без его участия и наблюдает за процессом игры.
Разнообразие фигур
Вскоре после представления общественности правил игры, было обнаружено несколько интересных вариантов расстановки живых клеток в первом поколении, которые приводили к бесконечным генерацием клеток или циклическое их повторение, в частности: r-пентамино и планер (glider). Пример таких образование показан на рисунке 1.
б)
Рисунок 1 – Шаблоны расстановки клеток: а) r-пентамино; б) планер
(анимация: 20 кадров, 10 циклов повторения, размер - 121x121, 24 килобайт)
Конвей первоначально предположил, что никакая начальная комбинация не может привести к неограниченному размножению и предложил премию в 50 долларов тому, кто докажет или опровергнет эту гипотезу. Приз был получен группой из Массачусетского технологического института, придумавшей неподвижную повторяющуюся фигуру, которая периодически создавала движущиеся «планеры». Таким образом, количество живых клеток могло расти неограниченно. Затем были найдены движущиеся фигуры, оставляющие за собой «мусор» из других фигур.
Компьютерная реализация
Для компьютерной реализации алгоритма игры была выбрана платформа .Net Framework и язык программирования С#. При реализации был использован объектно-ориентированный подход. Для реализации поведения клетки поверхности был написан следующий класс:
public partial class Cell
{
#region members
private bool isAlive; // состояние ячейки
private List Sosedi; // список соседей
private int countAliveSosedey; // количество соседей
private int _width; // ширина ячейки
private int _height; // высота
#endregion
#region property
public bool IsAlive
{
get { return isAlive; }
set{
if (isAlive == value)
{
IsChanged = false;
isAlive = value;
}
else
{
IsChanged = true;
isAlive = value;
}
}
}
public bool IsChanged { get; set; } // изменеие состоянния ячейки
public Point Location { get; set; } // координаты ячейки
#endregion
#region Constructors
public Cell()
{
Sosedi = new List| ();
}
public Cell(float colWid, float rowH):this()
{
IsChanged = true;
_width = (int)colWid;
_height = (int)rowH;
}
public Cell(int wCell, int hCell, Point point):this(wCell,hCell)
{
Location = point;
}
#endregion
internal void AddSosed(Cell cell)
{
Sosedi.Add(cell);
}
public void CaculateNextGeneration()
{
countAliveSosedey = this.GetAliveSosedey();
}
public void NextGeneration()
{
if (IsAlive)
{
if (countAliveSosedey < 2 || countAliveSosedey > 3)
{
IsAlive = false;
}
}
else
{
if (countAliveSosedey == 3)
{
IsAlive = true;
}
}
}
private int GetAliveSosedey()
{
int count = 0;
for (int i = 0; i < Sosedi.Count; i++)
{
if (Sosedi[i].IsAlive)
{
count++;
}
}
return count;
}
} | |
Данный класс хранит состояние клетки Жива
или Погибшая
. Так же данный класс включает в себя методы подсчета количества соседей и методы
реализующие логику изменения состояния клетки пространства.
Графика
Для отображения поля игры на котором будут отображатся процесс изменения состояния клеток пространства, используется библиотека OpenGL, так как данная открытая графическая библиотека позволяет работать с графикой не зависимо от платформы.
В современном мире, библиотеки OpenGL и DirectX являются конкурентами на платформе MS Windows. Microsoft всеми силами продвигает свою библиотеку DirectX, а также всеми силами стремится замедлить развитие библиотеки OpenGL, что ослабило бы графическую систему конкурирующих ОС, где для реализации вывода всей графики используется исключительно библиотека OpenGL [2].
Но, к сожалению, прямой поддержки данной библиотеки в .NET Framework нет, опять же по причинам конкуренции. Поэтому мы будем использовать библиотеку Tao Framework. Tao Framework – это свободно-распространяемая библиотека с открытым исходным кодом, предназначенная для быстрой и удобной разработки кросс-платформенного мультимедийного программного обеспечения в среде .NET Framewrok и Mono.На сегодняшний день Tao Framework - это лучший путь для использования библиотеки OpenGL при разработке в среде .NET на языке C# [2]. Данную библиотеку можно скачать по следующей ссылке.
После уставновки библиотеки, ее необходимо подключить к созданному в MS Visual Studio проекту "Приложение Windows Forms". Для этого в окне "Обозреватель решения" добавить в References боблиотеки Tao.OpenGL.dll, Tao.FreeGlut.dll, Tao.Platform.Windows.dll (см. рисунок 1).
Рисунок 1 – Добавления ссылки
В открывшемся окне менеджера ссылок необходимо добавить файлы библиотек. Для этого необходимо нажать кнопку "Обзор". В открывшемся окне из директории установки TaoFramework (C:\Program Files\TaoFramework\bin) необходимо выбрать следующие файлы показанные на рисунке 2.
Рисунок 2 – Добавления библиотек в менеджер ссылок
После добавления файлов в менеджер ссылок, необходимо отметить данные библиотеки и подтвердить выбор (см. рисунок 3).
Рисунок 3 – Подключение библиотек к проекту
Для работы с добавленными библиотеками необходимо подключить соответствующие пространства имен. Для этого в исходном коде главного окна необходимо написать следующий код:
using Tao.OpenGl; // для работы с библиотекой OpenGL
using Tao.FreeGlut; // для работы с библиотекой FreeGLUT
using Tao.Platform.Windows; // для работы с элементом управления SimpleOpenGLControl
Для отображения графики необходим контрол из добавленной библиотеки. Что бы добавить контроль необходимо на панели элементов нажать правой кнопкой мыши и из контекстного меню быть пункт "Выбрать элемент" (см. рисунок 4).
Рисунок 4 – Выбор меню добавления элмента
В открывшемся окне нужно выбрать элемент SimpleOpenGLControl (см. рисунок 5). После добавления контрола на панель элементов, его можно добавить на форму и задать ему имя "pane".
Рисунок 5 – Добавления контрола
После добавления контрола на форму, в конструкторе главной формы необходимо добавить инициализацию графического контекста данного контрола. Для этого необходимо дописать следующую строку кода:
public MainForm()
{
InitializeComponent();
pane.InitializeContexts();
}
После подключение графической библиотеки и инициализации контекста контрола, нужно проинициализировать OpenGl. Для этого нужно подписаться событие загрузки формы и написать следующий код:
private void MainForm_Load(object sender, EventArgs e)
{
Glut.glutInit(); // инициализация Glut
Glut.glutInitDisplayMode(Glut.GLUT_RGB | Glut.GLUT_DOUBLE | Glut.GLUT_DEPTH);
Gl.glClearColor(1.0f, 1.0f, 1.0f, 1); // очитка окна
Gl.glViewport(0, 0, pane.Width, pane.Height); // установка порта вывода в соотвествии с размерами элемента pane
Gl.glMatrixMode(Gl.GL_PROJECTION); // настройка проекции
Gl.glLoadIdentity();
Gl.glOrtho(-3, pane.Width, -1, pane.Height+2, -1, 1);
Gl.glMatrixMode(Gl.GL_MODELVIEW);
Gl.glLoadIdentity();
Gl.glEnable(Gl.GL_DEPTH_TEST);
}
Для отрисовки клеток игры используется следующая функция:
private void ShowPane()
{
Gl.glClear(Gl.GL_COLOR_BUFFER_BIT | Gl.GL_DEPTH_BUFFER_BIT);
int x, y;
Gl.glPushMatrix();
Gl.glColor3ub(0, 0, 0);
for (int i = 0; i < row; i++)
{
for (int j = 0; j < colom; j++)
{
if (cells[i][j].IsAlive)
{
Gl.glBegin(Gl.GL_POLYGON);
x = cells[i][j].Location.X;
y = cells[i][j].Location.Y;
Gl.glVertex2d(x, y);
Gl.glVertex2d(x, y + 10);
Gl.glVertex2d(x + 10, y + 10);
Gl.glVertex2d(x + 10, y);
Gl.glEnd();
}
}
}
Gl.glBegin(Gl.GL_LINES);
for (int i = 0; i < colom; i++)
{
Gl.glVertex3d(i*wCell, 0,1);
Gl.glVertex3d(i*wCell, pane.Height,1);
}
Gl.glVertex3d(colom*wCell, 0,1);
Gl.glVertex3d(colom*wCell, pane.Height,1);
for (int i = 0; i < row; i++)
{
Gl.glVertex3d(0, i*hCell,1);
Gl.glVertex3d(colom * wCell, i * hCell,1);
}
Gl.glVertex3d(0, row * hCell,1);
Gl.glVertex3d(colom * wCell, row * hCell,1);
Gl.glEnd();
Gl.glPopMatrix();
}
Пример отрисовки поля игры представлен на рисунке 6.
Рисунок 6 – Поле игры Жизнь
Инициализация данных и алгоритма игры
Для инициализации структур данных необходимых для алгоритма, необходимо добавить в конструктор формы следующий код:
CheckForIllegalCrossThreadCalls = false; // разрешение использовать контролы в разных потоках
threadSim = new Thread(SimulateLive); // создание потока алгоритма игры
colom = pane.Width / wCell; // количество столцов
row = hCell; // количество строк
// создание массива клеток
cells = new Cell[row][];
for (int i = 0; i < cells.Length; i++)
{
cells[i] = new Cell[colom];
}
// заполнение массива объектами класса Cell
for (int i = 0; i < row; i++)
{
for (int j = 0; j < colom; j++)
{
cells[i][j] = new Cell(wCell, hCell, new Point(j * wCell, i * hCell));
}
}
InitMass(); // инициализация массива клеток. определение соседей для клеток
Функция инициализации и определения соседей клеток выглядит следующим образом:
private void InitMass()
{
int str = cells.Length;
int stl = cells[0].Length;
for (int i = 1; i < str-1; i++)
{
//==========================================
//
// ***********
// * 1111111 *
// * 1111111 *
// * 1111111 *
// ***********
//
//==========================================
for (int j = 1; j < stl-1; j++)
{
cells[i][j].AddSosed(cells[i - 1][j - 1]);
cells[i][j].AddSosed(cells[i - 1][j]);
cells[i][j].AddSosed(cells[i - 1][j + 1]);
cells[i][j].AddSosed(cells[i][j - 1]);
cells[i][j].AddSosed(cells[i][j + 1]);
cells[i][j].AddSosed(cells[i + 1][j - 1]);
cells[i][j].AddSosed(cells[i + 1][j]);
cells[i][j].AddSosed(cells[i + 1][j + 1]);
}
//==========================================
//
// ***********
// 1*********1
// 1*********1
// 1*********1
// ***********
//
//==========================================
cells[i][0].AddSosed(cells[i - 1][stl-1]);
cells[i][0].AddSosed(cells[i - 1][0]);
cells[i][0].AddSosed(cells[i - 1][1]);
cells[i][0].AddSosed(cells[i][stl-1]);
cells[i][0].AddSosed(cells[i][1]);
cells[i][0].AddSosed(cells[i + 1][stl - 1]);
cells[i][0].AddSosed(cells[i + 1][0]);
cells[i][0].AddSosed(cells[i + 1][1]);
cells[i][stl - 1].AddSosed(cells[i - 1][stl - 2]);
cells[i][stl - 1].AddSosed(cells[i - 1][stl - 1]);
cells[i][stl - 1].AddSosed(cells[i - 1][0]);
cells[i][stl - 1].AddSosed(cells[i][stl - 2]);
cells[i][stl - 1].AddSosed(cells[i][0]);
cells[i][stl - 1].AddSosed(cells[i + 1][stl - 2]);
cells[i][stl - 1].AddSosed(cells[i + 1][stl - 1]);
cells[i][stl - 1].AddSosed(cells[i + 1][0]);
}
//==========================================
//
// *111111111*
// ***********
// ***********
// ***********
// *111111111*
//
//==========================================
for (int i = 1; i < stl-1; i++)
{
cells[0][i].AddSosed(cells[str-1][i-1]);
cells[0][i].AddSosed(cells[str-1][i]);
cells[0][i].AddSosed(cells[str-1][i+1]);
cells[0][i].AddSosed(cells[0][i-1]);
cells[0][i].AddSosed(cells[0][i+1]);
cells[0][i].AddSosed(cells[1][i-1]);
cells[0][i].AddSosed(cells[1][i]);
cells[0][i].AddSosed(cells[1][i+1]);
//=====================================
cells[str-1][i].AddSosed(cells[str - 2][i - 1]);
cells[str-1][i].AddSosed(cells[str - 2][i]);
cells[str-1][i].AddSosed(cells[str - 2][i + 1]);
cells[str-1][i].AddSosed(cells[str-1][i - 1]);
cells[str-1][i].AddSosed(cells[str-1][i + 1]);
cells[str-1][i].AddSosed(cells[0][i - 1]);
cells[str-1][i].AddSosed(cells[0][i]);
cells[str-1][i].AddSosed(cells[0][i + 1]);
}
//==========================================
//
// 1*********1
// ***********
// ***********
// ***********
// 1*********1
//
//==========================================
cells[0][0].AddSosed(cells[str - 1][stl - 1]);
cells[0][0].AddSosed(cells[str - 1][0]);
cells[0][0].AddSosed(cells[str - 1][1]);
cells[0][0].AddSosed(cells[0][stl - 1]);
cells[0][0].AddSosed(cells[0][1]);
cells[0][0].AddSosed(cells[1][stl - 1]);
cells[0][0].AddSosed(cells[1][0]);
cells[0][0].AddSosed(cells[1][1]);
cells[0][stl - 1].AddSosed(cells[str - 1][stl - 2]);
cells[0][stl - 1].AddSosed(cells[str - 1][stl - 1]);
cells[0][stl - 1].AddSosed(cells[str - 1][0]);
cells[0][stl - 1].AddSosed(cells[0][stl - 2]);
cells[0][stl - 1].AddSosed(cells[0][0]);
cells[0][stl - 1].AddSosed(cells[1][stl - 2]);
cells[0][stl - 1].AddSosed(cells[1][stl - 2]);
cells[0][stl - 1].AddSosed(cells[1][0]);
cells[str - 1][0].AddSosed(cells[str - 2][stl - 1]);
cells[str - 1][0].AddSosed(cells[str - 2][0]);
cells[str - 1][0].AddSosed(cells[str - 2][1]);
cells[str - 1][0].AddSosed(cells[str - 1][stl - 1]);
cells[str - 1][0].AddSosed(cells[str - 1][1]);
cells[str - 1][0].AddSosed(cells[0][stl - 1]);
cells[str - 1][0].AddSosed(cells[0][0]);
cells[str - 1][0].AddSosed(cells[0][1]);
cells[str - 1][stl - 1].AddSosed(cells[str - 2][stl - 2]);
cells[str - 1][stl - 1].AddSosed(cells[str - 2][stl - 1]);
cells[str - 1][stl - 1].AddSosed(cells[str - 2][0]);
cells[str - 1][stl - 1].AddSosed(cells[str - 1][stl - 2]);
cells[str - 1][stl - 1].AddSosed(cells[str - 1][0]);
cells[str - 1][stl - 1].AddSosed(cells[0][stl - 2]);
cells[str - 1][stl - 1].AddSosed(cells[0][stl - 1]);
cells[str - 1][stl - 1].AddSosed(cells[0][0]);
}
Работа основного алгоритма заключается в том чтобы просматривать массив клеток и вызывать функции CaculateNextGeneration и NextGeneration в которых реализована логика правил игры и после чего отрисовать клетки на форме. Функция имеет следующий вид:
private void SimulateLive()
{
while(true)
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < colom; j++)
{
cells[i][j].CaculateNextGeneration();
}
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < colom; j++)
{
cells[i][j].NextGeneration();
}
}
Thread.Sleep(100);
pane.Invoke(((Action)(() => { Render(); })));
}
}
После все вышесказанных манипуляций мы получил следующую программу, которая демонстрирует работы игры "Жизнь" (см. рисунок 7).
Рисунок 7 – Работа программы
(анимация: 21 кадров, 10 циклов повторения, размер - 412x481, 92 килобайт)
Загрузить данную программу можно по ссылке: скачать
Список использованных источников
- Жизнь (игра). [Электронный ресурс]. — Режим доступа: https://ru.wikipedia.org/wiki/Жизнь игра
- Уроки OpenGL + C#. [Электронный ресурс]. — Режим доступа: http://esate.ru/uroki/OpenGL/uroki-OpenGL-c-sharp/?rv1