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