Генерация пещер при помощи клеточного автомата
Клеточный автомат — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний (например, 1 и 0).
Игра «Жизнь» (Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Это игра без игроков, в которой человек создаёт начальное состояние, а потом лишь наблюдает за её развитием.
Всем привет! Меня зовут Нурислам (aka tonitaga), я участник School21 и сегодня я бы вам хотел рассказать о Генерации Пещер.
Правила игры "Жизнь"
Место действия игры — размеченная на клетки плоскость, которая может быть безграничной, ограниченной или замкнутой.
Каждая клетка на этой поверхности имеет восемь соседей, окружающих её, и может находиться в двух состояниях: быть «живой» (заполненной) или «мёртвой» (пустой).
Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:
в пустой (мертвой) клетке, с которой соседствуют три живые клетки, зарождается жизнь
если у живой клетки есть два или три живых соседа, клетка продолжает свою жизнь, иначе умирает
Возможные регулируемые параметры
Количество строк и столбцов для генерации
Шанс на начальную инициализацию клетки (живая или мертвая)
Пределы "рождения" и "выживания" (от 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]
