Процедурная генерация карты (часть 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));
}

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

void Map::generate(int roomsCount) { m_rooms.clear(); // второй цикл предотвращает залипание, в случае если на карту уже не помещается ни одной комнаты for (int i = 0; i < roomsCount; ++i) for (int j = 0; j < 1000; ++j) { // ширина и высота комнаты в пределах [10,40] const int w = 10 + rand() % 31, h = 10 + rand() % 31; // избегаем "прилипания" комнаты к краю карты const Room room = {3 + rand() % (m_width - w - 6), 3 + rand() % (m_height - h - 6), w, h}; // найдем первую комнату, из уже существующих, которая пересекается с новой auto intersect = std::find_if(std::begin(m_rooms), std::end(m_rooms), [&room](const Room &r){ return room.intersect(r); }); // если новая комната не имеет пересечений - добавляем ее if (intersect == std::end(m_rooms)) { m_rooms.push_back(room); break; } } }

// зануляем карту индексом 0 m_data.assign(m_width * m_height, 0); // пространство комнат заполняем индексом 1 for (const Room &room : m_rooms) { for (int x = 0; x < room.w; ++x) for (int y = 0; y < room.h; ++y) { m_data[(room.x + x) + (room.y + y) * m_width] = 1; } }

Соединение комнат коридорами

Теперь все эти комнаты надо связать между собой коридорами, иначе как наш герой будет перемещаться по карте? И снова идея достаточно проста - последовательно переберём комнаты на карте и ищем путь от середины одной комнаты до середины следующей в списке, таким образом получая гарантированный проход от первой до последней комнаты.

Для поиска пути используем базовый алгоритм A* (A star), который подробно описан во множестве источников, например здесь. Я использовал такой код (версия без оптимизаций):

struct Point {
    int x, y, cost;
    
    bool operator==(const Point &p) const {
        return x == p.x && y == p.y;
    }
    
    bool operator<(const Point &p) const {
        return cost > p.cost;
    }
};

void Map::generatePassage(const Point &start, const Point &finish) {
    // для хранения направления на "родительскую" клетку
    std::vector<int> parents(m_width * m_height, -1);
    
    // приоритетная очередь доступных клеток, отсортирована по "стоимости"
    std::priority_queue<Point> active;
    active.push(start);
    
    // направления возможных перемещений
    static const int directions[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    while (!active.empty()) {
        // берем самую "дешевую" клетку из списка доступных
        const Point point = active.top();
        active.pop();
        
        if (point == finish)
            break;
        
        // продолжаем поиск в доступных направлениях
        for (int i = 0; i < 4; ++i) {
            Point p = {point.x - directions[i][0], point.y - directions[i][1], 0};
            if (p.x < 0 || p.y < 0 || p.x >= m_width || p.y >= m_height)
                continue;
            
            // если мы еще не посещали заданную клетку
            if (parents[p.x + p.y * m_width] < 0) {
                // вычисляем "стоимость" указанной клетки
                p.cost = calcCost(p, finish);
                active.push(p);
                
                parents[p.x + p.y * m_width] = i;
            }
        }
    }
    
    // путь найден - теперь прокладываем его на карте, начиная с конца
    Point point = finish;
    while (!(point == start)) {
        m_data[point.x + point.y * m_width] = 1;
        
        const int *directon = directions[parents[point.x + point.y * m_width]];
        point.x += directon[0];
        point.y += directon[1];
    }
}

Функция calcCost() возвращает «стоимость» клетки, вычисляемую таким образом, что нам выгоднее перемещаться по уже существующим комнатам и коридорам, чем создавать новые. Плюс небольшая эвристика, которая позволяет нам целенаправленно идти к конечной точке. С этими параметрами вы можете поиграться самостоятельно.

После построения коридоров у нас на руках окажется карта такого вида:

Создание стен и заключительная чистка

Для полноты не хватает еще одной небольшой детали — стен. Конечно, можно обойтись и без них, но, как правило, стены можно красиво нарисовать, визуально разграничивая пространство карты.

Поэтому добавим новый метод, который пройдется по всей карте и добавит стены везде, где «пустые» клетки граничат с клетками комнат и коридоров:

void Map::generateWalls() { // смещения для соседних клеток static const int offsets[8][2] = { {-1,-1}, { 0,-1}, { 1,-1}, { 1, 0}, { 1, 1}, { 0, 1}, {-1, 1}, {-1, 0}, }; // игнорируем край карты, чтобы не проверять граничные условия for (int x = 1; x < m_width - 1; ++x) for (int y = 1; y < m_height - 1; ++y) { if (m_data[x + y * m_width] == 0) for (int i = 0; i < 8; ++i) { // если по соседству есть хоть одна клетка комнаты или коридора - размещаем стену (индекс 2) if (m_data[(x + offsets[i][0]) + (y + offsets[i][1]) * m_width] == 1) { m_data[x + y * m_width] = 2; break; } } } }

Заключение

Программа, которая генерирует карту изложенным способом: levelgen1

Надеюсь мое описание достаточно простого алгоритма для процедурной генерации карты поможет вам в создании своих небольших (а кто знает, может и больших) игр. Делитесь своими идеями, пожеланиями и сообщайте об ошибках в комментариях.

11 ноября 2013 (Обновление: 13 ноя 2013)