Генерация пещер при помощи клеточного автомата

Клеточный автомат — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний (например, 1 и 0).

Игра «Жизнь» (Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Это игра без игроков, в которой человек создаёт начальное состояние, а потом лишь наблюдает за её развитием.

Правила игры "Жизнь"

  • Место действия игры — размеченная на клетки плоскость, которая может быть безграничной, ограниченной или замкнутой.

  • Каждая клетка на этой поверхности имеет восемь соседей, окружающих её, и может находиться в двух состояниях: быть «живой» (заполненной) или «мёртвой» (пустой).

  • Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:

    • в пустой (мертвой) клетке, с которой соседствуют три живые клетки, зарождается жизнь

    • если у живой клетки есть два или три живых соседа, клетка продолжает свою жизнь, иначе умирает

Возможные регулируемые параметры

  1. Количество строк и столбцов для генерации

  2. Шанс на начальную инициализацию клетки (живая или мертвая)

  3. Пределы "рождения" и "выживания" (от 0 до 8)

  4. Количество поколений

Реализация генератора на С++

Для генерации нам нужно как то передавать настройки для генерации, для этого я создал структуру:

struct GenerationSettings final {
      value_type rows, cols, live_chance, generation_count;
      std::pair <value_type, value_type> live_limit, born_limit;
};
Что такое value_type?
  • value_type в данном случае это просто int

using value_type = int;

Лучшие правила для генерации пещеры

  1. Размеры не имеют значения

  2. Шанс на начальную инициализацию клетки должен быть выше 40%

  3. Пределы рождения от 5 до 8

  4. Пределы выживаемости от 4 до 8

  5. Обычно при таких настройках хватает от 20-40 поколений до стабилизации структуры

  6. Все клетки за пределами генерации считаются живыми

Первое поколение

  • В зависимости от шанса на начальную инициализации клетки мы должны решить какая клетка будет живой а какая мертвой

  • За шанс на начальную инициализацию отвечает переменная live_chance

Функция начальной инициализации
  • Принимает на вход размер пещеры и шанс начальной инициализации

  • Для генерации будет использовать средства из стандартной библиотеки <random> C++11

return_type InitializeRandom(value_type rows, value_type cols, value_type live_chance) {
    std::default_random_engine re(std::chrono::system_clock::now().time_since_epoch().count());
    std::uniform_int_distribution <value_type> dist(0, 100);

    // data_type -> std::vector<value_type>
    return_type::data_type generation(rows * cols);
    std::generate(generation.begin(), generation.end(), [&dist, &re, live_chance] {
        value_type chance = dist(re);
        return chance <= live_chance ? 1 : 0;
    });
    return {generation, rows, cols};
}
  • Клетку будем считать живой, если сгенерированное число меньше live_chance

  • Для генерирования (псевдо-)случайных чисел, движок будет инициализироваться seed'ом, зависящим от системного времени, используя для этого стандартную библиотеку <chrono>

Что такое return_type?
  • return_type в данном случае это просто обертка над одномерным массивом

  • DataWrapper знает размер матрицы, и позволяет доставать данные c одномерного массива в виде матрицы

template <> struct DataWrapper<kCave> final {
    using value_type = int;
    using data_type = std::vector<value_type>;

    data_type data;
    value_type rows = 0, cols = 0;

    int &operator()(std::size_t row, std::size_t col) {
        return data[row * cols + col];
    }

    int  operator()(std::size_t row, std::size_t col) const {
        if (row >= rows or col >= cols)
            return 1;
        return data[row * cols + col];
    }
}; 

Последующие поколения

  • Каждая клетка должна знать сколько у нее живых соседей

  • В зависимости от состояния клетки и количества соседей (с учетом генеративных настроек) будет принимать решение жить клетке или нет.

Функция подсчета живых соседей

Окре́стность Му́ра клетки (англ. Moore neighborhood) — в двумерном случае — совокупность восьми клеток на квадратном паркете, имеющих общую вершину с данной клеткой.

  • Функция принимает номер строки и столбца а также сам массив для проверки соседей

value_type CountLiveNeighbours(value_type row, value_type col, const return_type &cave) {
    value_type count = 0;
    for (auto item: {cave(row, col - 1), cave(row, col + 1), cave(row - 1, col), cave(row + 1, col),
                     cave(row - 1, col - 1), cave(row - 1, col + 1), cave(row + 1, col - 1),
                     cave(row + 1, col + 1)})
        if (item != 0)
            count++;
    return count;
}

Правила с учетом настроек генерации
  • Если текущая клетка жива и количество соседей находится в пределе live_limit, то клетка остается живой, иначе умирает.

std::pair<value_type, value_type> live_limit
  • Если текущая клетка мертва и количество соседей находится в пределе born_limit, то клетка оживает, иначе остается мертвой.

std::pair<value_type, value_type> born_limit
  • После определения состояния каждой клетки, из буфера, хранящего новое поколение, нужно скопировать с основной массив (для генерации последующих поколений)

Основная функция генерации

Посмотреть
return_type Generate(const GenerationSettings &s) {
    return_type cave{InitializeRandom(s.rows, s.cols, s.live_chance)}, tmp = cave;
    value_type generation = 0;
    while (generation++ != s.generation_count) {
        for (value_type row = 0; row != cave.rows; ++row) {
            for (value_type col = 0; col != cave.cols; ++col) {
                value_type count = CountLiveNeighbours(row, col, cave);
                if (cave(row, col) == 1 and (count < s.live_limit.first or count > s.live_limit.second))
                    tmp(row, col) = 0;
                else if (cave(row, col) == 0 and (count >= s.born_limit.first and count <= s.born_limit.second))
                    tmp(row, col) = 1;
            }
        }
        std::copy(tmp.data.begin(), tmp.data.end(), cave.data.begin());
    }
    return cave;
}

Сгенерированная пещера

  • количество строк 500

  • количество столбцов 500

  • шанс начальной инициализации 49

  • количество поколений 30

  • предел выживаемости [4-8]

  • предел рождаемости [5-8]

Комментарии (1)


  1. kreghek
    14.06.2023 03:13
    +2

    Крутой подход.

    Аналогично делал в своей хобби-пет--инди-игре.

    https://github.com/kreghek/Zilon_Roguelike/blob/master/Zilon.Core/Zilon.Core/MapGenerators/CellularAutomatonStyle/CellularAutomatonGenerator.cs

    Вдруг кому будет интересная реализация на шарпах.