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

Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре 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();
  }
}

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

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

Вот и всё!

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