Keywords
square mazes
randomized algorithms
trees and graphs
optimización combinatoria
laberintos cuadrados
algoritmos aleatorizados
árboles y gráficas
How to Cite
Abstract
In this article a new method to solve square mazes using a randomized depth-first search algorithm is described. The algorithm was tested in two families of labyrinths, one of them based on the Aldous-Broder method and the other on Backtrack. The algorithm was compared against the Dijkstra method, a well-known technique to solve this kind of problems. The new method finds solutions in less time for large-size labyrinths
(greater than 100 x 100 cells).
References
D. Ashlock, C. Lee, C. McGuinness, Search-based procedural generation of maze-like levels, IEEE Transactions on Computational Intelligence and Al in Games 3 (2011), no. 3, 260-273.
J. Buck, Mazes for Programmers: Code Your Own Twisty Little Passages, The Pragmatic Bookshelf, Texas, 2015.
D. C. Dracopoulos, Robot path planning for maze navigation, 1998 IEEE International Joint Conference on Neural Networks Proceedings, Vol. 3, IEEE World Congress on Computational Intelligence, 1998.
A. S. Fraenkel, Economic traversal of labyrinths, Mathematics Magazine 43 (1970), no. 3, 125-130.
K. Hamada, A picturesque maze generation algorithm with any given endpoints, Journal of Information Processing 21 (2013), no. 3, 393-397.
G. E. Jan, K-Y. Chang, I. Parberry, A new maze routing approach for path planning of a mobile robot, 2003 IEEE/ASME International Conference on Advanced Intelligent Mechatronics, Vol. 2, The Institute of Electrical and
Electronics Engineers, Inc., Japan, 2003.
M. T. Jones, Artificial Intelligence: A Systems Approach, Infinity Science Press, USA, 2008.
W. H. Matthews, Mazes and Labyrinths: Their History and Development, Dover Publications, New York, 1970.
V. T. Tomás, M. Pozas, J. Hernández, Propuesta para la generación de laberintos ampliados en 2D, Ciencia Huasteca, UAEH, México, 2011.
Comments
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright (c) 2019 Revista de Matemática: Teoría y Aplicaciones