Сегодня хочу рассказать про штуку под названием КЛЕТОЧНЫЙ АВТОМАТ (англ. cellular automata / automation).

Это алгоритм / механизм для симуляции «рождения» и «смерти» клеток в матрице. Изначально придуман Джоном Конвеем в 1970 для «Игры в жизнь» (Game of Life), смысл которой в том, чтобы задать популяцию «живых» клеток и наблюдать за тем, как она меняется со временем (а если загуглить «game of life», гугл выдаст симуляцию этой игры на странице поиска).

Кстати! Не бойтесь слова «матрица». В данном случае оно лишь означает клеточное 2D поле, в котором хранятся нули и единицы. Как лист бумаги для морского боя.


В игру Конвея можно поиграть здесь. Правила следующие:

— Есть изначальная матрица клеток, часть из которых «живые» (1) или «мертвые» (0). Можно задать ее случайно, можно использовать готовый паттерн (их целая куча — глайдеры, статичные фигуры, пушки и т.д.).

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

— Каждый новый «шаг» симуляции определяет, какие клетки будут «мертвыми» или «живыми». За это отвечают две величины — порог рождения (birth limit) — то, сколько «живых» соседей (минимум) должно быть у «мертвой» клетки, чтобы она «ожила», и порог смерти (death limit) — то, сколько «живых» соседей (минимум) должно быть у «живой» клетки, чтобы она не «умерла».

Пример: у «мертвой» клетки 4 «живых» соседа. Порог рождения — 3. Значит, на следующем шаге она станет «живой».

— Соседи — это ближайшие 8 клеток (иногда для крайних клеток учитывают соседей с другой стороны экрана). Таким образом, пороги рождения и смерти, а также формация клеток, определяют, как быстро популяция будет расти или умирать.


А зачем вообще нужен клеточный автомат?

Как минимум, он способен предсказывать развитие реальных популяций. А в программировании его можно использовать для… *барабанная дробь*

Генерации пещер. Да, серьезно.

Представьте, что у вас есть игра по типу Minecraft, в которой случайным образом нужно создавать пещеры (не говорю, что в реальном Minecraft это так работает, там все гораздо сложнее). Если правильно сбалансировать birth limit, death limit и шанс инициализации, то за 20-30 шагов симуляции на случайно созданном поле можно получить большое пространство из «мертвых» клеток — то есть, пещеру.

В этой статье как раз хорошо объяснено.

Год назад я в команде создавал свою версию Game of Life на языке Си. Сейчас делаю приложение, где есть генерация пещер с помощью клеточного автомата, так что этот алгоритм мне уже как родной :)

#Algorithms