What is it?
Research
Description
In this project, it is aimed to recreate the Pac-Man game using various algorithms. Pac-Man is a labyrinth arcade game developed and released by Namco. The player controls Pac-Man, who must eat all the dots in a closed maze while avoiding the four colored ghosts. It was aimed that Pac-Man factor realized within the scope of the project could find a way in the labyrinth, reach a specific location and collect food effectively. In order to realize these scenarios, certain artificial intelligence algorithms should be used. In order for Pac-Man to reach a certain fixed food source, depth first search algorithm, breadth first search algorithm and uniform cost search algorithm are planned. In addition to these algorithms, the implementation of the A * algorithm and the tests of the A * algorithm on certain special cases are planned as well.
Gallery
Conclusion
Among the four algorithms, BFS Algorithm and UCS Algorithm find the most suitable solution. However, the BFS Algorithm is expensive in terms of space as it expands the enormous number of nodes. The DFS Algorithm is space efficient but provides a long and unattractive solution. The A Star Algorithm produces a solution that is very close to the optimum length when searching heuristically, but without using excessive space. UCS Algorithm uses queue structure as priority queue and performs weight comparison. With these features, it differs from the Width Priority Search Algorithm. However, space is not efficient.