Algorithmic Diversity in Maze Generation Comparative Study of Backtracking, Kruskal's, Prim's, and Eller's Algorithms
Keywords:
Backtracking Algorithm, Eller’s Algorithm, Kruskal’s Algorithm, Maze, Prim’s AlgorithmAbstract
The creation of content using Procedural Content Generation or PCG is a common occurrence in game development. The utilization of PCG can reduce game development costs and provide players with unique gaming experiences in each session. Among the various existing PCG algorithms, each algorithm generates content with different levels of complexity. This research aims to compare maps generated by the Backtracking Algorithm, Kruskal’s Algorithm, Prim’s Algorithm, and Eller’s Algorithm. Each algorithm will create maze maps of sizes 5x5, 10x10, and 15x15, and their completion times will be measured using the A-Star maze-solver algorithm. Based on the results of this study, mazes created by the Backtracking algorithm are the most complex, with an average completion time of 2.3803 seconds, which is 14.82% longer than the mazes generated by the Eller algorithm. The mazes created by the Eller algorithm come in second as the most complex, with an average completion time of 2.0729 seconds, which is 4.27% longer than those generated by the Kruskal algorithm. The mazes created by the Kruskal algorithm rank third in complexity, with an average completion time of 1.988 seconds, which is 31.84% longer than the ones generated by the Prim algorithm. Lastly, the mazes created by the Prim algorithm are the least complex, with an average completion time of 1.5078 seconds.
Downloads
References
I. S.-E. Otobe, “Innovations in the video game industry,” Innov. Syst. Process. Asia, no. 94, pp. 1–34, 2007, [Online]. Available: http://asia.stanford.edu/events/fall07/slides/otobe.pdf
M.-P. Määttä, “Growth and Future of Video Game Industry,” in Proceedings of the 2022 International Conference on Economics, Smart Finance and Contemporary Trade, 2019, p. 31. doi: 10.2991/978-94-6463-052-7_9.
B. Chaarani, J. Ortigara, D. Yuan, H. Loso, A. Potter, and H. P. Garavan, “Association of Video Gaming with Cognitive Performance among Children,” JAMA Netw. Open, vol. 5, no. 10, p. E2235721, 2022, doi: 10.1001/jamanetworkopen.2022.35721.
C. S. Green and D. Bavelier, “Action video game training for cognitive enhancement,” Curr. Opin. Behav. Sci., vol. 4, pp. 103–108, 2015, doi: 10.1016/j.cobeha.2015.04.012.
I. Granic, A. Lobel, and R. C. M. E. Engels, “The benefits of playing video games,” Am. Psychol., vol. 69, no. 1, pp. 66–78, 2014, doi: 10.1037/a0034857.
M. Beukman, C. W. Cleghorn, and S. James, “Procedural content generation using neuroevolution and novelty search for diverse video game levels,” GECCO 2022 - Proc. 2022 Genet. Evol. Comput. Conf., pp. 1028–1037, 2022, doi: 10.1145/3512290.3528701.
J. Togelius et al., “Procedural Content Generation : Goals, Challenges and Actionable Steps,” Artif. Comput. Intell. Games, vol. 6, pp. 61–75, 2013, [Online]. Available: http://drops.dagstuhl.de/opus/volltexte/2013/4351%5Cnhttp://drops.dagstuhl.de/opus/volltexte/2013/4336/
A. Chia, “The artist and the automaton in digital game production,” Convergence, vol. 28, no. 2, pp. 389–412, 2022, doi: 10.1177/13548565221076434.
B. A. Hassan and T. A. Rashid, “Operational framework for recent advances in backtracking search optimisation algorithm: A systematic review and performance evaluation,” Appl. Math. Comput., vol. 370, 2020, doi: 10.1016/j.amc.2019.124919.
F. Rossi, P. van Beek, and T. Walsh, “Handbook of Constraint Programming Introduction,” Handb. Constraint Program., pp. 1–955, 2006.
D. C. Schmidt and L. E. Druffel, “A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices,” J. ACM, vol. 23, no. 3, pp. 433–445, 1976, doi: 10.1145/321958.321963.
G. Kondrak and P. Van Beek, “A theoretical evaluation of selected backtracking algorithms,” Artif. Intell., vol. 89, no. 1–2, pp. 365–387, 1997, doi: 10.1016/s0004-3702(96)00027-6.
H. Li, Q. Xia, and Y. Wang, “Research and Improvement of Kruskal Algorithm,” J. Comput. Commun., vol. 05, no. 12, pp. 63–69, 2017, doi: 10.4236/jcc.2017.512007.
S. Marković, J. Novakovic, and A. Marković, “Generating and solving of the maze by using Kruskal’s and Floyd’s algorithm,” Int. Sci. Conf. “UNITECH 2019” – Gabrovo, no. November, pp. 315–319, 2019.
D. Jakus, R. Čađenović, J. Vasilj, and P. Sarajčev, “Optimal reconfiguration of distribution networks using hybrid heuristic-genetic algorithm,” Energies, vol. 13, no. 7, 2020, doi: 10.3390/en13071544.
Wamiliana, M. Usman, Warsono, Warsito, and J. I. Daoud, “Using modification of Prim’s algorithm and GNU Octave and to solve the multiperiods installation problem,” IIUM Eng. J., vol. 21, no. 1, pp. 100–112, 2020, doi: 10.31436/iiumej.v21i1.1088.
M. Iqbal, A. P. U. Siahaan, N. Elizabeth, and D. Purwanto, “Prim’s Algorithm for Optimizing Fiber Optic Trajectory Planning,” Int. J. Sci. Res. Sci. Technol., vol. 3, no. September, pp. 504–509, 2017, [Online]. Available: https://www.researchgate.net/publication/319349574
C. Science, “Fundamentals of Maze Generation,” Fundam. Program. Comput. Sci., pp. 1–6.
P. A. Newell, J. Aycock, and K. M. Biittner, “Still Entombed After All These Years: The continuing twists and turns of a maze game,” Internet Archaeol., no. 60, 2022, doi: 10.11141/ia.59.3.
O. R. Chandra and W. Istiono, “A-star Optimization with Heap-sort Algorithm on NPC Character,” Indian J. Sci. Technol., vol. 15, no. 35, pp. 1722–1731, 2022, doi: 10.17485/ijst/v15i35.857.
G. T. Kumala and W. Istiono, “Comparison of Flow Field and A-Star Algorithm for Pathfinding in Tower Defense Game,” Int. J. Multidiscip. Res. Anal., vol. 5, no. 9, pp. 2445–2453, 2022, doi: 10.47191/ijmra/v5-i9-20.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
