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