Лабиринты являются неотъемлемой частью игровой индустрии практически с момента её зарождения. Дебютным проектом, в котором была реализована процедурная генерация уровней, стала Beneath Apple Manor, вышедшая в 1978 году. В ней использовался простейший метод разделения на комнаты и коридоры, что зачастую приводило к созданию монотонных и легко предугадываемых структур, снижавших интерес к игровому процессу. Стремясь к большей органичности, разработчики обратились к алгоритмам теории графов. В данном материале мы разберем способы построения «идеального» лабиринта, взяв за основу алгоритм Прима.
Что представляет собой идеальный лабиринт?
Под определением «идеальный» подразумевается лабиринт, в котором полностью отсутствуют замкнутые циклы и недоступные для посещения зоны. Это означает, что между любыми двумя точками существует строго один маршрут. С точки зрения теории графов такой лабиринт является деревом. Кроме того, в нем не должно встречаться шахматное расположение пустых пространств и препятствий следующего вида:
|
стена |
проход |
|
проход |
стена |
Принцип работы алгоритма Прима
Алгоритм Прима предназначен для поиска минимального остовного дерева — подграфа, который соединяет все вершины исходного графа при минимально возможной суммарной стоимости ребер.
В процессе работы алгоритм разделяет вершины графа на два множества. На каждой итерации выбирается ребро с наименьшим весом, соединяющее вершину из уже сформированной части с вершиной из оставшегося множества. Выбранная вершина переносится в основную часть, и процесс повторяется до тех пор, пока не будут задействованы все точки. Мы рассмотрим адаптированную версию алгоритма для графов с равнозначными ребрами, что идеально подходит для генерации игровых сеток.
Первый вариант реализации
В этой схеме вершинами графа выступают все ячейки сетки. По мере выполнения алгоритма часть из них закрепляется как элементы пути, а другие превращаются в стены, если их присоединение нарушает правила построения идеального лабиринта.
class Maze:
# Возможные направления движения: по сторонам и по диагонали
side_directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
corner_directions = [[1, 1], [1, -1], [-1, -1], [-1, 1]]
def __init__(self, n: int, m: int):
self.n = n
self.m = m
# 0 — стена, 1 — проход
self.cell_status = tuple([0 for _ in range(m)] for _ in range(n))
# Точка входа
self.cell_status[0][0] = 1
# Счетчик соседних клеток пути для предотвращения циклов
self.cnt_side_neighbours = tuple([0 for _ in range(m)] for _ in range(n))
def update_neighbours(self, cell: tuple[int, int], neighbours: set):
for direction in self.side_directions:
new_cell = (cell[0] + direction[0], cell[1] + direction[1])
if not self.in_field(new_cell): continue
self.cnt_side_neighbours[new_cell[0]][new_cell[1]] += 1
neighbours.add(new_cell)
def in_field(self, cell: tuple[int, int]):
return 0 <= cell[0] < self.n and 0 <= cell[1] < self.m
def is_placement_ok(self, cell: tuple[int, int]):
# Проверка диагональных соседей для соблюдения структуры
for direction in self.corner_directions:
new_cell = (cell[0] + direction[0], cell[1] + direction[1])
if not self.in_field(new_cell): continue
# Предотвращение формирования "шахматных" узлов
side_cell_1 = (new_cell[0], cell[1])
side_cell_2 = (cell[0], new_cell[1])
if self.cell_status[new_cell[0]][new_cell[1]] == 1 and \
self.cell_status[side_cell_1[0]][side_cell_1[1]] == 0 and \
self.cell_status[side_cell_2[0]][side_cell_2[1]] == 0:
return False
return True
def Prim(self):
# Список доступных для расширения кандидатов
neighbours = {(0, 0)}
self.update_neighbours((0, 0), neighbours)
while neighbours:
cell = neighbours.pop()
if not self.in_field(cell) or self.cell_status[cell[0]][cell[1]] == 1:
continue
# Если добавление клетки создаст цикл или нарушит "идеальность"
if not self.is_placement_ok(cell) or self.cnt_side_neighbours[cell[0]][cell[1]] >= 2:
continue
# Валидация пройдена: добавляем клетку в структуру пути
self.cell_status[cell[0]][cell[1]] = 1
self.update_neighbours(cell, neighbours)
def visuialise(self):
for row in self.cell_status:
for cell in row:
print("0" if cell == 1 else "1", end="")
print()
def main():
n, m = map(int, input().split())
maze = Maze(n, m)
maze.Prim()
maze.visuialise()
if __name__ == '__main__':
main()
Второй вариант реализации
Этот метод демонстрирует более высокую производительность, хотя его логика несколько сложнее. Мы расширяем исходную область до размера (a+2)x(b+2), где клетки с нечетными координатами назначаются опорными вершинами графа. Задача сводится к связыванию этих вершин. Стартуя из точки [1][1], мы на каждом этапе выбираем случайное неиспользованное ребро, ведущее к еще не посещенной вершине. Результат считывается в границах от [1][1] до [a][b]. Ключевое преимущество — высокая вариативность уровней благодаря элементу случайности при выборе путей.
import random
class Edge:
"""Объект ребра, связывающий родительскую ячейку с целевой."""
def __init__(self, parent_i, parent_j, cur_i, cur_j):
self.parent_i = parent_i
self.parent_j = parent_j
self.cur_i = cur_i
self.cur_j = cur_j
a, b = map(int, input().split())
labyrinth = []
# Формирование сетки: нечетные клетки — потенциальные пути, остальные — стены
for i in range(a + 2):
row = []
for j in range(b + 2):
row.append(0 if i % 2 == 1 and j % 2 == 1 else 1)
labyrinth.append(row)
visited = [[False for _ in range(b + 2)] for _ in range(a + 2)]
visited[1][1] = True
front = []
# Инициализация начальных ребер от стартовой точки
if 3 < b + 2: front.append(Edge(1, 1, 1, 3))
if 3 < a + 2: front.append(Edge(1, 1, 3, 1))
while front:
# Выбор случайного ребра для обеспечения уникальности лабиринта
idx = random.randint(0, len(front) - 1)
front[idx], front[-1] = front[-1], front[idx]
edge = front.pop()
if visited[edge.cur_i][edge.cur_j]:
continue
visited[edge.cur_i][edge.cur_j] = True
# "Прорубаем" проход между вершинами
mid_i = (edge.parent_i + edge.cur_i) // 2
mid_j = (edge.parent_j + edge.cur_j) // 2
labyrinth[mid_i][mid_j] = 0
# Проверка границ и добавление новых ребер в очередь
if 0 < edge.cur_i < a + 1 and 0 < edge.cur_j < b + 1:
for di, dj in [(0, 2), (0, -2), (2, 0), (-2, 0)]:
ni, nj = edge.cur_i + di, edge.cur_j + dj
if 0 <= ni < a + 2 and 0 <= nj < b + 2 and not visited[ni][nj]:
front.append(Edge(edge.cur_i, edge.cur_j, ni, nj))
# Вывод итоговой матрицы
for i in range(1, a + 1):
print("".join(map(str, labyrinth[i][1:b+1])))
Резюме
Мы изучили два различных подхода к автоматической генерации идеальных лабиринтов. Подобные алгоритмические решения находят широкое применение в геймдизайне — от создания простых головоломок до сложной процедурной генерации многоуровневых подземелий. Надеемся, что этот разбор окажется полезным для ваших будущих проектов.
