Процедурная генерация карты (часть 1)
Автор: Артем Гуревич
В этой короткой статье я поделюсь нехитрым алгоритмом, для процедурного генерирования геометрии карты, который я собрал как прототип для своей небольшой roguelike-like игры.
Чтобы было понятно, о чем пойдет речь, на выходе получаются такие карты (кликайте для увеличения):
Сразу оговорюсь, что речь пойдет про генерирование только геометрии карты, если удачно пойдет такой материал, то дальше будем говорить про процедурную генерацию остальных элементов игры — вещей, монстров, событий.
За основу алгоритма я взял замечательную статью Procedural Generation - The Dungeons инди-разработчика игр Ноэла Берри (Noel Berry). Обязательно посетите его сайт, у него классные игры!
Предлагаемый подход достаточно прост, его можно разбить на три этапа:
1. Генерирование и размещение комнат.
2. Соединение комнат коридорами.
3. Создание стен и заключительная чистка.
Генерирование и размещение комнат
Первое что мы сделаем — создадим игровое поле и разместим на нем несколько случайных комнат, которые станут основой нашей карты.
Для начала заведем структуры для карты и комнат в ней (сразу задаем размеры карты):
class Map { public: struct Room { int x, y, w, h; }; Map(int width, int height): m_width( width), m_height( height) { m_data.resize( width * height, 0); } private: int m_width, m_height; // размеры карты std::vector<int> m_data; // финальные данные карты std::vector<Room> m_rooms; // комнаты };
Одно из требований для новой комнаты: она не должна пересекаться с существующими, но мне, также, хотелось, чтобы комнаты стояли плотно друг к другу, поэтому я добавил в Room такую функцию для проверки пересечения:
bool Room::intersect(const Room &r) const { return !( r.x >= ( x + w) || x >= ( r.x + r.w) || r.y >= ( y + h) || y >= ( r.y + r.h)); }
Вот теперь можно сгенерировать несколько комнат со случайным расположением и размерами, для этого добавим новый метод: