Алгоритм, суть и реализация знаменитой игры «Жизнь» (симуляция жизни клеток) при помощи HTML5 canvas и чистого JS.

Игра «Жизнь» на HTML5 canvas - gozman.space

Игра «Жизнь» (Game of Life) впервые была разработана английским математиком Джоном Конвеем ещё в 1970 году. Суть игры заключается в симуляции жизни клеток, которые живут и рождаются по определённым, крайне простым правилам. 

Законы жизни клеток в виртуальной среде порождают целые организмы, поражающие воображение тем, что были созданы таким простым алгоритмом! Вот лишь парочка самых простых организмов, рождённых простейшим алгоритмом игры:

Пушка госпера

Пушка госпера

Эксплодер

Эксплодер

Игре уже много десятков лет, а люди всё находят новые и новые фигуры, создают целые вселенные из клеток, пишут многочисленные реализации на всевозможных языках программирования, в том числе и на эвристических (вроде Brainfuck).

Неужели лишь какие-то движущиеся клетки смогли приковывать внимание математиков и программистов на протяжении стольких лет? Давайте разберёмся!

Правила игры

Игра происходит пошагово. Каждый шаг (момент времени или кадр) решается какие клетки вымрут, а какие родятся.

Как уже можно было догадаться - клетки не вечны, это «жизнь». Следовательно от сюда и выходит главный параметр клетки:

Клетка может быть либо живой, либо мёртвой.

Вот и вся суть жизни клетки в этой игре, но эта жизнь подвержена 4 простым правилам, которые и будут определять жить ей или нет:

  1. Живая клетка, у который меньше двух живых соседних клеток умирает от одиночества.
  2. Живая клетка, у которой больше трех живых соседних клеток умирает из-за перенаселённости.
  3. Мёртвые клетки со строго тремя живыми соседними клетками становятся живыми, будто из-за размножения (оргия из 3х клеток).
  4. Во всех остальных случаях клетка сохраняет своё состояние в последующем поколении. 

Правила игры жизни

Вот и все правила игры!

 

Алгоритм действий

Постараюсь максимально последовательно представить простой алгоритм действий без привязанности к языку:

  1. Нарисовать клеточное поле
  2. Выделить два массива для клеток. Первый массив содержит статус клетки на текущее поколение, а второй на следующее. Так же можно в них для удобства хранить позицию клетки на поле, отталкиваясь от индексов элемента массива
  3. Заполнить первый массив случайными данными либо координатами определённой фигуры
  4. Пробежаться циклом по каждой клетке в первом массиве и посчитать её соседей
  5. В том же цикле на основании количества соседей и статуса клетки проверить, будет ли жить клетка в следующем поколении или вымрет? 
  6. Результат проверки записать во второй массив и вывести его на экран
  7. Скопировать второй массив в первый
  8. Вернутся к шагу 4 и повторить жизненный цикл снова. 

Игра считается оконченной, если все клетки вымерли, либо образовали устойчивые фигуры.

Вот и всё, постарайтесь реализовать это на любом языке программирования. Поверьте - это интересно! 

Готовый проект

Моя рабочая демка игры жизни

Проект на Git

 

Saturday, 05 November 2016