Лабиринт: генерация и поиск выхода

Начните с небольшого лабиринта

Выберите 7 × 5 клеток и seed 2. Запустите построение: стек уходит по ветке, возвращается из тупика и продолжает незавершённую ветвь. Генератор заканчивает работу только после обхода всей сетки. Попадание в клетку T во время построения его не останавливает.

После генерации запустите BFS, чтобы увидеть слои расстояния, затем DFS на том же лабиринте — для наблюдения за веткой и возвратами. Таблица сохраняет оба результата, пока стены и концы пути остаются прежними. Корень генерации всегда находится слева сверху; другой старт поиска меняет только поиск.

1. Остановитесь на паузе, сделайте шаг в обе стороны и перемотайте историю: очередь или стек соответствуют выбранной позиции.
2. Нажмите «Выбрать старт» или «Выбрать выход» и кликните клетку либо введите столбец и строку от единицы. После изменения полей нажмите «Старт» или «Найти путь». Выбор клетки готовит новый поиск на паузе.
3. Для большой сетки увеличьте масштаб и перетаскивайте поле. «Следить» удерживает текущую клетку при генерации и DFS; у BFS функция недоступна, поскольку волна расходится по нескольким ветвям. Ручной сдвиг отключает слежение.

Клетки — вершины, проходы — рёбра

Сетка width × height содержит N = width · height логических клеток. У каждой до четырёх геометрических соседей; перейти к соседу можно только через открытый проход. Диагоналей и весов нет: каждый переход стоит один шаг. Стены не занимают дополнительные вершины.

Идентификатор клетки — row · width + column, координаты в коде начинаются с нуля. В полях плеера и концах пути JSON отсчёт идёт от единицы. S и T обозначают клетки, а не отверстия во внешней границе. Например, при ширине 7 клетка (столбец 1, строка 2) имеет id 7.

Четыре бита хранят ЗАКРЫТЫЕ стены: север = 1, восток = 2, юг = 4, запад = 8. Маска 15 закрывает все стороны. Чтобы открыть проход на восток, убираем бит 2 у одной клетки и бит 8 у соседней. Обе стороны обязаны совпадать, внешняя граница остаётся закрытой. При загрузке JSON сайт проверяет эти условия.

JavaScript

// Directions: north, east, south, west. A set bit means a closed wall.
const WALL = [1, 2, 4, 8];
const DX = [0, 1, 0, -1], DY = [-1, 0, 1, 0];
function neighbor(maze, cell, direction) {
    const x = cell % maze.width + DX[direction];
    const y = Math.floor(cell / maze.width) + DY[direction];
    return x < 0 || x >= maze.width || y < 0 || y >= maze.height
        ? -1 : y * maze.width + x;
}
function seededRandom(seed) {
    let state = seed >>> 0;
    return () => {
        state = (state + 0x6d2b79f5) >>> 0;
        let value = Math.imul(state ^ (state >>> 15), state | 1);
        value ^= value + Math.imul(value ^ (value >>> 7), value | 61);
        return ((value ^ (value >>> 14)) >>> 0) / 4294967296;
    };
}

Рандомизированный DFS прокладывает проходы и возвращается

В начале все стены закрыты. Отмечаем верхнюю левую клетку и кладём её кадр в стек. При входе в каждую клетку один раз перемешиваем четыре направления алгоритмом Фишера — Йетса. Кадр хранит этот порядок и индекс следующего направления. Явный стек повторяет рекурсивный обход с возвратами, не расходуя стек вызовов JavaScript.

Следующий блок использует помощники выше. Это синхронное ядро для корректных входов, без валидации плеера, неизменяемых обёрток результата, событий анимации и истории. Размеры — положительные целые числа, seed — uint32; на сайте каждая сторона дополнительно ограничена 201 клеткой.

1. Проверяем следующее направление верхнего кадра. Пропускаем соседа за границей или уже посещённую клетку.
2. Для непосещённого соседа убираем общую стену с обеих сторон, отмечаем клетку и кладём в стек её новый кадр с перемешанными направлениями.
3. Когда все четыре направления кадра рассмотрены, снимаем его и продолжаем родителя. Повторяем, пока стек не опустеет.

JavaScript

