← Все примеры

Генератор лабиринтов

Программа генерирует случайный лабиринт размером $15 \times 15$ и находит в нём путь от левого верхнего угла до правого нижнего. Для генерации используется поиск в глубину (DFS), а для поиска выхода -- правило правой руки.

Идея алгоритма

Программа состоит из двух частей:

Генерация лабиринта (DFS с возвратом):

1. Начинаем с клетки $(0, 0)$, помечаем её как посещённую
2. Выбираем случайного непосещённого соседа
3. Убираем стену между текущей клеткой и соседом
4. Переходим к соседу и повторяем с шага 2
5. Если все соседи уже посещены -- возвращаемся назад (backtracking)
6. Когда стек пуст -- лабиринт готов

Поиск выхода (правило правой руки):

1. Встаём в клетку $(0, 0)$, смотрим на юг
2. На каждом шаге пробуем повернуть направо и пойти
3. Если направо стена -- пробуем идти прямо
4. Если и прямо стена -- пробуем налево
5. Если везде стены -- разворачиваемся
6. Повторяем, пока не дойдём до клетки $(14, 14)$

Разбор

Параметры и главный алгоритм

использовать Робот

| Параметры лабиринта
цел ШИРИНА = 15
цел ВЫСОТА = 15

алг
нач
    | Генерируем лабиринт и сохраняем в файл
    вывод "Генерация лабиринта ", ШИРИНА, "x", ВЫСОТА, "...", нс
    генерировать_лабиринт
    вывод "Лабиринт создан", нс

    | Теперь ищем выход (робот загрузит файл при первой команде)
    вывод "Поиск выхода...", нс
    искать_выход
    вывод "Готово!", нс
кон

Константы ШИРИНА и ВЫСОТА задают размер лабиринта. Главный алгоритм последовательно вызывает генерацию и поиск выхода.

Структуры данных для лабиринта

    | Массивы для хранения стен
    | wallRight[x,y] = 1 если есть стена справа от (x,y)
    | wallDown[x,y] = 1 если есть стена снизу от (x,y)
    цел таб wallRight[0:ШИРИНА-1, 0:ВЫСОТА-1]
    цел таб wallDown[0:ШИРИНА-1, 0:ВЫСОТА-1]
    цел таб visited[0:ШИРИНА-1, 0:ВЫСОТА-1]

Лабиринт хранится в двух двумерных массивах стен:

• wallRight[x, y] -- есть ли стена между клеткой $(x, y)$ и клеткой $(x+1, y)$ (справа)
• wallDown[x, y] -- есть ли стена между клеткой $(x, y)$ и клеткой $(x, y+1)$ (снизу)

Изначально все стены стоят (1), а все клетки непосещены (0). Достаточно хранить только правые и нижние стены -- левая стена клетки $(x, y)$ это правая стена клетки $(x-1, y)$, а верхняя -- это нижняя стена клетки $(x, y-1)$.

Поиск в глубину (DFS) -- что это такое

Поиск в глубину (DFS, depth-first search) -- это способ обхода, при котором мы идём "вглубь" как можно дальше, а когда заходим в тупик -- возвращаемся и пробуем другой путь.

Представьте, что вы стоите в начале коридора с развилками. Вы всегда выбираете первый попавшийся поворот и идёте дальше. Когда упираетесь в тупик, возвращаетесь к последней развилке и пробуете другой поворот. Это и есть DFS.

В программе DFS реализован итеративно (через стек), а не рекурсивно. Стек хранит координаты клеток, по которым мы прошли:

    | Итеративный DFS со стеком
    цел таб стекX[1:ШИРИНА*ВЫСОТА], стекY[1:ШИРИНА*ВЫСОТА]
    цел верх

    верх := 1
    стекX[1] := 0
    стекY[1] := 0
    visited[0, 0] := 1

• стекX и стекY -- массивы, моделирующие стек координат
• верх -- указатель на вершину стека
• Начинаем с клетки $(0, 0)$

Перемешивание направлений

        | Перемешиваем направления
        цел таб dirs[0:3]
        dirs[0] := 0; dirs[1] := 1; dirs[2] := 2; dirs[3] := 3
        цел i, j, t
        нц для i от 3 до 1 шаг -1
            j := rnd(i + 1)
            t := dirs[i]; dirs[i] := dirs[j]; dirs[j] := t
        кц

