Создание идеального лабиринта с помощью упрощённого алгоритма Прима

Лабиринты использовались в видеоиграх с момента их появления. Первой видеоигрой с процедурно генерируемым лабиринтом была Beneath Apple Manor, выпущенная в 1978 году. Лабиринт в ней генерировался методом деления на комнаты и коридоры, из-за этого лабиринт часто выглядел однообразным и предсказуемым, что портило впечатление от игры. Для того, чтобы лабиринт выглядел естественнее разработчики стали использовать различные алгоритмы на графах. В этой статье мы рассмотрим реализации генерации идеального лабиринта с помощью алгоритма Прима.

Что такое идеальный лабиринт?

Идеальный лабиринт - это лабиринт без циклов и без недостижимых областей. Из этого следует, что из каждой точки существует ровно один путь к любой другой точке, что на языке графов означает, что лабиринт является деревом ^[1]. Также не должно быть стен и проходов, расположенных следующим образом:

Алгоритм Прима и как он работает

Алгоритм Прима находит дерево с минимальной суммой весов рёбер, которое является подграфом изначального графа. Такие деревья называют минимальными остовными.

Алгоритм Прима делит граф на две части (компоненты), на каждом шаге находя ребро с минимальным весом между этими частями, каждый раз присоединяя одну вершину к первой части и удаляя из второй. Алгоритм заканчивается, когда во второй части не остаётся вершин. Изначально первая часть - одна вершина, а вторая - все остальные. В этой статье мы рассмотрим упрощённую версию алгоритма для графов, где все рёбра имеют одинаковый вес.

Первая реализация

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

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()
 [2]

Вторая реализация

Данная реализация быстрее первой, но она труднее в понимании. В этой реализации мы увеличиваем поле 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()
 [2]

Заключение

Мы рассмотрели два подхода к генерации идеальных лабиринтов. Результаты работы таких алгоритмов можно использовать для создания лабиринтов в играх или процедурной генерации уровней на их основе. Надеемся, материал был полезен.