GOLDE — это редактор и симулятор клеточных автоматов, который умеет проигрывать триллионы поколений «Жизни» Конвея мгновенно. Автор начал писать его восемь месяцев назад, не имея опыта в C++. Говорит, что боялся языка из-за репутации с «граблями» и segmentation fault, но решил разобраться. В итоге проект превратился в глубокое погружение в современный C++ и клеточные автоматы.
Главная техническая сложность — реализация алгоритма HashLife, придуманного Биллом Госпером. Он представляет вселенную «Жизни» в виде мемоизированного квадродерева, где каждый узел кэширует своё состояние на много поколений вперёд. Узлы каноничны: одинаковые подпаттерны никогда не вычисляются дважды. Узел размером 2^n × 2^n может посчитать себя на 2^(n-2) поколений вперёд — так, вселенная 2048 × 2048 прыгает на 512 поколений почти мгновенно.
Для хранения узлов используется собственный bump-pointer аллокатор LifeNodeArena — он выдаёт узлы непрерывными блоками, что даёт отличную кэш-локальность и стабильность указателей. Поскольку вся структура данных неизменяема (immutable), указатели можно смело делать const. Для поиска кэшированных узлов автор использует хеш-таблицу ankerl::unordered_dense.
Базовый случай — вселенная 8 × 8, которая кодируется четырьмя uint16_t. Поскольку для 4 × 4 есть всего 65 536 комбинаций, все они предпросчитываются при старте — тринадцатью табличными запросами и нулём ветвлений вычисляются два следующих поколения.
Отдельная проблема — поддержка ограниченных топологий, например, тора. HashLife не знает границ, поэтому GOLDE врёт алгоритму: перед шагом копирует живые клетки с одного края на противоположный, а после — «подчищает» призраков. Через абстрактный класс Topology можно добавлять любые поверхности — от сферы до бутылки Клейна.
Самая хитроумная часть — произвольный шаг. HashLife умеет прыгать только степенями двойки. Автор не нашёл решений в сети и написал холодное письмо Томасу Рокицки (одному из создателей Golly). Тот подсказал идею: GOLDE не ищет наибольшую степень двойки, которая делит n, а просто прыгает ближайшей меньшей степенью, вычитает и повторяет. Для 1000 поколений это 512+256+128+64+32+8 — шесть прыжков против 125 у Golly. Да, кэш прогревается хуже, зато любой шаг укладывается в log₂(n) итераций.
Процесс легко останавливается: через std::jthread и std::stop_token. Каждый рекурсивный вызов проверяет флаг остановки, а при закрытии редактора поток завершается безопасно. Для одновременного запуска нескольких симуляций используется статический массив из 256 кэшей (std::array) с thread_local индексом — это и эффективно, и позволяет шерить кэш между потоками в паузе.
В GOLDE ещё много чего: многопоточный цикл, отрисовка всей вселенной одним draw call через OpenGL-текстуру, GUI на ImGui с нормальной интеграцией в C++-модель владения. Исходники выложены на GitHub.