function generateMaze(width, height, seed) {
    const maze = { width, height, walls: new Uint8Array(width * height).fill(15) };
    const visited = new Uint8Array(width * height), random = seededRandom(seed);
    function frame(cell) {
        const directions = [0, 1, 2, 3];
        for (let i = 3; i > 0; i--) {
            const j = Math.floor(random() * (i + 1));
            [directions[i], directions[j]] = [directions[j], directions[i]];
        }
        return { cell, directions, next: 0 };
    }
    const stack = [frame(0)];
    const counters = { visitedCount: 1, passageCount: 0,
        directionChecks: 0, maxStackSize: 1 };
    visited[0] = 1;
    while (stack.length) {
        const call = stack[stack.length - 1];
        if (call.next === 4) { stack.pop(); continue; }
        const d = call.directions[call.next++];
        const next = neighbor(maze, call.cell, d);
        counters.directionChecks++;
        if (next === -1 || visited[next]) continue;
        maze.walls[call.cell] &= ~WALL[d];
        maze.walls[next] &= ~WALL[(d + 2) % 4];
        visited[next] = 1;
        counters.visitedCount++;
        counters.passageCount++;
        stack.push(frame(next));
        counters.maxStackSize = Math.max(counters.maxStackSize, stack.length);
    }
    return { topology: maze, counters };
}

Почему путь гарантирован

Каждый новый проход соединяет посещённую область ровно с одной ещё не посещённой клеткой. Область остаётся связной, а соединения между двумя уже включёнными вершинами не добавляются, поэтому цикл не возникает. Стек показывает текущую ветку растущего дерева.

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

Открыто ровно N − 1 проходов; результат — остовное дерево сетки. Между любыми двумя клетками существует ровно один простой путь. Для любых допустимых S и T путь гарантирован, включая S = T с длиной ноль. Это свойство сгенерированного лабиринта: загруженная схема может быть несвязной.

Seed повторяет лабиринт, но не даёт равномерного выбора

Реализация использует Mulberry32 и фиксированный исходный порядок направлений перед каждым перемешиванием Фишера — Йетса. Одинаковые размеры, seed и версия генератора дают одинаковый лабиринт. Скорость воспроизведения, размер окна и концы поиска не расходуют случайные числа и не меняют стены. Seed — целое от 0 до 4294967295; ноль допустим.

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

BFS — волна кратчайших расстояний

Кладём S в очередь FIFO и задаём расстояние ноль. Извлекаем самую давно ожидающую клетку, проверяем север, восток, юг и запад и добавляем ещё не обнаруженных соседей через открытые проходы. Отмечаем соседа при добавлении, один раз записываем родителя и расстояние текущей клетки плюс один. Цикл не сможет повторно поставить клетку в очередь.

Очередь обрабатывает слои по неубыванию расстояния. Когда клетка с расстоянием d впервые обнаруживает соседа, все более близкие слои уже обработаны: d + 1 будет кратчайшим расстоянием до него. На такой сетке с одинаковой ценой перехода BFS реализует волновой поиск, обычно связываемый с алгоритмом Ли. Волна распространяется по проходам, а не напрямую через стены к геометрически близким клеткам.

В этом плеере поиск останавливается, когда T извлечена из очереди и стала текущей, до проверки её направлений. Можно завершать и при обнаружении — для нахождения расстояния этого достаточно, но счётчики будут другими. Оттенки и подписи показывают слои; в живой очереди могут одновременно ожидать клетки соседних слоёв.

DFS сначала исследует одну ветвь

Поиск использует фиксированный порядок север–восток–юг–запад, без случайности. Каждый кадр помнит следующее направление. Обнаруживаем непосещённого соседа, записываем родителя и глубину и сразу входим в него. После проверки четырёх направлений снимаем кадр и возвращаемся к родителю. Возврат не считается новым обнаружением или активацией.

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

Останавливаемся при первом входе в T. Уровень означает глубину в дереве DFS и в общем случае не равен кратчайшему расстоянию. В сгенерированном дереве единственный простой путь оказывается кратчайшим; при наличии циклов DFS может выбрать более длинный. А цель, близкую по порядку его обхода, он иногда достигает раньше, чем BFS закончит расширять волну.

Восстанавливаем маршрут по родителям

При первом обнаружении запоминаем клетку, из которой пришли. Когда T стала текущей, переходим к parent[T], затем к родителю родителя, пока не достигнем S. Ссылки ведут к более ранним обнаружениям, поэтому цикл из родителей невозможен. Разворачиваем собранные клетки, чтобы показать маршрут от S к T.

