Pac-Man

Pac-Man is a popular arcade game from the 1980s. The player controls Pac-Man through a maze, eating dots. Eating all the dots in a maze advances the player to the next level. Four ghosts (Blinky, Pinky, Inky, and Clyde) roam the maze trying to catch Pac-Man. If a ghost touches Pac-Man, a life is lost. Each maze has power pills that allow Pac-Man to temporarily eat the ghosts and score extra points. The game is lost when Pac-Man is out of lives.

​http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#Introduction -- This page contains some nice history and interesting facts about Pac-Man. There are also some cool videos.

​http://www.pacman-vs-ghosts.net/ -- The Ms Pac-Man vs Ghost competition. People can submit AI controllers for both Pac-Man and the ghost team. Creating your own controllers is very easy to do. Just download the software and follow the instructions on the website. Eclipse is a nice IDE for working with the code. There are sample controllers for you to look at to get started.

The attached chart shows some work I did with the controllers.

• The built in pill eating Pac-Man uses a greedy algorithm that targets the closet pill to Pac-Man.
• The built in Legacy Team ghosts each target Pac-Man with a different function.
  • Blinky: Shortest path distance
  • Inky: Euclidean distance
  • Pinky: Manhattan distance
  • Clyde: Random
• My Pac-Man uses the greedy approach but also targets edible ghosts within a certain distance and will try to avoid ghosts if they get too close.
• My ghost team targets different spots on the maze
  • Blinky: Pac-Man
  • Inky: Random power pill locations
  • Pinky: Closest pill to Pac-Man
  • Clyde: A few spaces ahead of Pac-Man

The results show that the greedy algorithm gets Pac-Man further into the game because it doesn't go out of its way to eat the ghosts but scores significantly less points because most of the scoring comes from eating ghosts. My ghost team also performed a little better than the built in ghosts because it is a little better at surrounding Pac-Man by cutting him off.

Note: The code you are given contains a shortest path finding algorithm. All you need to do is specify where in the maze you want to target and it will give you the shortest path. This is probably good enough for the ghosts but for a better Pac-Man controller, you will probably want some path costs.