Муравей Лэнгтона

Муравей, меняющий цвета клеток и после хаотичного движения строящий бесконечную магистраль.

  • Ant
  • Turn right
  • Turn left
100%

Tap to drop another ant, drag to paint tiles in its way; Rerun starts again from step 0 with the ants and tiles you added. One ant turns, flips the tile and steps, and after about 10,000 steps builds an ordered highway.

Setup
120 × 120 cells
Model
View
60 steps per second
40°

Как вам Муравей Лэнгтона?

О генераторе Муравей Лэнгтона

Автор и год
1986 год, Кристофер Лэнгтон
Базовый алгоритм
Поворот вправо на белом, влево на черном; смена цвета клетки; шаг вперед
Автострада
Формируется примерно через 10 000 шагов с циклом повторения в 104 шага
Встроенные пресеты
RL, RLR, LLRR и три многоцветных алгоритма
Частота обновления
До 400 шагов за один кадр отрисовки

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

Первые несколько сотен итераций муравей чертит простые симметричные узоры. Затем начинается продолжительный псевдослучайный хаос длительностью около 10 000 шагов, после чего система самоорганизуется и запускает «автостраду» — периодический диагональный след с циклом в 104 шага, уходящий в бесконечность. Каждая проверенная конфигурация пустого поля неизбежно приводит к автостраде, хотя строгого математического доказательства этому пока нет. Обобщенные версии используют строки правил с отдельной буквой для каждого цвета, формируя треугольники, симметричные орнаменты или сплошные блоки.

Симулятор запускает одного или нескольких агентов со скоростью до 400 шагов за один кадр. Выбирайте пресеты Classic highway (RL), Triangles (RLR), Symmetry (LLRR), Cardioid, Chaos или Filled, либо вводите собственные строки с командами R, L, U и N. Добавляйте муравьев кликом по экрану, рисуйте преграды у них на пути, подбирайте палитру и скачивайте результат в PNG.

Как пользоваться Муравей Лэнгтона

  1. Запустите муравья. Нажмите Play и наблюдайте за классическим правилом RL: от простых фигур через долгий хаос к диагональной трассе примерно на 10 000-м шаге.
  2. Увеличьте скорость. Поднимите значение Steps per frame до 400, чтобы быстро преодолеть хаотическую стадию и увидеть рождение автострады.
  3. Экспериментируйте с правилами. Переключайтесь между пресетами Triangles, Symmetry, Cardioid или задайте собственное правило буквами R (вправо), L (влево), U (разворот) и N (прямо).
  4. Меняйте окружение. Кликайте по сетке, чтобы подсаживать новых муравьев, или проводите линии курсором, создавая препятствия на их траектории.
  5. Сохраните результат. Настройте параметры Grid, Hue и Background, остановите анимацию и сохраните изображение в PNG.

Часто задаваемые вопросы

По каким правилам перемещается Муравей Лэнгтона?

Попав на белую клетку, муравей поворачивает на 90° вправо, а на черной — на 90° влево. Затем он инвертирует цвет клетки, на которой стоял, и перемещается на одну позицию вперед.

Что представляет собой «автострада» (highway)?

После приблизительно 10 000 шагов кажущегося хаоса классический муравей зацикливается на повторяющейся последовательности из 104 шагов. За каждый такой цикл он смещается на две клетки по диагонали, прокладывая ровную полосу.

Всегда ли возникает автострада?

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

Что означают буквы в составных формулах вроде RLR?

Каждая буква обозначает направление поворота на соответствующем цвете: цвета переключаются циклически при каждом посещении клетки. Обозначение RL задает классическую двухцветную систему, а более длинные цепочки вводят дополнительные цвета и команды: U (разворот на 180°) и N (шаг без поворота).

Руководства и статьи

Научные источники

  1. Langton, C. G. (1986). Studying artificial life with cellular automata. Physica D 22(1–3), 120–149.