Порядок из хаоса. Напишем клеточный автомат «Муравей Лэнгтона» на p5py в браузере и анимируем с помощью state machine

Тридцать восемь лет назад в свои тридцать восемь лет аспирант Мичиганского университета Крис Лэнгтон придумал два простых правила для клеточного автомата. Мы быстро повторим правила Лэнгтона, оживим муравья, написав код онлайн, добавим динамики (плавная анимация) и интерактивности (редактор уровней). Повоюем, постреляем купидоновыми стрелами, порисуем на заборе. А ещё педагогически немного адаптируем код для занятий с детьми (опционально).

Продолжим экспериментировать с клеточными автоматами прямо в браузере (или в VS Code), используя Python + p5py, чтобы вы могли быстро опробовать свои идеи.

В глубокой задумчивости и с лёгким удивлением муравей взирает на суету мира

• Часть первая. Муравей Лэнгтона

• Часть вторая. Анимация. Вот, плавный поворот

• Часть третья. Редактор уровней

Часть первая. Муравей Лэнгтона

Представим, что у нас есть тетрадь в клетку и карандаш, символизирующий муравья. Следуя простым правилам мы будем или закрашивать или стирать квадратики:

На белом квадрате поворачиваем на 90° по часовой стрелке, меняем цвет квадрата, перемещаемся на один шаг вперёд.
На чёрном квадрате поворачиваем на 90° против часовой стрелки, меняем цвет квадрата, перемещаемся на один шаг вперёд.

Можно чуть короче сформулировать:

Чёрная? Нале-во!
Белая? Напра-во!
Инвертируем цвет клетки.
Шаг вперёд.

То есть, у муравья есть координаты и направление. Давайте напишем код, с которым поэкспериментируем. На p5py нарисовать муравья в виде круга крайне просто:

from p5py import *
run()

size(400, 400)
background("white")
fill("red")
ellipse(200, 200, 25, 25)

Запустить

Но нам нужна динамика, а значит — куча переменных. Приступим...

Личинка

Сначала сделаем просто неподвижного муравья:

from p5py import *
run()

size(display_width, display_height)

# Определяем размеры сетки и начальное направление муравья
grid_size = 25
cols = width // grid_size
rows = height // grid_size
grid = [[0 for _ in range(cols)] for _ in range(rows)]
ant_x, ant_y = cols // 2, rows // 2
direction = 0  # 0 - вверх, 1 - вправо, 2 - вниз, 3 - влево

def draw():
    draw_grid()
    render_ant()

def draw_grid():
    for y in range(rows):
        for x in range(cols):
            fill(255) if grid[y][x] == 0 else fill(0)
            rect(x * grid_size, y * grid_size, grid_size, grid_size)

def render_ant():
    fill(255, 0, 0)  # цвет муравья
    ellipse(ant_x * grid_size + grid_size / 2, ant_y * grid_size + grid_size / 2, grid_size / 2, grid_size / 2)

Меняем состояние клетки, где находится муравей:

if grid[ant_y][ant_x] == 0:  # белая клетка
    grid[ant_y][ant_x] = 1    # меняем на черную
    direction = (direction + 1) % 4  # поворот направо
else:  # черная клетка
    grid[ant_y][ant_x] = 0    # меняем на белую
    direction = (direction - 1) % 4  # поворот налево

Двигаем муравья, учитывая направление:

if direction == 0:  # вверх
    ant_y = (ant_y - 1) % rows
elif direction == 1:  # вправо
    ant_x = (ant_x + 1) % cols
elif direction == 2:  # вниз
    ant_y = (ant_y + 1) % rows
elif direction == 3:  # влево
    ant_x = (ant_x - 1) % cols

Вуаля: бежит, суетится:

Запустить муравья

Длинный нос

Можем ему добавить «носик» в виде линии, чтобы было видно, куда он смотрит:

line(x, y, x1, y1)

Или полностью:

