Randomized Pacman maze generation algorithm

Kwan Man Cheng; Hongfan Liu; Xinyu Dou

doi:10.54254/2755-2721/42/20230771

Research Article

Open access

Published on 23 February 2024

Download pdf

Cheng,K.M.;Liu,H.;Dou,X. (2024). Randomized Pacman maze generation algorithm. Applied and Computational Engineering,42,156-162.

Export citation

Randomized Pacman maze generation algorithm

Kwan Man Cheng *^,1, Hongfan Liu ², Xinyu Dou ³

¹ Beijing Normal University
² Zhejiang University
³ Pennsylvania State University

* Author to whom correspondence should be addressed.

https://doi.org/10.54254/2755-2721/42/20230771

Abstract

Pacman, a cultural icon since its debut in 1980, is celebrated for its captivating static maze design. This research explores innovative algorithms, including an improved version of Sidewinder, in the context of dynamic maze generation for Pacman. Traditional algorithms, constituting the initial focus, serve as counterexamples to highlight their unsuitability in creating Pacman mazes due to their generic design unrelated to the game's unique gameplay. By showcasing these limitations, the study emphasizes the necessity for tailored solutions that align with Pacman's dynamic environment. Subsequently, attention shifts to an innovative algorithm exhibiting promise for Pacman maze generation. An in-depth analysis, using the same rigorous criteria applied to traditional algorithms provides essential insights into its potential for enhancing the Pacman gaming experience.

Keywords

Pacman, Maze generation algorithms, Sidewinder

View pdf

References

[1]. Lowood, H. E. (2004). Pac-Man. Encyclopedia Britannica. https://www.britannica.com/topic/Pac-Man-1688279

[2]. Kent, Steve L. 2001. The Golden Age (Part I: 1979-1980). The Ultimate History of Video Games. New York, Three Rivers Press. PP. 141-143

[3]. M. Gallagher, A. Ryan. (2003) "Learning to play Pac-Man: an evolutionary, rule-based approach," In: The 2003 Congress on Evolutionary Computation. Canberra, ACT, Australia, 2003, pp. 2462-2469 Vol.4

[4]. Liapis, A., Yannakakis, G. N., & Togelius, J. (2013). Sentient sketchbook: Computer-aided game level authoring. In Proceedings of the International Conference on Foundations of Digital Games (FDG) (pp. 213-220)

[5]. Hendrikx, M., Meijer, S., Van Der Velden, J., & Iosup, A. (2013). Procedural content generation for games: A survey. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 9(1), 1-22.

[6]. Safak, A., Bostanci, G. E., & Soylucicek, A. (2016). Automated Maze Generation for Ms. Pac-Man Using Genetic Algorithms. International Journal of Machine Learning and Computing, 6, 226-230. doi: 10.18178/ijmlc.2016.6.4.602.

[7]. Karlsson, A. (2018). Evaluation of the Complexity of Procedurally Generated Maze Algorithms (Dissertation). https://urn.kb.se/resolve?urn=urn:nbn:se:bth-16839

[8]. Gabrovšek, P. (2019). Analysis of maze generating algorithms. IPSI Transactions on Internet Research. http://ipsitransactions.org/journals/papers/tir/2019jan/p5.pdf

[9]. Buck, J. (2015). Mazes for Programmers: Code Your Own Twisty Little Passages. Pragmatic Bookshelf.

[10]. Kwiecień, J. (2018). A Swarm-Based Approach to Generate Challenging Mazes. Entropy, 20(10), 762.

Cite this article

Cheng,K.M.;Liu,H.;Dou,X. (2024). Randomized Pacman maze generation algorithm. Applied and Computational Engineering,42,156-162.

Data availability

The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.

Disclaimer/Publisher's Note

The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

About volume

Volume title: Proceedings of the 2023 International Conference on Machine Learning and Automation

Conference website: https://2023.confmla.org/

ISBN：978-1-83558-309-8(Print) / 978-1-83558-310-4(Online)

Conference date: 18 October 2023

Editor：Mustafa İSTANBULLU

Series: Applied and Computational Engineering

Volume number: Vol.42

ISSN：2755-2721(Print) / 2755-273X(Online)

© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series'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 series.
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 Open access policy for details).