• Kevin
• Preethi
• Tanmay Modh

Pac-man has been a very popular arcade game since it’s release in 1980. The goal of the game was to navigate pac-man through a maze and collect pac-dots while avoiding the four ghosts in the game. The original game used a static maze that players get used to over time, we propose to generate random mazes through the use of heuristic search techniques and apply best first search to the ghosts in order to find pac-man in the maze quickly and efficiently. Heuristic search techniques such as genetic algorithms will allow us to find optimal maze structures through a number of iterations in which the best candidates are chosen in an approach similar to that of evolution. The ghosts in this project will be using best first search, or specifically a* algorithm which uses a heuristic search function to guide the search, what makes a* better than other shortest path algorithms is its ability to cut down the size of the subgraph that must be explored, if additional information is available that provides a lower bound on the “distance” to the “target”, the target being pac-man. The game will also be designed in such a way that it’ll be cross-platform in nature i.e. it can run as a desktop,web or mobile app.

graph theory, AI

"Application of graph theory in pacman", International Journal of Emerging Technologies and Innovative Research (www.jetir.org), ISSN:2349-5162, Vol.6, Issue 4, page no.81-84, April-2019, Available :http://www.jetir.org/papers/JETIR1904I14.pdf

"Application of graph theory in pacman", International Journal of Emerging Technologies and Innovative Research (www.jetir.org | UGC and issn Approved), ISSN:2349-5162, Vol.6, Issue 4, page no. pp81-84, April-2019, Available at : http://www.jetir.org/papers/JETIR1904I14.pdf