Четыре направления (0 -- вверх, 1 -- вправо, 2 -- вниз, 3 -- влево) перемешиваются алгоритмом Фишера -- Йетса. Благодаря этому каждый раз генерируется новый случайный лабиринт.

Поиск непосещённого соседа и удаление стены

        нц для i от 0 до 3
            напр := dirs[i]
            выбор
                при напр = 0: nx := cx; ny := cy - 1     | вверх
                при напр = 1: nx := cx + 1; ny := cy     | вправо
                при напр = 2: nx := cx; ny := cy + 1     | вниз
                при напр = 3: nx := cx - 1; ny := cy     | влево
            все

            если nx >= 0 и nx < ШИРИНА и ny >= 0 и ny < ВЫСОТА
                то
                    если visited[nx, ny] = 0
                        то
                            найден := 1
                            выход
                    все
            все
        кц

Для текущей клетки $(cx, cy)$ перебираем направления в случайном порядке. Для каждого вычисляем координаты соседа $(nx, ny)$. Проверяем, что сосед внутри поля и ещё не посещён.

        если найден = 1
            то
                | Убираем стену между (cx,cy) и (nx,ny)
                выбор
                    при напр = 0:  | вверх
                        wallDown[cx, cy - 1] := 0
                    при напр = 1:  | вправо
                        wallRight[cx, cy] := 0
                    при напр = 2:  | вниз
                        wallDown[cx, cy] := 0
                    при напр = 3:  | влево
                        wallRight[cx - 1, cy] := 0
                все

                | Добавляем соседа в стек
                visited[nx, ny] := 1
                верх := верх + 1
                стекX[верх] := nx
                стекY[верх] := ny
            иначе
                | Backtrack
                верх := верх - 1
        все

Если непосещённый сосед найден -- убираем стену между текущей клеткой и соседом (ставим 0 в соответствующий массив стен) и добавляем соседа в стек.

Если все соседи уже посещены -- выполняем возврат (backtracking): уменьшаем верх на 1, тем самым "снимая" текущую клетку со стека и возвращаясь к предыдущей. Это ключевой момент алгоритма: возврат позволяет исследовать все ветви.

Сохранение лабиринта в файл

    | Сохраняем лабиринт в файл
    файл ф
    ф := открыть на запись("maze.fil")

    | Размер и позиция робота
    вывод ф, ШИРИНА, " ", ВЫСОТА, нс
    вывод ф, "0 0", нс

    | Записываем клетки со стенами
    нц для y от 0 до ВЫСОТА - 1
        нц для x от 0 до ШИРИНА - 1
            цел wE, wS
            wE := 0; wS := 0

            если x < ШИРИНА - 1
                то wE := wallRight[x, y]
            все
            если y < ВЫСОТА - 1
                то wS := wallDown[x, y]
            все

            если wE = 1 или wS = 1
                то
                    | x y WallN WallE WallS WallW Painted PointMark Rad Temp R G B
                    вывод ф, x, " ", y, " 0 ", wE, " ", wS, " 0 0 0 0 0 0 0 0", нс
            все
        кц
    кц

    закрыть(ф)

Лабиринт записывается в файл maze.fil в формате, который понимает исполнитель Робот. Для каждой клетки указываются её координаты и наличие стен с восточной (wE) и южной (wS) сторон. При первой команде Робота (например, закрасить) исполнитель загрузит этот файл и построит поле.

Поиск выхода -- правило правой руки

Правило правой руки -- простой способ найти выход из односвязного лабиринта (то есть такого, где нет замкнутых островов стен). Идея: всегда старайся повернуть направо. Если не получается -- иди прямо. Не получается прямо -- поверни налево. Совсем тупик -- развернись.

алг искать_выход
нач
    цел направление
    направление := 2  | начинаем смотря на юг

    цел шагов, pos_x, pos_y
    шагов := 0
    pos_x := 0
    pos_y := 0

    нц пока не (pos_x = ШИРИНА - 1 и pos_y = ВЫСОТА - 1)
        закрасить

        | Правило правой руки: сначала пробуем направо
        цел правое
        правое := mod(направление + 1, 4)

        если можно_идти(правое)
            то
                направление := правое
                сделать_шаг(направление, pos_x, pos_y)
            иначе
                если можно_идти(направление)
                    то
                        сделать_шаг(направление, pos_x, pos_y)
                    иначе
                        цел левое
                        левое := mod(направление + 3, 4)
                        если можно_идти(левое)
                            то
                                направление := левое
                                сделать_шаг(направление, pos_x, pos_y)
                            иначе
                                направление := mod(направление + 2, 4)
                        все
                все
        все

        шагов := шагов + 1
        если шагов > ШИРИНА * ВЫСОТА * 10
            то
                вывод "Превышен лимит шагов", нс
                выход
        все
    кц

    закрасить
    вывод "Шагов: ", шагов, нс
