Formation of Non-Perfect Maze Using Prim’s Algorithm

Mahyus Ihsan; Fahrul Razi; Ikhsan Maulidi; Vina Apriliani; Zahnur Zahnur

doi:10.31764/jtam.v7i2.12772

Formation of Non-Perfect Maze Using Prim’s Algorithm

Mahyus Ihsan, Fahrul Razi, Ikhsan Maulidi, Vina Apriliani, Zahnur Zahnur

Abstract

Maze is a place that has many paths with tortuous paths that are misleading and full of dead ends and can be viewed as a grid graph. A non-perfect maze is a maze that has a cycle. This research produces an algorithm that can form a non-perfect maze with a size of m×n which has two types of bias. The first bias is the composition of the percentage of horizontal and vertical partitions. The second bias is the percentage of the number of cycles. The algorithm created in this study was generated by modifying Prim’s algorithm and the use of Fisher-Yates algorithm which is used in random selection in Prim’s algorithm. The non-perfect maze algorithm begins with the calculation of the parameter values of the two types of bias and continues with forming a perfect maze and ends with forming a non-perfect maze. The algorithm that has been designed can form a non-perfect maze with a complexity of O(|E|^2), where E is the set of edges of an m×n grid graph. Flash-based application development is also carried out in order to implement algorithms to obtain a non-perfect maze. The non-perfect maze is produced in a two-dimensional visual form in the form of an image along with its corresponding grid graph. The application is capable of displaying up to the first 20 solutions of the biased maze.

Keywords

Maze; Non-perfect maze; Prim’s algorithm; Grid graph.

Full Text:

PDF

References

Baddeley, A. (2012). Working memory: theories, models, and controversies. Annual Review of Psychology, 63(2012), 1–29. https://doi.org/10.1146/annurev-psych-120710-100422

Brooks, S. (2016). Tradigital Animate CC: 12 Principles of Animation in Adobe Animate. CRC Press.

Chatterjee, A., & Kiao, U. (2021). Time Complexity Analysis. OpenGenus.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT Press.

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

Fitzgerald, R. E., 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

Foulds, L. R. (2012). Graph Theory Applications. Springer Science & Business Media.

Galbiati, G. (2003). On finding cycle bases and fundamental cycle bases with a shortest maximal cycle. Information Processing Letters, 88(4), 155–159. https://doi.org/10.1016/j.ipl.2003.07.003

Groner, L. (2016). Learning JavaScript Data Structures and Algorithms. Packt Publishing Ltd.

Hart, J. (2008). The Art of the Storyboard Second Edition. Elsevier.

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

Hoetama, D. O., Putri, F. P., & Winarno, P. M. (2018). Algoritma Fisher-Yates Shuffle dan flood fill sebagai maze generator pada game labirin. Ultima Computing: Jurnal Sistem Komputer, 10(2), 59–64. https://doi.org/10.31937/sk.v10i2.1064

Hutama, D. R., Santosa, R. G., & Karel, J. (2014). Implementasi algoritma Prim sebagai creator jalur permainan maze. Jurnal Informatika, 9(2), 147–155.

Ihsan, M., Suhaimi, D., Ramli, M., Yuni, S. M., & Maulidi, I. (2021). Non-perfect maze generation using Kruskal algorithm. Jurnal Natural, 21(1), 35–45. https://doi.org/10.24815/jn.v21i1.18840

Jonasson, A., & Westerlind, S. (2016). Genetic algorithms in mazes: a comparative study of the performance for solving mazes between genetic algorithms, BFS and DFS.

Kavitha, T., Liebchen, C., Mehlhorn, K., Michail, D., Rizzi, R., Ueckerdt, T., & Zweig, K. A. (2009). Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review, 3(4), 199–243. https://doi.org/10.1016/j.cosrev.2009.08.001

Kung, D. (2013). Object-oriented Software Engineering. McGraw-Hill Higher Education.

Miller, T. (2019). Explanation in artificial intelligence: insights from the social sciences. Artificial Intelligence, 267(2019), 1–38. https://doi.org/10.1016/j.artint.2018.07.007

Nugroho, D. A., Harmastuti, H., & Uminingsih, U. (2017). Membangun game edukasi “mathematic maze” berbasis android untuk meningkatkan kemampuan berhitung pada anak sekolah dasar. Jurnal Statistika Industri Dan Komputasi, 2(1), 67–77. https://doi.org/10.34151/statistika.v2i01.1101

Rosenzweig, G. (2013). ActionScript 3.0 Game Programming University. Pearson Education India.

Roy, S., Das, S. K., & Kamal, A. H. M. (2022). A multi-path based embedding scheme at perfect maze. Indian Journal of Computer Science, 7(1). https://doi.org/10.17010/ijcs/2022/v7/i1/168954

Subaeki, B., & Ardiansyah, D. (2017). Implementasi algoritma Fisher-Yates Shuffle pada aplikasi multimedia interaktif untuk pembelajaran tenses bahasa inggris. Infotronik: Jurnal Teknologi Informasi Dan Elektronika, 2(1), 67–74. https://doi.org/10.32897/infotronik.2017.2.1.31

Ullah, Z., Chen, X., Gou, S., Xu, Y., & Salam, M. (2022). FNUG: imperfect mazes traversal based on detecting and following the nearest-to-final-goal and unvisited gaps. IEEE Robotics and Automation Letters, 7(2), 5175–5182. https://doi.org/10.1109/LRA.2022.3151393

DOI: https://doi.org/10.31764/jtam.v7i2.12772