Идеальные лабиринты на той же сетке 40×28, что и A*: рекурсивный backtracker, Уилсон, Эллер или случайный Прим; решение A* (Манхэттен, 4-соседство). Дорисовывайте стены, стирайте проходы, переносите S и G.
О модели
Страница строит идеальные лабиринты (остовное дерево на решётке комнат) на той же сетке 40×28, что и engineering/astar-dijkstra-grid. «Комнаты» — клетки с нечётными индексами (1,1)…; проходы прорубают и сами комнаты, и стенку между соседними комнатами, поэтому лабиринт связный и без циклов, пока вы не начнёте править поле. Доступны рекурсивный backtracker (стек DFS), Уилсон (случайные прогулки с стиранием петель), Эллер (слияние множеств по строкам со случайными вертикалями) и случайный Прим (рост дерева с фронтом рёбер). После генерации запускается **A* с манхэттенской эвристикой и 4-соседством** — та же дискретная модель, что и в лаборатории A*, без диагоналей и без «дорогих» клеток. Можно добавлять стены, стирать проходы и переносить S/G; при переносе концы принудительно делаются проходимыми.
Для кого: Курсы дискретной математики и CS: сравнение алгоритмов построения лабиринтов и связь с кратчайшим путём на сетке; хорошо сочетается со страницей **A* / Дейкстра**.
Ключевые понятия
Идеальный лабиринт
Остовное дерево
Рекурсивный backtracker
Алгоритм Уилсона
Алгоритм Эллера
Случайный Прим
Поиск A*
Манхэттенская эвристика
Как это работает
Идеальный лабиринт на 40×28: комнаты на нечётной решётке, проходы прорубают стенки между ними — остов без циклов. Backtracker / Уилсон / Эллер / Прим задают разные случайные деревья; затем тот же учебный A* (4-соседство, Манхэттен) ищет кратчайший путь по уже готовым стенам.
Часто задаваемые вопросы
Почему лабиринты Уилсона и Эллера «выглядят» по-разному?
Оба строят случайные остовные деревья на одной и той же решётке, но другая локальная случайность (корень Уилсона, горизонтальные решения Эллера) даёт разный рисунок при конечном размере.
Это тот же A*, что на странице A* / Дейкстра?
Те же четыре направления, манхэттенская эвристика и единичная стоимость шага по свободным клеткам. Здесь нет диагоналей, взвешенных клеток и режимов Дейкстры/жадного best-first — только учебный A*.
Можно ли нарушить «идеальность» лабиринта?
Да: ластик создаёт цикл (второй путь между областями), лишние стены могут разорвать связность. A* покажет новую топологию; при отсутствии пути до G — нет пути.