кон

• Направления кодируются числами: 0 -- вверх, 1 -- вправо, 2 -- вниз, 3 -- влево
• Правый поворот вычисляется как $(\text{направление} + 1) \bmod 4$, левый -- как $(\text{направление} + 3) \bmod 4$, разворот -- $(\text{направление} + 2) \bmod 4$
• На каждом шаге Робот закрашивает клетку, оставляя за собой след
• Лимит шагов $\text{ШИРИНА} \times \text{ВЫСОТА} \times 10$ защищает от зацикливания

Вспомогательные алгоритмы

алг лог можно_идти(цел напр)
нач
    выбор
        при напр = 0: знач := сверху свободно
        при напр = 1: знач := справа свободно
        при напр = 2: знач := снизу свободно
        при напр = 3: знач := слева свободно
    все
кон

Алгоритм можно_идти принимает числовой код направления и возвращает да или нет, проверяя стену с помощью стандартных команд Робота.

алг сделать_шаг(цел напр, арг рез цел x, арг рез цел y)
нач
    выбор
        при напр = 0:
            вверх
            y := y - 1
        при напр = 1:
            вправо
            x := x + 1
        при напр = 2:
            вниз
            y := y + 1
        при напр = 3:
            влево
            x := x - 1
    все
кон

Алгоритм сделать_шаг перемещает Робота в указанном направлении и обновляет координаты x, y. Параметры объявлены как арг рез -- это означает, что они передаются по ссылке: алгоритм и читает, и изменяет их значение.

Полная программа

использовать Робот

| Генератор случайного лабиринта и поиск выхода
| Алгоритм генерации: рекурсивный backtracking
| Алгоритм поиска: правило правой руки
|
| Робот стартует в левом верхнем углу (0,0)
| Цель — дойти до правого нижнего угла

| Параметры лабиринта
цел ШИРИНА = 15
цел ВЫСОТА = 15

алг
нач
    | Генерируем лабиринт и сохраняем в файл
    вывод "Генерация лабиринта ", ШИРИНА, "x", ВЫСОТА, "...", нс
    генерировать_лабиринт
    вывод "Лабиринт создан", нс

    | Теперь ищем выход (робот загрузит файл при первой команде)
    вывод "Поиск выхода...", нс
    искать_выход
    вывод "Готово!", нс
кон

