Генератор лабиринтов по алгоритму Крускала

Опубликовано: 16 февраля 2025 г. в 18:00:10 UTC
Последнее обновление: 12 января 2026 г. в 08:59:22 UTC

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

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

Kruskal's Algorithm Maze Generator

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

Идеальный лабиринт - это лабиринт, в котором есть ровно один путь из любой точки лабиринта в любую другую точку. Это значит, что вы не сможете ходить по кругу, но часто будете сталкиваться с тупиками, вынужденными разворачиваться и идти обратно.

Созданные здесь карты лабиринтов включают в себя версию по умолчанию без стартовых и финишных позиций, так что вы можете решить их сами: из любой точки лабиринта в любую другую найдется решение. Если вам нужно вдохновение, вы можете включить предлагаемые стартовую и финишную позиции - и даже увидеть решение между ними.

Об алгоритме Крускала

Алгоритм Крускала был создан Джозефом Бернардом Крускалом-младшим, американским математиком, статистиком и специалистом по информатике. Впервые он описал этот алгоритм в 1956 году в своей статье «О кратчайшем остовном поддереве графа и задаче коммивояжера».

Алгоритм предназначен для поиска минимального остовного дерева (МОСТ) графа, обеспечивающего соединение всех вершин с минимально возможным суммарным весом ребер и избегающего циклов.

Как работает алгоритм Крускала для генерации лабиринтов

Шаг 1: Инициализация

Рассматривайте каждую клетку в лабиринте как отдельный набор (уникальный компонент).
Перечислите все стенки между соседними ячейками как потенциальные ребра.

Шаг 2: Сортировка стен

Перемешайте или упорядочите стены случайным образом. Если вы реализуете алгоритм как настоящий алгоритм Крускала, отсортируйте стены в случайном порядке (поскольку для генерации лабиринта не требуются веса).

Шаг 3: Технологические стенки

Пройдитесь по перемешанным стенам.
Если две клетки, разделённые стенкой, принадлежат к разным множествам (то есть, они ещё не соединены в лабиринте), удалите стенку и объедините множества.
Если они уже находятся в одном наборе, пропустите стену (чтобы избежать циклов).

Шаг 4: Продолжайте до завершения.

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

Поскольку алгоритм Крускала основан на слиянии множеств, его можно оптимизировать с помощью алгоритма Union-Find, который обеспечивает эффективный способ отслеживания связанных ячеек при построении лабиринта. Мою реализацию алгоритма Union-Find на PHP можно посмотреть здесь: Ссылка

Дополнительное чтение

Если вам понравился этот пост, вам также могут понравиться эти предложения:

Создайте новый лабиринт

Об алгоритме Крускала

Как работает алгоритм Крускала для генерации лабиринтов

Дополнительное чтение