На втором курсе я впервые встретил так называемую игру "Жизнь", которую я тогда воспринимал как занятный способ генерации любопытных картинок. Годы шли, и я узнал, что, во-первых, игра была придумана не в 80-е любителями графического программирования, а в 1970 году математиком Джоном Конвеем для исследования машин, которые умеют строить собственные копии, и, во-вторых, есть целый класс таких "игр", называемых клеточными автоматами, которые широко используются в математическом моделировании самых разных процессов.
Совсем недавно я узнал, что помимо вышеперечисленного, у клеточных автоматов есть еще одно применение: с их помощью можно копать. Вернее, с их помощью можно генерировать разнообразный ландшафт — в том числе, пещер.
Исходной точкой здсь по-прежнему служит "Жизнь". Статья на википедии хорошо описывает, что это такое, так что не буду перессказываьт правила. Идея состоит в следующем: взять поле клеток, случайно разбросать начальное распределение живых и мертвых клеток, а потом провести несколько итераций клеточного автомата. Параметрами такого автомата будут порог смерти (минимальное число соседей, необходимое для поддержания жизни в клетке), порог рождаемости (минимальное число клеток, необходимое для рождения новой клетки), и вероятность оказаться живой в начальном распредлении. На следующих картинках живые клетки будут черными, мертвые — жёлтыми.
Оказывается, такие автоматы умеют неплохо генерировать пещеры. Вот, например, начальное распределение и первые семь итераций автомата (3,4,0.4):
Начальное распределение, как видно, представляет собой обычный белый шум, однако уже первая итерация заметно "упорядочивает" его. На третьей-четвертой итерации процесс стабилизируется, и каждая новая итерация выдаёт новую случайную "пещеру". Я просмотрел 100-200 итераций — каждая даёт новую пещеру.
Изменение вероятности начального выживания делает всю пещеру более или менее просторной. Вот примеры того же автомата для вероятностей 0.35, 0.4. 0.47:
Задание разных порогов рождаемости и смерти позволяет получать качественно другие пещеры. Вот, например, седьмая итерация автомата (2,4) для вероятностей 0.3, 0.35, 0.4 и 0.42:
Автомат (3,6) даёт несколько более "рваные" пещеры (вероятности 0.48, 0.50, 0.52, 0.60):
Автомат (5,6) даёт существенно другую картину с гораздо большими "островами" (вероятности 0.7, 0.75, 0.77, 0.80):
По всей видимости, для любого автомата можно указать интервал начальных вероятностей (обычно длинной в 0.1), для которых последовательность порождает интересные (не слишком пустые и не слишком заполненные) пещеры.
По слухам, этот метод используется для генерирования пещер в рогаликах и не только.