| Генерация лабиринта алгоритмом рекурсивного backtracking
алг генерировать_лабиринт
нач
    цел x, y

    | Массивы для хранения стен
    | wallRight[x,y] = 1 если есть стена справа от (x,y)
    | wallDown[x,y] = 1 если есть стена снизу от (x,y)
    цел таб wallRight[0:ШИРИНА-1, 0:ВЫСОТА-1]
    цел таб wallDown[0:ШИРИНА-1, 0:ВЫСОТА-1]
    цел таб visited[0:ШИРИНА-1, 0:ВЫСОТА-1]

    | Изначально все стены стоят, ничего не посещено
    нц для y от 0 до ВЫСОТА - 1
        нц для x от 0 до ШИРИНА - 1
            wallRight[x, y] := 1
            wallDown[x, y] := 1
            visited[x, y] := 0
        кц
    кц

    | Итеративный DFS со стеком
    цел таб стекX[1:ШИРИНА*ВЫСОТА], стекY[1:ШИРИНА*ВЫСОТА]
    цел верх

    верх := 1
    стекX[1] := 0
    стекY[1] := 0
    visited[0, 0] := 1

    нц пока верх > 0
        цел cx, cy
        cx := стекX[верх]
        cy := стекY[верх]

        | Перемешиваем направления
        цел таб dirs[0:3]
        dirs[0] := 0; dirs[1] := 1; dirs[2] := 2; dirs[3] := 3
        цел i, j, t
        нц для i от 3 до 1 шаг -1
            j := rnd(i + 1)
            t := dirs[i]; dirs[i] := dirs[j]; dirs[j] := t
        кц

        | Ищем непосещённого соседа
        цел найден, nx = 0, ny = 0, напр = 0
        найден := 0

        нц для i от 0 до 3
            напр := dirs[i]
            выбор
                при напр = 0: nx := cx; ny := cy - 1     | вверх
                при напр = 1: nx := cx + 1; ny := cy     | вправо
                при напр = 2: nx := cx; ny := cy + 1     | вниз
                при напр = 3: nx := cx - 1; ny := cy     | влево
            все

            если nx >= 0 и nx < ШИРИНА и ny >= 0 и ny < ВЫСОТА
                то
                    если visited[nx, ny] = 0
                        то
                            найден := 1
                            выход
                    все
            все
        кц

        если найден = 1
            то
                | Убираем стену между (cx,cy) и (nx,ny)
                выбор
                    при напр = 0:  | вверх
                        wallDown[cx, cy - 1] := 0
                    при напр = 1:  | вправо
                        wallRight[cx, cy] := 0
                    при напр = 2:  | вниз
                        wallDown[cx, cy] := 0
                    при напр = 3:  | влево
                        wallRight[cx - 1, cy] := 0
                все

                | Добавляем соседа в стек
                visited[nx, ny] := 1
                верх := верх + 1
                стекX[верх] := nx
                стекY[верх] := ny
            иначе
                | Backtrack
                верх := верх - 1
        все
    кц

    | Сохраняем лабиринт в файл
    файл ф
    ф := открыть на запись("maze.fil")

    | Размер и позиция робота
    вывод ф, ШИРИНА, " ", ВЫСОТА, нс
    вывод ф, "0 0", нс

    | Записываем клетки со стенами
    нц для y от 0 до ВЫСОТА - 1
        нц для x от 0 до ШИРИНА - 1
            цел wE, wS
            wE := 0; wS := 0

            если x < ШИРИНА - 1
                то wE := wallRight[x, y]
            все
            если y < ВЫСОТА - 1
                то wS := wallDown[x, y]
            все

            если wE = 1 или wS = 1
                то
                    | x y WallN WallE WallS WallW Painted PointMark Rad Temp R G B
                    вывод ф, x, " ", y, " 0 ", wE, " ", wS, " 0 0 0 0 0 0 0 0", нс
            все
        кц
    кц

    закрыть(ф)
кон

| Поиск выхода по правилу правой руки
| Закрашиваем клетки по пути
алг искать_выход
нач
    цел направление
    направление := 2  | начинаем смотря на юг

    цел шагов, pos_x, pos_y
    шагов := 0
    pos_x := 0
    pos_y := 0

    нц пока не (pos_x = ШИРИНА - 1 и pos_y = ВЫСОТА - 1)
        закрасить

        | Правило правой руки: сначала пробуем направо
        цел правое
        правое := mod(направление + 1, 4)

        если можно_идти(правое)
            то
                направление := правое
                сделать_шаг(направление, pos_x, pos_y)
            иначе
                если можно_идти(направление)
                    то
                        сделать_шаг(направление, pos_x, pos_y)
                    иначе
                        цел левое
                        левое := mod(направление + 3, 4)
                        если можно_идти(левое)
                            то
                                направление := левое
                                сделать_шаг(направление, pos_x, pos_y)
                            иначе
                                направление := mod(направление + 2, 4)
                        все
                все
        все

        шагов := шагов + 1
        если шагов > ШИРИНА * ВЫСОТА * 10
            то
                вывод "Превышен лимит шагов", нс
                выход
        все
    кц

    закрасить
    вывод "Шагов: ", шагов, нс
кон

| Проверить можно ли идти
алг лог можно_идти(цел напр)
нач
    выбор
        при напр = 0: знач := сверху свободно
        при напр = 1: знач := справа свободно
        при напр = 2: знач := снизу свободно
        при напр = 3: знач := слева свободно
    все
кон

| Сделать шаг и обновить позицию
алг сделать_шаг(цел напр, арг рез цел x, арг рез цел y)
нач
    выбор
        при напр = 0:
            вверх
            y := y - 1
        при напр = 1:
            вправо
            x := x + 1
        при напр = 2:
            вниз
            y := y + 1
        при напр = 3:
            влево
            x := x - 1
    все
кон

▶ Запустить пример