Non-perfect maze generation using Kruskal algorithm



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.


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

Full Text:



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.

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.

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.

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.

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

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.

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.

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.

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.

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

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).



  • There are currently no refbacks.

Indexed and harvested by:


©2001 Jurnal Natural (JN), Indonesia, Banda Aceh: | eISSN 2541-4062 | pISSN 1411-8513 | Contact: JN site and its metadata are licensed under CC BY