Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре 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(); } }
Снова удаляем тупики
В конце в течение нескольких итераций удаляем тупики, как было описано выше. Этот этап необязателен, но я убираю лишние тупики для удобства геймплея. Но если они вам нравятся, их можно оставить!
Вот и всё!
Вот так можно сгенерировать пещерную карту без разрывов. Можете использовать этот способ в любом проекте с процедурной генерацией!
