Материал: АиСД. Проектная работа

Федеральное агентство связи

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет телекоммуникаций

им. проф. М. А. Бонч-Бруевича»

ГЕНЕРАЦИЯ И ПОИСК КРАТЧАЙШЕГО ПУТИ В 2D ЛАБИРИНТАХ

Проектная работа по дисциплине «Алгоритмы и структуры данных»

Студенты: Коваленко Л. А. Курс: 2 Группа: ИКПИ-81 Преподаватель: Дагаев А. В.

Санкт-Петербург

2020

2

1.ГЕНЕРАЦИЯ ЛАБИРИНТОВ

1.1Алгоритмы генерации идеальных лабиринтов

Идеальный лабиринт – такой лабиринт, в котором одна клетка связана с другой одним единственным путём. Иначе говоря, остовное дерево.

Для создания стандартного идеального лабиринта обычно необходимо «выращивать» его, обеспечив отсутствие петель и изолированных областей.

Следующие алгоритмы генерируют идеальные лабиринты либо методом добавления стен, либо методом вырезания проходов.

Таблица 1. Алгоритмы генерации идеальных лабиринтов

3

Решение. Это процент ячеек лабиринта, по которым проходит его решение для типичного лабиринта, создаваемого алгоритмом. Здесь предполагается, что лабиринт состоит из 100×100 проходов, а начало и конец находятся в противоположных углах. Этот параметр является показателем «извилистости» пути решения. Максимальную извилистость имеют одномаршрутные лабиринты, потому что решение проходит по всему лабиринту. Минимально возможную извилистость имеет двоичное дерево, у которого решение просто пересекает лабиринт и никогда не отклоняется и не приостанавливает движение по направлению к концу. Обычно генерация добавлением стен имеет те же свойства, что и вырезание проходов, но если значения сильно отличаются, то в скобках указывается процент в случае добавления стен.

Тупики. Это приблизительный процент ячеек, являющихся тупиками в лабиринте. Обычно при добавлении стен процент такой же, как и при вырезании проходов, но если они значительно отличаются, то в скобках указан процент при добавлении стен. Значение для алгоритма выращивания дерева на самом деле варьируется от 10% (если всегда выбирается самая новая ячейка) до 49% (если всегда выбирается самая старая ячейка). При достаточно высоком показателе проходов количество тупиков Recursive Backtracking может становиться ниже 1%. Наибольший вероятный процент тупиков в двухмерном ортогональном идеальном лабиринте равен 66% — это одномаршрутный проход с кучей тупиков единичной длины по обеим сторонам от него.

Тип. Существует два типа алгоритмов создания идеальных лабиринтов:

•Алгоритм на основе дерева выращивает лабиринт подобно дереву, всегда добавляя к тому, что уже есть, и на каждом этапе имея правильный идеальный лабиринт.

•Алгоритм на основе множеств выполняет построения там, где ему хочется, отслеживая части лабиринта, соединённые друг с другом, чтобы соединить всё и создать правильный лабиринт на момент завершения.

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

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

Однородность. Генерирует ли алгоритм все возможные лабиринты с равной вероятностью. «Да» означает, что алгоритм полностью однороден. «Нет» означает, что

4

алгоритм потенциально может генерировать все возможные лабиринты в пределах любого пространства, но не с равной вероятностью. «Никогда» означает, что существуют возможные лабиринты, которые алгоритм никогда не сможет сгенерировать. Учтите, что только алгоритмы с полным отсутствием смещенности могут быть полностью однородными.

Память. Объём дополнительной памяти или стека, необходимый для реализации алгоритма. Эффективные алгоритмы требуют только битовой карты самого лабиринта, в то время как другие требуют объёма памяти, пропорционального одной строке (N), или пропорционального количеству ячеек (N2). Некоторым алгоритмам даже не нужно иметь в памяти весь лабиринт, и они могут добавлять части лабиринта бесконечно (такие алгоритмы помечены звёздочкой). Алгоритму Эллера нужен объём памяти для хранения строки, но большего ему не требуется, потому что достаточно хранить только одну строку лабиринта. Алгоритму Sidewinder тоже нужно хранить только одну строку лабиринта, в то время как двоичному дереву нужно отслеживать только текущую ячейку. Для рекурсивного деления требуется стек объёмом вплоть до размера строки, но ему не нужно смотреть на битовую карту лабиринта.

5