Анимация добавляет клетки пути от T назад к S; завершённый маршрут представлен в обратном порядке. Длина — число переходов: path.length − 1, а не число клеток. При S = T маршрут равен [S], длина — ноль. Если фронт исчерпан без достижения T, результат — «Пути нет», пустой маршрут и длина null. Пока анимация ещё идёт, отсутствие найденного пути не доказывает недостижимость.

7 × 5, seed 2: маршрут одинаковый, работа разная

При S = (1, 1) и T = (7, 5) генератор посещает 35 клеток, открывает 34 прохода и проверяет 140 направлений; максимум стека генерации — 29 кадров. Это результат полного построения, а не поиска, остановленного на T.

Оба поиска восстанавливают id 0 → 1 → 2 → 9 → 10 → 3 → 4 → 11 → 12 → 13 → 20 → 27 → 34: 13 клеток, 12 переходов. При этом DFS возвращается и из других веток; пройденная в анимации траектория не равна итоговому маршруту. В данном примере оба метода обнаруживают 15 клеток, но проверяют разное число направлений.

Что именно считают счётчики

Обнаружение — первая отметка клетки, включая S. Активация — первый переход обнаруженной клетки в текущую. В момент нахождения цели часть клеток может ещё ждать в очереди BFS, поэтому числа обнаружений и активаций не обязаны совпадать. Восстановление маршрута не меняет эти счётчики.

Проверка направления учитывает и внешнюю границу, и закрытую стену, и уже обнаруженного соседа. У полностью обработанной клетки четыре проверки. Полный генератор делает ровно 4N проверок; поиск может завершиться раньше. Очередь BFS содержит ожидающие клетки без текущей; стек DFS — кадры вместе с текущей клеткой.

Таблица сравнения имеет смысл только при одинаковых стенах, концах пути и порядке соседей. Пик очереди и пик стека описывают разные структуры, а не всю память программы. Длительность анимации зависит от детализации событий и выбранной скорости и не служит замером быстродействия BFS против DFS.

Загрузите цикл, чтобы увидеть более длинный путь DFS

Сохраните JSON ниже в файл и нажмите «Загрузить JSON». В нём цикл 3 × 2 со стартом (1, 1) и выходом (1, 2). BFS проходит напрямую на юг: id [0, 3], один переход. DFS сначала пробует восток и находит [0, 1, 2, 5, 4, 3], пять переходов. Оба результата допустимы; только BFS гарантирует кратчайший.

Файл может описывать и несвязные области. Корректная схема сохраняет согласованность общих стен и закрытую внешнюю границу, но не обязана быть связной или ацикличной. Загрузка готовит поиск на паузе, без вымышленного построения. «Сохранить JSON» выгружает готовую топологию и выбранные концы/метод, а не промежуточный кадр прокладки проходов.

JSON

{
  "format": "grundyjs-maze", "version": 1,
  "width": 3, "height": 2,
  "walls": [9, 1, 3, 12, 4, 6],
  "start": { "column": 1, "row": 1 },
  "target": { "column": 1, "row": 2 },
  "method": "bfs"
}

JavaScript: те же правила поиска без анимации

Запустите этот блок после помощников модели. Он принимает проверенный лабиринт, допустимые id старта/цели от нуля и метод "bfs" либо "dfs". Правила обнаружения общие; оба метода останавливаются при активации T, как и плеер. cursor хранит следующее направление, parent восстанавливает маршрут, levels заодно служит отметкой обнаружения.

BFS использует массив с индексом головы вместо постоянного сдвига содержимого через shift(). Обработанные элементы остаются выделенными, хотя размер показанной очереди их исключает. DFS использует тот же массив как стек кадров. Сайт дополнительно выдаёт небольшие неизменяемые события и проверяет/копирует входы; в исполняемом учебном варианте этих слоёв нет.

JavaScript