def render_ant():
    fill(255, 0, 0)
    ellipse(ant_x * grid_size + grid_size / 2, ant_y * grid_size + grid_size / 2, grid_size / 2, grid_size / 2)
    x = ant_x * grid_size + grid_size / 2
    y = ant_y * grid_size + grid_size / 2
    x1 = x - grid_size if direction == 3 else x + grid_size if direction == 1 else x
    y1 = y - grid_size if direction == 0 else y + grid_size if direction == 2 else y
    line(x, y, x1, y1)

Заодно мы его замедлили с помощью frame_rate(1).

Оживить муравья

Часть вторая. Вот, плавный поворот

Кстати, Муравей Лэнгтона — хорошее и забавное упражнение на пространственное мышление для детей.

Мы с дочкой обожаем вместе изучать подобные задачки, сначала на бумаге, потом смотрим, как всё можно ускорить на компьютере. Но такие быстрые скачки муравья не очень наглядны. Попробуем всё замедлить. Вдруг вы тоже захотите со своими детьми поисследовать тему. Также наш код будет подъёмен для тех детей, которые занимались по книжке Python+p5py.

Давайте добавим state machine для муравья. Одно состояние — он выбирает, куда ему повернуться. Второе — поворачивает плавно-плавно в течение 30 кадров. Третье — делает шаг после того, как закончил поворачиваться. Четвёртое — возвращается в исходное состояние (или, если сделаете, будет медленно перекрашивать ячейку).

# Состояния
STATE_TURN_CHOOSE = 0
STATE_TURNING = 1
STATE_STEPPING = 2
STATE_INVERTING = 3

Текущее состояние:

state = STATE_TURN_CHOOSE
turn_frames = 0

И напишем саму обработку состояний. В первом из них муравей определяется с направлением и инвертирует цвет ячейки:

if state == STATE_TURN_CHOOSE:
    if grid[ant_y][ant_x] == 0:
        grid[ant_y][ant_x] = 1
        direction = (direction + 1) % 4
    else:
        grid[ant_y][ant_x] = 0
        direction = (direction - 1) % 4
    state = STATE_TURNING
    turn_frames = 0

Во втором будет медленно поворачиваться (30 кадров):

elif state == STATE_TURNING:
    turn_frames += 1
    if turn_frames >= 30:
        state = STATE_STEPPING

В третьем он сделает шаг вперёд:

elif state == STATE_STEPPING:
    if direction == 0:
        ant_y = (ant_y - 1) % rows
    elif direction == 1:
        ant_x = (ant_x + 1) % cols
    elif direction == 2:
        ant_y = (ant_y + 1) % rows
    elif direction == 3:
        ant_x = (ant_x - 1) % cols
    state = STATE_INVERTING
    turn_frames = 0

В последнем вернётся к началу:

elif state == STATE_INVERTING:
    turn_frames += 1
    if turn_frames >= 30:
        state = STATE_TURN_CHOOSE  

Понятно, что можно улучшить код, например, вынести всё в функции, для наглядности, вынести «магические числа» в константы, не отрисовывать поле в лоб и т. п. Но пока оставим так.

Визуально ещё ничего не поменялось, но мы заложили фундамент:

Код со state machine

Хвост по ветру

Но муравей поворачивает всё ещё дёргано. Нужно сделать так, чтобы нос поворачивался плавно, а не дискретно. Добавим текущий угол «носа» у муравья. И будем инкрементировать его в elif state == STATE_TURNING:. Для начала добавим переменные для отслеживания угла:

angle_step = 1
agle_goal = angle + PI / 2

И перепишем состояние поворота, например, так:

elif state == STATE_TURNING:
    turn_frames += 1
    angle += angle_step 
    if turn_frames >= 90:
        state = STATE_STEPPING

Вот медленно вращается

Плавнее шаг!

А ещё сделаем так, чтобы муравей шагал тоже плавно. Для наглядности вынесем в функции отдельные состояния:

if state == STATE_TURN_CHOOSE:
    choose_direction()

elif state == STATE_TURNING:
    turning()

elif state == STATE_STEPPING:
    stepping()

elif state == STATE_INVERTING:
    inverting()

Теперь код намного легче читается.

И напишем функцию плавного шага:

def stepping():
    global ant_x, ant_y, state, turn_frames, prev_ant_x, prev_ant_y, x, y
    move_ant()
    turn_frames += 1
    if turn_frames >= grid_size:
        prev_ant_x, prev_ant_y = ant_x, ant_y
        update_ant_grid_position()
        turn_frames = 0
        state = STATE_INVERTING

Здесь вынесли в отдельные вспомогательные функции обновление координат:

def update_ant_grid_position():
    global ant_x, ant_y
    if direction == 0:
        ant_y = (ant_y - 1) % rows
    elif direction == 1:
        ant_x = (ant_x + 1) % cols
    elif direction == 2:
        ant_y = (ant_y + 1) % rows
    elif direction == 3:
        ant_x = (ant_x - 1) % cols

def update_ant_render_position():
    global x, y
    x = ant_x * grid_size + grid_size / 2
    y = ant_y * grid_size + grid_size / 2

Да не мельтеши ты!

Короче, во время тестирования я обнаружил, что такое мерцание муравья сбивает с толку. Только ребёнок начал думать, какой цвет соответствует какому повороту, а цвет — раз! — и уже поменялся.

Поэтому для удобства будем инвертировать цвет ячейки не до перемещения, а после. Так цвет ячейки дольше остаётся неизменным и мы дольше можем фоново сверить, правильно ли муравей повернул. Если же менять цвет до перемещения, то он слишком быстро инвертируется и путает. Как только закончили делать шаг вперёд, выполняем функцию инвертирования. Но только не с текущими координатами, а с предварительно сохранёнными:

def inverting():
    global state, turn_frames
    turn_frames += 1
    if turn_frames >= TURN_FRAMES_MAX:
        grid[prev_ant_y][prev_ant_x] = 1 - grid[prev_ant_y][prev_ant_x]
        turn_frames = 0
        state = STATE_TURN_CHOOSE

А предварительно сохраним их здесь:

def stepping():
    global ant_x, ant_y, state, turn_frames, prev_ant_x, prev_ant_y, x, y
    move_ant()
    turn_frames += 1
    if turn_frames >= grid_size:
        prev_ant_x, prev_ant_y = ant_x, ant_y
        update_ant_grid_position()
        turn_frames = 0
        state = STATE_INVERTING

Получилось значительно лучше. Теперь ребёнок видит белый цвет клетки, озвучивает, что муравей поворачивает направо, смотрит, что муравей и правда повернул направо и сделал шаг вперёд. И только потом оставшийся позади квадратик поменял свой цвет на противоположный:

Код финальный

Подать эмодзи нашему алгоритму

А если захотите с детьми поиграть, можно заменить круг на эмодзи муравья. Но с эмодзи какая проблема? Нет гарантии, что на разных системах они хоть примерно одинаково нарисованы. Поэтому, возможно, вам придётся подправить код. Благо, это быстро и не сложно. Если что-то сломается — пишите в комментах.

Здесь используем специальные команды p5py (p5.js, Processing) для работы с матрицами, так проще реализовать повороты:

def render_ant():
    global angle, x, y
    fill(255, 0, 0)
    push()  # Сохраняем текущие трансформации
    translate(x, y)  # Перемещаем координаты в центр муравья
    rotate(PI + radians(angle))  # Поворачиваем вокруг центра
    text_align(CENTER)
    text_size(grid_size * 2 / 3)  # Устанавливаем размер текста равным размеру клетки
    text("🐜", 0, grid_size / 4)  # Смещаем координаты для центрирования
    pop()  # Восстанавливаем предыдущие трансформации

