В статье рассмотрены задачи построения лабиринта с несколькими проходами, нахождения всех проходов и возможности их редактирования. Вначале рассмотрены два алгоритма генерации лабиринтов, дающие наиболее разнообразные лабиринты на выходе, выявлены их достоинства и недостатки, выбран один наиболее эффективный и подходящий к данной задаче. Проблемой всех алгоритмов построения лабиринтов, и двух рассмотренных в том числе, является невозможность создания лабиринта с определенным количеством проходов, поэтому предложена модификация алгоритма Уилсона. Проблемой всех известных алгоритмов нахождения проходов в лабиринте является то, что ни один из них не находит абсолютно все проходы. Поэтому для нахождения всех путей разработана модификация муравьиного алгоритма. Для редактирования лабиринта разработаны два алгоритма: на основе длины путей и на основе схожести путей. Проведено исследование с целью выявить зависимость количества путей в лабиринте от начальных параметров. Для модификации муравьиного алгоритма проведен вычислительный эксперимент для выявления оптимального количества муравьев при различных входных параметрах. Кроме того, проведена оценка эффективности алгоритмов редактирования лабиринта с различными входными данными.
This article considers the problem of creating a maze with multiple solutions, searching for all solutions and a possibility of editing them. First, we view two algorithms, which generate the most various mazes, and find their positive and negative sides. Then we choose the one most efficient and suitable for the problem. All maze creation algorithms, including two considered, are unable to reveal a definite number of solutions. Here we offer a modification of Wilson’s algorithm. Still we tend to think that all maze solving algorithms cannot find all possible solutions. Therefore, we develop a modification of Ant Colony algorithm. To edit mazes the two algorithms were developed: one by solutions lengths and another by similarity of solutions. The research was conducted in order to find dependencies between number of solutions and initial parameters. A computational experiment was made to find optimal number of ants within different initial parameters. Also, there were evaluated efficiencies of two maze editing algorithms with different parameters.
The authors declare that there are no conflicts of interest present.