1. Home
  2. Volume 21 Number 1, February 2021
  3. IHSAN

Non-perfect maze generation using Kruskal algorithm

MAHYUS IHSAN, DEDI SUHAIMI, MARWAN RAMLI, SYARIFAH MEURAH YUNI, IKHSAN MAULIDI

Abstract


A non-perfect maze is a maze that contains loop or cycle and has no isolated cell. A non-perfect maze is an alternative to obtain a maze that cannot be satisfied by perfect maze. This paper discusses non-perfect maze generation with two kind of biases, that is, horizontal and vertical wall bias and cycle bias. In this research, a maze is modeled as a graph in order to generate non-perfect maze using Kruskal algorithm modifications. The modified Kruskal algorithm used Fisher Yates algorithm to obtain a random edge sequence and disjoint set data structure to reduce process time of the algorithm. The modification mentioned above are adding edges randomly while taking account of the edge’s orientation, and by adding additional edges after spanning tree is formed. The algorithm designed in this research constructs an  non-perfect maze with complexity of  where  and  denote vertex and edge set of an  grid graph, respectively. Several biased non-perfect mazes were shown in this research by varying its dimension, wall bias and cycle bias.

Keywords


cycle bias, grid graph, Kruskal algorithm modifications, non-perfect maze, wall bias

References


Kim, P.H.; Crawfis, R. 2015. The quest for the perfect perfect-maze. 2015 Computer Games: AI, Animation, Mobile, Multimedia, Educational and Serious Games (CGAMES). (Louisville: IEEE) 65–72. https://doi.org/10.1109/CGames.2015.7272964

Haidar, A.; Fathoni, M.I.; Pu, M.; Ilham, M. 2016. Android maze game for children as an autism therapy. Scientific Journal of PPI - UKM. 3(1), 22–25.

Setiawan, W.; Hafitriani, S.; Prabawa, H.W. 2016. The scientific learning approach using multimedia-based maze game to improve learning outcomes. International Seminar on Mathematics, Science, and Computer Science Education. (Bandung: AIP Conference Proceedings) 050004. https://doi.org/10.1063/1.4941162

Fitzgerald, R..; Isler, R.; Rosenberg, E.; Oettinger, R.; Bättig, K. 1985. Maze patrolling by rats with and without food reward. Animal Learning & Behavior. 13(4), 451–462. https://doi.org/10.3758/BF03208022

Saar, M.; Gilad, T.; Kilon-Kallner, T.; Rosenfeld, A.; Subach, A.; Scharf, I. 2017. The interplay between maze complexity, colony size, learning and memory in ants while solving a maze: A test at the colony level. PLOS ONE. 12(8), 1–12. https://doi.org/10.1371/journal.pone.0183753

Jirout, J.J.; Newcombe, N.S. 2014. Mazes and Maps: Can Young Children Find Their Way? Mind, Brain, and Education. 8(2), 89–96. https://doi.org/10.1111/mbe.12048

Pentland, L.M.; Anderson, V.A.; Dye, S.; Wood, S.J. 2003. The Nine Box Maze Test: A measure of spatial memory development in children. Brain and Cognition. 52(2), 144–154. https://doi.org/10.1016/S0278-2626(03)00079-4

Chou, W. 2016. Rectangular Maze Construction by Combining Algorithms and Designed Graph Patterns. GSTF Journal on Computing. 5(1), 35–39.

Kim, J. 2019. Maze Terrain Authoring System in Immersive Virtual Reality for New Visual Realism. Symmetry. 11(4), 490. https://doi.org/10.3390/sym11040490

Foltin, M. 2011. Automated Maze Generation and Human Interaction. (Brno: Masaryk University).

Jonasson, A.; Westerlind, S. 2016. Genetic algorithms in mazes: A comparative study of the performance for solving mazes between genetic algorithms, BFS and DFS. (Stockholm: KTH Royal University).

Pickover, C.A. 1992. Mazes for the Mind: Computers and the Unexpected. (New York: St. Martin’s Press).

Dubey, P.; Sarita, K. 2016. Maze Generation & Solver. International Journal of Scientific and Technical Advancements. 2(4), 139–142.

Singh, B.; Saxena, S.; Pandey, A.; Khulbe, P. 2014. Maze Generation Using Disjoint-Sets with Stack. Journal of Basic and Applied Engineering Research. 1(6), 19–21.

Hendrawan, Y.F. 2018. A Maze Game on Android Using Growing Tree Method. Journal of Physics: Conference Series. 953(1), 012148. https://doi.org/10.1088/1742-6596/953/1/012148

Pech, A.; Hingston, P.; Masek, M.; Lam, C.P. 2015. Evolving Cellular Automata for Maze Generation. Australasian Conference on Artificial Life and Computational Intelligence. (Newcastle: Springer International Publishing) p. 112–124. https://doi.org/10.1007/978-3-319-14803-8_9

Lekova, M.; Boytchev, P. 2018. Virtual Learning Environment for Computer Graphics University Course. 12th International Technology, Education and Development Conference. (Valencia: IATED) 3301–3309. https://doi.org/10.21125/inted.2018.0633

Shah, M.S.H.; Mohite, M.J.M.; Musale, A.G.; Borade, J.L. 2017. Survey Paper on Maze Generation Algorithms for Puzzle Solving Games. International Journal of Scientific & Engineering Research. 8(2), 1064–1067.

Cormen, T.H.; E., C.; Leiserson, R.L.; Rivest; Stein, C. 2009. Introduction to Algorithms, 3 ed. (Cambridge: The MIT Press).


Full Text: PDF

DOI: 10.24815/jn.v21i1.18840

Refbacks

  • There are currently no refbacks.