Formation of Non-Perfect Maze Using Prim’s Algorithm

Authors

  • Mahyus Ihsan Department of Mathematics, Universitas Syiah Kuala, Banda Aceh Multimedia Research Group, Universitas Syiah Kuala, Banda Aceh
  • Fahrul Razi Department of Mathematics, Universitas Syiah Kuala, Banda Aceh Multimedia Research Group, Universitas Syiah Kuala, Banda Aceh
  • Ikhsan Maulidi Department of Mathematics, Universitas Syiah Kuala, Banda Aceh Multimedia Research Group, Universitas Syiah Kuala, Banda Aceh Graduate School of Natural Science and Technology, Kanazawa University, Kanazawa
  • Vina Apriliani Department of Mathematics Education, UIN Ar-Raniry, Banda Aceh
  • Zahnur Zahnur Department of Informatics, Universitas Syiah Kuala, Banda Aceh

DOI:

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

Keywords:

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

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.

 

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

Downloads

Published

2023-04-08

Issue

Vol. 7 No. 2 (2023): April

Section

Articles

License

Authors who publish articles in JTAM (Jurnal Teori dan Aplikasi Matematika) agree to the following terms:

  1. Authors retain copyright of the article and grant the journal right of first publication with the work simultaneously licensed under a CC-BY-SA or The Creative Commons Attribution–ShareAlike License.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).