Лабиринты использовались в видеоиграх с момента их появления. Первой видеоигрой с процедурно генерируемым лабиринтом была 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]): if 0 <= cell[0] < self.n and 0 <= cell[1] < self.m: return True return False 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): continue # Если клетка уже путь - пропускаем if self.cell_status[cell[0]][cell[1]] == 1: continue # Если размещение клетки приведёт к нарушению идельности лабиринта - пропускаем if not self.is_placement_ok(cell): continue if 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: # Путь if cell == 1: print("0", end="") # Не путь else: print("1", end="") print() def main(): n, m = map(int, input().split()) maze = Maze(n, m) maze.Prim() maze.visuialise() if __name__ == '__main__': main()
Вторая реализация
Данная реализация быстрее первой, но она труднее в понимании. В этой реализации мы увеличиваем поле a*b до поля (a + 2)*(b+2), а затем присваиваем клеткам с нечётным номером строки и столбца статус вершины. Таким образом у нас появляется вершины графа, которые надо связать. Мы начинаем из вершины [1][1] и каждый шаг выбираем случайное неиспользованное ребро, доступное из вершин, которые уже в дереве. Итоговый ответ будет находится на индексах матрицы [1][1] - [a][b]. Главное преимущество данной реализации - благодаря случайному выбору ребра каждый раз лабиринт получается разный.
import random class Edge: """Класс, хра��ящий ребро, соединяющее клетку матрицы [parent_i][parent_j] и [cur_i][cur_j].""" def __init__(self, parent_i: int, parent_j: int, cur_i: int, cur_j: int): """ Инициализация ребра. 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): # Заполняем лабиринт стенами (1) и перекрёстками (0) temp = [] for j in range(b + 2): if i % 2 == 1 and j % 2 == 1: temp.append(0) else: temp.append(1) labyrinth.append(temp) visited = [] # Матрица, хранящая была ли клетка [i][j] уже посещена алгоритмом for i in range(a + 2): temp = [] for j in range(b + 2): temp.append(False) visited.append(temp) visited[1][1] = True # Начинаем с вершины 1,1 front = [] # Массив, в котором будут храниться все обрабатываемые рёбра if 3 < b + 2: front.append(Edge(1, 1, 1, 3)) # По возможности добавляем соседа клетки 1, 1 справа if 3 < a + 2: front.append(Edge(1, 1, 3, 1)) # По возможности добавляем соседа клетки 1, 1 снизу while len(front) != 0: random_edge_index = random.randint(0, len(front) - 1) # Выбираем случайное ребро из списка обрабатываемых рёбер # Для лучшей асимптотики меняем местами выбранное и последнее ребро front[random_edge_index], front[len(front) - 1] = front[len(front) - 1], front[random_edge_index] current_edge: Edge = front[len(front) - 1] # Запоминаем выбранное ребро front.pop() # Удаляем выбранное ребро из списка обрабатываемых рёбер if visited[current_edge.cur_i][current_edge.cur_j]: # Если вершина уже посещена, заканчиваем обработку этого ребра continue visited[current_edge.cur_i][current_edge.cur_j] = True # Отмечаем вершину как посещённую # Соединяем вершину с её родителем if current_edge.parent_i > current_edge.cur_i: labyrinth[current_edge.cur_i + 1][current_edge.cur_j] = 0 elif current_edge.parent_i < current_edge.cur_i: labyrinth[current_edge.cur_i - 1][current_edge.cur_j] = 0 elif current_edge.parent_j > current_edge.cur_j: labyrinth[current_edge.cur_i][current_edge.cur_j + 1] = 0 else: labyrinth[current_edge.cur_i][current_edge.cur_j - 1] = 0 # Если вершина находится в необрабатываемой зоне, заканчиваем обработку ребра if current_edge.cur_i == 0 or current_edge.cur_i == a + 1: continue if current_edge.cur_j == 0 or current_edge.cur_j == b + 1: continue # Добавляем в список обрабатываемых рёбер рёбра, ведущие к не посещённым соседям вершины if current_edge.cur_i + 2 < a + 2 and not visited[current_edge.cur_i + 2][current_edge.cur_j]: front.append(Edge(current_edge.cur_i, current_edge.cur_j, current_edge.cur_i + 2, current_edge.cur_j)) if current_edge.cur_i - 2 >= 0 and not visited[current_edge.cur_i - 2][current_edge.cur_j]: front.append(Edge(current_edge.cur_i, current_edge.cur_j, current_edge.cur_i - 2, current_edge.cur_j)) if current_edge.cur_j + 2 < b + 2 and not visited[current_edge.cur_i][current_edge.cur_j + 2]: front.append(Edge(current_edge.cur_i, current_edge.cur_j, current_edge.cur_i, current_edge.cur_j + 2)) if current_edge.cur_j - 2 >= 0 and not visited[current_edge.cur_i][current_edge.cur_j - 2]: front.append(Edge(current_edge.cur_i, current_edge.cur_j, current_edge.cur_i, current_edge.cur_j - 2)) for i in range(1, a + 1): # Выводим обрабатываемую зону for j in range(1, b + 1): print(labyrinth[i][j], end="") print()
Заключение
Мы рассмотрели два подхода к генерации идеальных лабиринтов. Результаты работы таких алгоритмов можно использовать для создания лабиринтов в играх или процедурной генерации уровней на их основе. Надеемся, материал был полезен.