function searchMaze(maze, start, target, method = "bfs") {
    const count = maze.walls.length;
    const parent = new Int32Array(count).fill(-1);
    const levels = new Int32Array(count).fill(-1);
    const cursor = new Uint8Array(count), frontier = [start];
    const counters = { discoveredCount: 1, activatedCount: 0,
        finishedCount: 0, directionChecks: 0, maxFrontierSize: 1 };
    let head = 0, current = -1, found = false;
    const size = () => method === "bfs" ? frontier.length - head : frontier.length;
    levels[start] = 0;
    while (current !== -1 || size() > 0) {
        if (current === -1) {
            current = method === "bfs" ? frontier[head++] : frontier[frontier.length - 1];
            counters.activatedCount++;
            if (current === target) { found = true; break; }
        }
        if (cursor[current] === 4) {
            counters.finishedCount++;
            if (method === "bfs") current = -1;
            else { frontier.pop(); current = frontier.at(-1) ?? -1; }
            continue;
        }
        const d = cursor[current]++, next = neighbor(maze, current, d);
        counters.directionChecks++;
        if (next === -1 || (maze.walls[current] & WALL[d]) || levels[next] !== -1) continue;
        parent[next] = current;
        levels[next] = levels[current] + 1;
        counters.discoveredCount++;
        frontier.push(next);
        counters.maxFrontierSize = Math.max(counters.maxFrontierSize, size());
        if (method === "dfs") current = -1;
    }
    const path = [];
    if (found) {
        for (let cell = target; cell !== -1; cell = parent[cell]) path.push(cell);
        path.reverse();
    }
    return { found, path, pathLength: found ? path.length - 1 : null,
        parent, levels, counters };
}

Запустите и сравните примеры

Скопируйте блоки модели, генерации и поиска в таком порядке в одну область JavaScript, затем выполните пример. Проверки сайта сопоставляют именно эти фрагменты статьи с настоящим ядром: стены, маршруты, уровни, родителей и счётчики.

JavaScript

// Run after the three code blocks above, in the same scope.
const generated = generateMaze(7, 5, 2);
const bfs = searchMaze(generated.topology, 0, 34, "bfs");
const dfs = searchMaze(generated.topology, 0, 34, "dfs");
console.log(bfs.pathLength, dfs.pathLength); // 12, 12

// A cyclic 3 x 2 maze: a direct edge 0-3 and a longer route around it.
const cyclic = { width: 3, height: 2, walls: [9, 1, 3, 12, 4, 6] };
console.log(searchMaze(cyclic, 0, 3, "bfs").path); // [0, 3]
console.log(searchMaze(cyclic, 0, 3, "dfs").path); // [0, 1, 2, 5, 4, 3]

Линейные алгоритмы и отдельная стоимость плеера

Пусть N = width · height, E — число открытых неориентированных проходов. У клетки не более четырёх соседей, поэтому E ≤ 2N − width − height. Генератор посещает каждую клетку один раз и проверяет четыре направления: O(N) времени. BFS и DFS работают за O(N + E), то есть здесь за O(N) в худшем случае. Инициализация массивов на всю сетку уже требует O(N), даже если цель рядом со стартом.

Все три реализации используют O(N) рабочей памяти. В стеке генератора может быть N кадров; BFS хранит отметки, родителей, расстояния и память очереди; DFS — отметки, родителей, глубины, курсоры и до N кадров. Восстановление маршрута из L переходов требует ещё O(L + 1) времени и места под результат. Эти оценки не включают сохранённую историю анимации и bitmap canvas.

Как плеер работает с большой историей

Визуализатор записывает компактные события вместо полной сетки после каждого действия. Разреженные контрольные точки и текущее рабочее состояние позволяют перематывать: восстанавливаем предшествующую точку и порциями проигрываем недостающие события. Более новый запрос отменяет старую перемотку, поэтому запоздавшая задача не подменяет последнюю выбранную позицию.

Пул истории делит лимит 32 MiB между генерацией и текущим поиском. При нехватке места удаляются дополнительные точки: перемотка может стать дольше, зато удерживаемые буферы остаются в бюджете. Это не предел памяти всей вкладки. Canvas рисует видимые клетки и переиспользует пиксели viewport при небольшом сдвиге, но полный обзор или длинная перемотка всё ещё могут быть дорогими.

Пример 7 × 5 удобен для изучения отдельных действий, большие сетки — для общей структуры. На мелком масштабе увеличьте поле, чтобы различать проходы и расстояния. При высокой скорости плеер может не показывать промежуточные кадры, сохраняя последовательное применение событий. Лабиринт и результат поиска от этого не меняются.

Источники

Основа алгоритмов: генерация с возвратами и кратчайшие пути BFS. Маски стен, правила seed, счётчики и устройство воспроизведения в разборе относятся к реализации этого сайта.

• Jamis Buck — Maze Generation: Recursive Backtracking
• Sedgewick & Wayne — BreadthFirstPaths