СОЗДАНИЕ ЛАБИРИНТА С НЕСКОЛЬКИМИ ПРОХОДАМИ, ПОИСК ВСЕХ ПУТЕЙ В НЕМ И ИХ РЕДАКТИРОВАНИЕ

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

1. Классические алгоритмы генерации лабиринтов. Часть 1: вступление. – URL: https://habr.com/post/320140/ .

2. Классические алгоритмы генерации лабиринтов. Часть 2: погружение в случайность. – URL: https://habr.com/post/321210/ .

3. Walter P. Maze Algorithms / P. Walter // Astrolog – URL: http://www.astrolog.org/labyrnth/algrithm.htm .

4. Штовба С. Д. Муравьиные алгоритмы / С. Д. Штовба // Exponenta Pro. – 2003. – №4. – С. 70-75.