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

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

Теперь у нас есть набор случайных комнат, который довольно легко можно преобразовать в 2D-массив карты:

// зануляем карту индексом 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() возвращает «стоимость» клетки, вычисляемую таким образом, что нам выгоднее перемещаться по уже существующим комнатам и коридорам, чем создавать новые. Плюс небольшая эвристика, которая позволяет нам целенаправленно идти к конечной точке. С этими параметрами вы можете поиграться самостоятельно.

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

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

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

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

После этого мы получим уже полноценную карту:

Но и этого мне показалось мало, поэтому я решил добавить финальную «чистку», где я убираю ненужные (на мой взгляд) стены и различные мелкие артефакты, код этого метода довольно «грязный», так что приводить его не буду, могу лишь сказать, что на выходе я получаю такой результат:

Заключение

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

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

#roguelike, #генерирование, #процедурная генерация

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

Комментарии [37]