Клеточные автоматы: как из шума получаются пещеры

Что такое клеточный автомат

Клеточный автомат — это сетка ячеек, где состояние каждой ячейки на следующем шаге зависит только от состояний её соседей на текущем. Правило простое и одно и то же для всей сетки, но при многократном применении к случайному полю оно рождает удивительно органичные формы — вспомните «Игру жизни» Конвея.

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

Где это используется в играх

• Генерация пещер и подземелий — классический приём в рогаликах: случайная сетка «стена / пол», сглаженная за несколько итераций.
• Карты островов и озёр — та же логика на карте высот даёт естественные береговые линии вместо ровных геометрических форм.
• Распространение эффектов — пожар, заражение или рост растительности на сетке тайлов часто моделируют теми же локальными правилами.

Как это работает изнутри

Самое популярное правило для пещер называют «4–5»: сначала сетка случайно заполняется стенами с вероятностью около 45%. Затем несколько раз подряд для каждой ячейки считают количество стен среди восьми соседей. Если соседних стен больше четырёх — ячейка тоже становится стеной, если меньше — полом. Так шум постепенно «остывает» до гладких пещерных стен.

// Генерация пещеры клеточным автоматом (правило 4–5)
function generateCave(width, height, fillChance, steps):
    grid = randomGrid(width, height, fillChance)  // true = стена

    repeat steps times:
        newGrid = copy(grid)

        for each cell (x, y) in grid:
            walls = countWallNeighbors(grid, x, y)

            if walls > 4:
                newGrid[x][y] = true   // становится стеной
            elif walls < 4:
                newGrid[x][y] = false  // становится полом
            // при walls == 4 клетка не меняется

        grid = newGrid

    return grid

Число итераций сильно влияет на результат: одна-две дают рваный, «шумный» ландшафт, четыре-пять — гладкие извилистые туннели, а слишком много превращает пещеру в одну большую пустую комнату. После сглаживания обычно отдельно проверяют связность — заливкой (flood fill) находят изолированные полости и либо соединяют их коридорами, либо отбрасывают.