Генерация пещер при помощи клеточного автомата
Клеточный автомат — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний (например, 1 и 0).
Игра «Жизнь» (Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Это игра без игроков, в которой человек создаёт начальное состояние, а потом лишь наблюдает за её развитием.
Правила игры «Жизнь»
-
Место действия игры — размеченная на клетки плоскость, которая может быть безграничной, ограниченной или замкнутой.
-
Каждая клетка на этой поверхности имеет восемь соседей, окружающих её, и может находиться в двух состояниях: быть «живой» (заполненной) или «мёртвой» (пустой).
-
Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:
-
в пустой (мертвой) клетке, с которой соседствуют три живые клетки, зарождается жизнь
-
если у живой клетки есть два или три живых соседа, клетка продолжает свою жизнь, иначе умирает
-
Возможные регулируемые параметры
-
Количество строк и столбцов для генерации
-
Шанс на начальную инициализацию клетки (живая или мертвая)
-
Пределы «рождения» и «выживания» (от 0 до 8)
-
Количество поколений
Реализация генератора на С++
Для генерации нам нужно как то передавать настройки для генерации, для этого я создал структуру:
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;Лучшие правила для генерации пещеры
-
Размеры не имеют значения
-
Шанс на начальную инициализацию клетки должен быть выше 40%
-
Пределы рождения от 5 до 8
-
Пределы выживаемости от 4 до 8
-
Обычно при таких настройках хватает от 20-40 поколений до стабилизации структуры
-
Все клетки за пределами генерации считаются живыми
Первое поколение
-
В зависимости от шанса на начальную инициализации клетки мы должны решить какая клетка будет живой а какая мертвой
-
За шанс на начальную инициализацию отвечает переменная 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]
ссылка на оригинал статьи https://habr.com/ru/articles/741564/
Добавить комментарий