CREATION OF MAZE WITH MULTIPLE SOLUTIONS, SEARCH FOR ALL SOLUTIONS AND EDITING THEM

UDC 519.688
DOI:10.26102/2310-6018/2019.25.2.030

E.S.Simonyan, O.A.Medvedeva, S.N.Medvedev


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.

Keywords: maze generation, Ant Colony algorithm, Wilson’s algorithm, computational experiment

Full text:
SimonyanSoavtori_2_19_1.pdf