Использование алгоритма Прима для генерации соединённых друг с другом пещер

Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре In the House of Silence. Главное преимущество этого способа заключается в том, что в отличие от других алгоритмов, он никаким образом не может сгенерировать карту с разделёнными частями.

Генерация идеального лабиринта

Как понятно из названия, я использую хорошо задокументированный рандомизированный алгоритм Прима. Описание этого алгоритма можно найти на Википедии, однако вы можете применить любой другой алгоритм генерации лабиринтов.

Для понятности я привёл псевдокод, описывающий алгоритм Прима. Будет довольно просто приспособить его под любой язык программирования.

// Create a 2D array to represent your map, setting all cells in the map as walls. Cell[][] map = new Cell[width][height]; for (h in height) {   for (w in width) {     map[w][h].make_wall();   } }  // Choose a random cell with odd x and y coordinates and clear it. int x = random_int(0, width / 2) * 2 + 1; int y = random_int(0, height / 2) * 2 + 1; map[x][y].clear_cell();  // Create an array and add valid cells that are two orthogonal spaces away from the cell you just cleared. Point[] to_check = new Point[0]; if (y - 2 >= 0) {   to_check.append(new Point(x, y - 2)); } if (y + 2 < height) {   to_check.append(new Point(x, y + 2)); } if (x - 2 >= 0) {   to_check.append(new Point(x - 2, y)); } if (x + 2 < width) {   to_check.append(new Point(x + 2, y)); }  // While there are cells in your growable array, choose choose one at random, clear it, and remove it from the growable array. while (to_check.size() > 0) {   int index = random_int(0, to_check.size());   Point cell = to_check.get(index);   x = cell.get_x();   y = cell.get_y();   map[x][y].make_clear();   to_check.remove(index);    // The cell you just cleared needs to be connected with another clear cell.   // Look two orthogonal spaces away from the cell you just cleared until you find one that is not a wall.   // Clear the cell between them.   Direction[] d = {Direction.NORTH, Direction.SOUTH, Direction.EAST, Direction.WEST};   while (d.size() > 0) {     int dir_index = random_int(0, d.size());     switch (d[dir_index]) {       case Direction.NORTH:         if (y - 2 >= 0 && map[x][y - 2].is_clear()) {           map[x][y - 1].make_clear();           d.remove_all();         }         break;       case Direction.SOUTH:         if (y + 2 < height && map[x][y + 2].is_clear()) {           map[x][y + 1].clear();           d.remove_all();         }         break;       case Direction.EAST:         if (x - 2 >= 0 && map[x - 2][y].is_clear()) {           map[x - 1][y].make_clear();           d.remove_all();         }         break;       case Direction.WEST:         if (x + 2 < width && map[x + 2][y].is_clear()) {           map[x + 1][y].make_clear();           d.remove_all();         }         break;     }     d.remove(dir_index);   }    // Add valid cells that are two orthogonal spaces away from the cell you cleared.   if (y - 2 >= 0 && map[x][y - 2].is_wall()) {     to_check.append(new Point(x, y - 2));   }   if (y + 2 < height && map[x][y + 2].is_wall()) {     to_check.append(new Point(x, y + 2));   }   if (x - 2 >= 0 && map[x - 2][y].is_wall()) {     to_check.append(new Point(x - 2, y));   }   if (x + 2 < width && map[x + 2][y].is_wall()) {     to_check.append(new Point(x + 2, y));   } }

Избавляемся от тупиков

Затем несколько раз удалим тупики. Просто итеративно пройдём по каждой пустой ячейке карты, а затем удалим все, у которых есть только одна соседняя ячейка, не являющаяся стеной. Можно проделывать это любое нужное количество итераций, но я рекомендую выполнить не менее трёх итераций. Если повторить операцию меньшее количество раз, то карты становится слишком просторными.

for (i in 4) {   // Get a list of all dead ends by checking the number of neighboring cells.   Cell[] dead_ends = new Cell[0];   for (h in height) {     for (w in width) {       if (map[w][h].is_clear()) {         int neighbors = 0;         if (h - 1 >= 0 && map[w][h - 1].is_clear()) {           neighbors++;         }         if (h + 1 < height && map[w][h + 1].is_clear()) {           neighbors++;         }         if (w - 1 >= 0 && map[w - 1][h].is_clear()) {           neighbors++;         }         if (w + 1 < width && map[w + 1][h].is_clear()) {           neighbors++;         }         if (neighbors <= 1) {           dead_ends.append(new Point(w, h))         }     }   }    // Remove those dead ends.   for (cell in dead_ends) {     map[cell.get_x()][cell.get_y()].make_wall();   } }

Выращиваем карту при помощи клеточных автоматов

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

for (i in 3) {   // Add cell to the list if it has four or more cleared neighbors.   Cell[] new_cells = new Cell[0];   for (h in height) {     for (w in width) {       if (map[w][h].is_wall()) {         int neighbors = 0;         for (a in 3) {           for (b in 3) {             int neighbor_x = w - a;             int neighbor_y = h - b;             if (neighbor_x >= 0 && neighbor_x < width && neighbor_y >= 0 && neighbor_y < height) {               if (map[neighbor_x][neighbor_y].is_clear()) {                 neighbors++;               }             }           }         }         if (neighbors >= 4) {           new_cells.append(new Point(w, h));         }       }     }   }    // Clear those cells.   for (cell in new_cells) {     map[cell.get_x()][cell.get_y()].make_clear();   } }

Снова удаляем тупики

В конце в течение нескольких итераций удаляем тупики, как было описано выше. Этот этап необязателен, но я убираю лишние тупики для удобства геймплея. Но если они вам нравятся, их можно оставить!

Вот и всё!

Вот так можно сгенерировать пещерную карту без разрывов. Можете использовать этот способ в любом проекте с процедурной генерацией!