Вот в этой строчке rotate(PI + radians(angle)) вам может понадобиться заменить PI на что-то другое, чтобы соответствовало выбранной «картинке».

Муравей в виде эмодзи

Эмерджентное поведение

Самое увлекательное в Муравье Лэнгтона — это самовозникающий из хаоса порядок.

Муравей движется псевдо-хаотически и в какой-то момент начинает повторять одну и ту же структуру «бесконечно», видимо, пытаясь убежать от экспериментатора.

Ускоряемся. Как сбежать быстрее

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

def draw():
    global ant_x, ant_y, direction

    for i in range(0, 50):
        # Меняем состояние клетки, где находится муравей
        if grid[ant_y][ant_x] == 0:  # белая клетка
            grid[ant_y][ant_x] = 1    # меняем на черную
            direction = (direction + 1) % 4  # поворот направо
        else:  # черная клетка
            grid[ant_y][ant_x] = 0    # меняем на белую
            direction = (direction - 1) % 4  # поворот налево
        
        # Двигаем муравья по направлению
        if direction == 0:  # вверх
            ant_y = (ant_y - 1) % rows
        elif direction == 1:  # вправо
            ant_x = (ant_x + 1) % cols
        elif direction == 2:  # вниз
            ant_y = (ant_y + 1) % rows
        elif direction == 3:  # влево
            ant_x = (ant_x - 1) % cols

    draw_grid()
    render_ant()

Вот что нас ускорит в условные 50 раз:

for i in range(0, 50):

Но там всё ещё остаётся перерисовка всего поля, что явно лишнее в этом алгоритме. В дальнейшем избавимся от этих действий.

Ускоренный в 50 раз код

Часть третья. Редактор уровней

Давайте добавим муравью мини-редактор уровней, чтобы при клике мышкой цвет ячейки инвертировался.

def mouse_clicked():
    # Получаем координаты клетки под курсором мыши
    cell_x = mouse_x // grid_size
    cell_y = mouse_y // grid_size

    # Проверяем, что координаты находятся в пределах сетки
    if 0 <= cell_x < cols and 0 <= cell_y < rows:
        # Инвертируем цвет клетки
        grid[cell_y][cell_x] = 1 - grid[cell_y][cell_x]

Нарисовав клетку вокруг муравья, можно заметить интересный паттерн: муравей переносит линию на один пиксель в сторону.

Редактор уровня у нас пока не особо-то и удобный. Он крайне примитивный: просто рисует точку при клике, и даже не оставляет следа, если продолжать двигать мышкой. Позже исправим.

Мини-редактор

Ещё ускоряемся

Давайте добавим на экран кнопку, чтобы при клике на неё скорость SPEED муравья переключалась с 1 на 50. Чтобы можно было временно ускорять рендеринг.

button_x, button_y, button_width, button_height = 650, 550, 100, 40  # Параметры кнопки

def draw_button():
    fill(180)
    rect(button_x, button_y, button_width, button_height)
    fill(0)
    text("Toggle Speed", button_x + 10, button_y + 25)

Классический серый цвет. Но можно выбрать и что-то более современное.

Заодно уберём переключение цвета и оставим только рисование чёрным:

def mouse_clicked():
    global speed  

    # Получаем координаты клетки под курсором мыши
    cell_x = mouse_x // grid_size
    cell_y = mouse_y // grid_size

    # Проверяем, что координаты находятся в пределах сетки
    if 0 <= cell_x < cols and 0 <= cell_y < rows:
        # Инвертируем цвет клетки
        grid[cell_y][cell_x] = 1# - grid[cell_y][cell_x]
    
    # Проверяем, нажата ли кнопка
    if button_x <= mouse_x <= button_x + button_width and button_y <= mouse_y <= button_y + button_height:
        speed = 50 if speed == 1 else 1  # Переключаем скорость

Ещё чуть улучшили, чтобы след оставался относительно непрерывно, если двигать мышкой с нажатой кнопкой.

Готовый код с ускорением

