Combining Search-Based and Evolutionary Techniques for Autonomous Pac-Man Gameplay
Main Article Content
Abstract
Artificial intelligence has become a fundamental component in modern video game development, especially in the creation of autonomous and adaptive non-player character (NPC) behavior. This research proposes a hybrid artificial intelligence approach to enable fully autonomous gameplay in a classic Pac-Man environment without any form of user input. The proposed system combines evolutionary optimization methods with deterministic search algorithms to balance strategic planning and real-time decision-making. A Genetic Algorithm (GA) is utilized to optimize long-term gameplay strategies, including route selection and risk management, while A* pathfinding and adversarial search techniques are applied to support efficient real-time movement and enemy avoidance. Additionally, Breadth-First Search (BFS) and Depth-First Search (DFS) are implemented to model diverse ghost behaviors, resulting in a more dynamic, challenging, and adversarial game environment. Experimental evaluations indicate that the hybrid AI system demonstrates improved navigation stability, longer survival duration, and more consistent pellet collection when compared to baseline artificial intelligence models that rely on single techniques. The results further show that separating strategic optimization from tactical pathfinding enhances overall gameplay performance and adaptability. This study highlights the effectiveness of hybrid AI architectures in game environments and offers a structured educational framework for understanding and implementing artificial intelligence techniques within video game simulations, particularly for classic arcade-style games.
Article Details
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal the right of first publication. The work is simultaneously licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits others to copy, distribute, remix, adapt, and build upon the work, even commercially, provided proper attribution is given to the original authors and the journal as the source of first publication.
- Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal’s published version of the work (e.g., posting to institutional repositories, inclusion in books), with an acknowledgment of its initial publication in this journal.
- Authors are encouraged to post their work online (e.g., in institutional repositories, personal websites, or preprint servers) prior to and during the submission process. This practice can foster productive exchanges and may lead to earlier and increased citation of the published work.
User Rights:
All articles published Open Access will be immediately and permanently free for everyone to read and download. We are continuously working with our author communities to select the best choice of license options, currently being defined for this journal as follows: Creative Commons Attribution 4.0 International License.
References
[1] G. Skinner and T. Walmsley, “Artificial intelligence and deep learning in video games a brief review,” in 2019 ieee 4th international conference on computer and communication systems (icccs). IEEE, 2019, pp. 404–408.
[2] D. Ciugurean, B. Maxim, and D. Gorgan, “Impact of game ai systems on player experience.” in RoCHI, 2018, pp. 135–140.
[3] D. Setiono, D. Saputra, K. Putra, J. V. Moniaga, and A. Chowanda, “En- hancing player experience in game with affective computing,” Procedia Computer Science, vol. 179, pp. 781–788, 2021.
[4] J. DeNero and D. Klein, “Teaching introductory artificial intelligence with pac-man,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 24, no. 3, 2010, pp. 1885–1889.
[5] J. Smith and S. Cayzer, “Learning through programming games: Teach- ing ai with pac-man and netlogo.”
[6] J. Lewis, “Playing tetris with genetic algorithms,” in CS229 Machine Learning Final Project, 2015, pp. 1–10.
[7] Y. Li, D. Dong, and X. Guo, “Mobile robot path planning based on improved genetic algorithm with a-star heuristic method,” in 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference (ITAIC), vol. 9. IEEE, 2020, pp. 1306–1311.
[8] B. Geisler, “Integrated machine learning for behavior modeling in video games,” in Challenges in game artificial intelligence: papers from the 2004 AAAI workshop. AAAI Press, Menlo Park, 2004, pp. 54–62.
[9] S. Mirjalili and S. Mirjalili, “Genetic algorithm,” Evolutionary algo- rithms and neural networks: theory and applications, pp. 43–55, 2019.
[10] A. Candra, M. A. Budiman, and R. I. Pohan, “Application of a-star algorithm on pathfinding game,” in Journal of Physics: Conference Series, vol. 1898, no. 1. IOP Publishing, 2021, p. 012047.
[11] M. Stanescu, N. Barriga, and M. Buro, “Hierarchical adversarial search applied to real-time strategy games,” in Proceedings of the AAAI Con- ference on Artificial Intelligence and Interactive Digital Entertainment, vol. 10, no. 1, 2014, pp. 66–72.
[12] A. Rafiq, T. A. A. Kadir, and S. N. Ihsan, “Pathfinding algorithms in game development,” in IOP Conference Series: Materials Science and Engineering, vol. 769, no. 1. IOP Publishing, 2020, p. 012021.
[13] S. Ito, Z. Guo, C. Y. Chu, T. Harada, and R. Thawonmas, “Efficient implementation of breadth first search for general video game playing,” in 2016 IEEE 5th Global Conference on Consumer Electronics. IEEE, 2016, pp. 1–2.
[14] Y. Bjo¨rnsson, “Selective depth-first game-tree search,” 2002.
[15] J. Liu, B. Xi, S. Chen, F. Gao, Z. Wang, and Y. Long, “The path planning study of autonomous patrol robot based on modified astar algorithm and genetic algorithm,” in 2022 34th Chinese Control and Decision Conference (CCDC). IEEE, 2022, pp. 4713–4718.
[16] C. Allsman, “Pacman ai,” https://chris-allsman.github.io/projects/ pacman-ai, 2017.
[17] H. L. Manteco´n, J. S. Cremades, J. M. T. Garrigo´s, J. V. Luna, C. C. Ru¨ckauer, and A. A. Sa´nchez-Ruiz, “A pac-man bot based on grammatical evolution.” in CoSECivi, 2017, pp. 118–130.
[18] L. Haldurai, T. Madhubala, and R. Rajalakshmi, “A study on genetic algorithm and its applications,” Int. J. Comput. Sci. Eng, vol. 4, no. 10, pp. 139–143, 2016.
[19] N. Salem, H. Haneya, H. Balbaid, and M. Asrar, “Exploring the maze: A comparative study of path finding algorithms for pac-man game,” in 2024 21st Learning and Technology Conference (L&T). IEEE, 2024, pp. 92–97.
[20] L. Bottaci, “A genetic algorithm fitness function for mutation testing,” in Proceedings of the SEMINALL-workshop at the 23rd international conference on software engineering, Toronto, Canada. Citeseer, 2001.