Разработка клеточного автомата. Часть 1.
Я написал много текста. Если вам лень читать, можете сразу перейти к главе "Разработка клеточного автомата".
Я очень люблю клеточные автоматы. Наблюдать за ними — настоящее удовольствие. Как правило, клеточные автоматы создаются с целью моделирования биологического поведения организмов.
Знакомство с клеточными автоматами
Game Of Life
Самый известный клеточный автомат написанный Джоном Конвеем в 1970 году.
Это первый клеточный автомат, с которым я познакомился. Его правила очень просты:
- Клетка может быть живой или мёртвой. Белый пиксель — живая клетка, чёрный — мёртвая.
- Если у живой клетки 2-3 соседа, она остаётся живой. Если соседей больше или меньше — умирает.
- Если у мёртвой клетки 3 живых соседа, она оживает.
Я делю клеточные автоматы на два типа:
- Дискретные: пространство разделено на фиксированные ячейки/пиксели, и сущности существуют только в этих ячейках.
- Непрерывные: сущности не привязаны к отдельным ячейкам и могут свободно перемещаться в пространстве.
Игра в Жизнь относится к дискретным автоматам, так как пространство разбито на пиксели. Хотя может казаться, что некоторые сущности двигаются, на самом деле их элементы умирают и рождаются заново. Например, планер:
Планер можно назвать сущностью второго порядка, так как он представляет собой устойчивую структуру, состоящую из нескольких клеток. Хотя кажется, что он движется по диагонали, его отдельные части не двигаются, а сменяют друг друга.
В Игре в Жизнь существует множество таких структур. Вот несколько примеров из Википедии.
Стабильные структуры остаются неизменными на протяжении всей симуляции.
Осцилляторы — это структуры, которые не перемещаются, но меняют свою форму через определённое количество шагов симуляции.
Космические корабли — это структуры, способные перемещаться по полю симуляции.
Важно отметить, что разработчик Игры в Жизнь не прописывал в коде этих сущностей. Они появляются естественным образом в результате базовых правил. Игра в Жизнь является полной по Тьюрингу, что означает возможность создания в ней полноценного компьютера.
Кто-то даже сумел создать симуляцию Игры в Жизнь внутри самой себя!
Симуляция Эволюции
Затем я узнал о канале foo52ru и обнаружил, что он создаёт множество интересных клеточных автоматов.
Я был вдохновлён его работой и создал свою собственную симуляцию на языке Java. Эта клеточная игра в тысячи раз сложнее, чем Игра В Жизнь.
Правила игры. Могу ошибаться в некоторых моментах:
- Пространство разделено на пиксели. Каждый пиксель может содержать одну сущность или оставаться пустым.
- Каждая живая сущность обладает генетическим кодом, который представляет собой набор чисел или генов произвольной длины. Каждое число или ген может иметь значение от 0 до 255. Каждое числовое значение гена кодирует определённое действие или свойство. Например, диапазон от 1 до 9 представляет собой команды перемещения, а от 15 до 30 — команды условий, такие как проверка наличия соседней клетки или проверка уровня энергии.
- Каждый шаг симуляции сущность выполняет действие текущего гена. На следующем шаге вступает в силу следующий ген в цепочке.
- Когда рождается новая клетка, она мутирует. Дочерняя клетка получает тот же набор генов, что и родительская, но с некоторыми случайными изменениями в цепочке.
В этой игре множество правил, но этот пост не об этом, поэтому я не буду описывать её подробно.
Lenia
Этот клеточный автомат даже трудно назвать клеточным, потому что клетки здесь не видны. Я классифицирую его как непрерывный.
Как и в Игре в Жизнь, здесь есть сущности. Например, глайдер.
Slime Mold
Slime Mold, или, как её ещё называют, Симуляция Слизня, — это клеточный автомат, который меня особенно заинтересовал.
В основе этого клеточного автомата лежат боты, оснащённые сенсорами, которые можно сравнить с глазами или носом. На каждом шагу симуляции бот проверяет, где находится больше всего «феромонов», и движется в этом направлении. При этом он также оставляет за собой след феромонов.
Вот пример одного такого бота. Он состоит из тела (большая сфера) и трёх сенсоров (мелкие сферы).
На экране может быть несколько тысяч или даже миллионов таких ботов. В этой симуляции мы видим только феромонный след, который они оставляют за собой.
Разработка клеточного автомата
Я сразу увидел потенциал игры Slime Mould и решил создать её клон. Для начала я полностью скопировал базовые правила: каждый бот должен был иметь три глаза и выпускать феромоны. Я быстро осознал, что эта симуляция отлично подходит для параллельной обработки, поэтому сразу начал писать код под графический процессор (GPU).
Вот какой результат я получил:
- Количество ботов: 100 тысяч.
- Скорость исчезновения феромонов: 2. (этот параметр отвечает за то, как быстро исчезает след от бота)
- Сила выпускания феромонов: 0.01
- Расстояние от бота до сенсоров: 10 пикселей.
- Угол сенсоров: 25 градусов.
- Скорость: 0.5 пикселя в секунду.
- Максимальная угловая скорость: 0.1 радиан в секунду или 5,73 градуса.
- Количество сенсоров: 3.
Это были глобальные параметры, их изменение приводило к различным результатам.
Например, вот интересная конфигурация:
- Сила выпускания феромонов: 0.007045008
- Расстояние от бота до сенсоров: 67.36086 пикселей.
- Угол сенсоров: 101.6259 градусов.
- Скорость: 0.8940543 пикселя в секунду.
- Максимальная угловая скорость: 0.01443696 радиан в секунду.
- Количество сенсоров: 4.
При такой конфигурации бот выглядел следующим образом:
Интересно, что все его сенсоры находились в задней части. На визуализации не отображается расстояние до сенсоров.
Я рандомизировал параметры, чтобы найти интересные конфигурации, но их оказалось не так много. Примерно через час я понял, что уже вижу очень похожие результаты.
Во второй части я расскажу о том, как я улучшал и добавлял новые функции в свой клон.