Теперь можно экспериментировать со своими рисунками и ловить магистрали:

Наблюдать блуждающих по линии муравьёв:

Поймать шпалоукладчика:

На длинной линии его ещё лучше видно:

И вечные магистрали:

Ну и несложно сделать паузу, чтобы нарисовать стартовый рисунок:

speed = 50 if speed == 0 else 0

Код мы позже переделаем. Для быстрого тестирования пойдёт, но интерфейс при таком решении не отзывчивый.

Пытаемся удержать муравья в клетке:

Fail.

А вот при таких стартовых условиях размера холста не хватило — не успел построить магистраль. Остался пленником.

Побег из Шоушенка. Можно добавить счётчик кадров и соревноваться, кто дольше удержит муравья или кто ему лучше поможет.

Катализатор магистрали

Легко обнаружить, что стартовые три точки справа от муравья дают шанс быстро найти магистраль:

Можно даже захардкодить, чтобы было легче повторить:

grid[ant_y][ant_x + 3] = 1
grid[ant_y][ant_x + 4] = 1
grid[ant_y][ant_x + 5] = 1

Ну, в целом, это уже на пятна Роршаха смахивает.

Не сложно обнаружить, что третья точка — лишняя. Да и вообще одной точки сверху достаточно. Она играет роль катализатора магистрали.

grid[ant_y - 2][ant_x] = 1

Код с быстрой магистралью

А ещё это похоже на выстрелы и взрывы

Запустим генерацию и нажмём паузу, когда муравей начнёт прокладывать магистраль. Нарисуем препятствие на его пути и возобновим движение муравья; он теперь не муравей, а снаряд какой-то. Ударяется в препятствие и натурально «взрывается».

Хе, нарисуем в «редакторе» НЛО и танчики:

Предсказуемый результат:

А в анимации выглядит прямо как настоящий взрыв:

Пришло время причесаться

Здесь мы наконец-то немного причесали код. В mouse_clicked() оставили только смену скорости:

def mouse_clicked():
    global speed  
    if button_x <= mouse_x <= button_x + button_width and button_y <= mouse_y <= button_y + button_height:
        speed = 50 if speed == 0 else 0

А возможность рисовать мышкой вынесли в draw():

if mouse_is_pressed:
    cell_x = mouse_x // grid_size
    cell_y = mouse_y // grid_size
    if 0 <= cell_x < cols and 0 <= cell_y < rows:
        grid[cell_y][cell_x] = 1# - grid[cell_y][cell_x]
        draw_grid(cell_x, cell_y)

Теперь можно рисовать и более сложные рисунки. Поиграть в стрелялки: Финальная версия редактора.

Чайник, просто чайник:

Стрелы Купидона

Нарисуем сердечко:

А это уже не одна стрела, а целая куча:

Итак

• Мы реализовали базовый алгоритм Муравья Лэнгтона.

• Добавили к нему плавную анимацию, чтобы даже ребёнку было понятно, как всё работает. Для этого вспомнили паттерн State Machine.

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

• Обнаружили на практике эмерджентное поведение: когда из хаоса внезапно возникает порядок.

• Добавили кнопку ускорения рендеринга, теперь можем быстро «заглядывать в будущее» муравья.

• Нарисовали забавные картинки и понаблюдали, как муравей в них живёт: войнушки, сердечки.

Если вам понравилось быстро тестировать гипотезы в браузере, вот ещё статьи про p5py:

• 📖 Как я написал книгу для детей: «Мама, не отвлекай. Я Python учу!»

• Давайте-ка наваяем PumpKeen Game. Как Commander Keen, только про Pumpkin (тыкву). Хэллоуин же

• Хотите, покажу вам магию живого кода на p5py? (Про Игру Жизнь)

• Самая простая модель естественного отбора (в браузере на p5py).

Модуль p5py в бета-версии, узнать новости, обсудить ошибки, идеи и свои работы можно в общей группе в Телеграм: @p5py_ru