Firstly, this is AI for PacMan and not the ghosts.
I am writing an Android live wallpaper which plays PacMan around your icons. While it supports user suggestions via screen touches, the majority of the game will be played by an AI. I am 99% done with all of the programming for the game but the AI for PacMan himself is still extremely weak. I'm looking for help in developing a good AI for determining PacMan's next direction of travel.
My initial plan was this:
- Initialize a score counter for each direction with a value of zero.
- Start at the current position and use a BFS to traverse outward in the four possible initial directions by adding them to the queue.
Pop an element off of the queue, ensure it hasn't been already "seen", ensure it is a valid board position, and add to the corresponding initial directions score a value for the current cell based on:
- Has a dot: plus 10
- Has a power up: plus 50
- Has a fruit: plus fruit value (varies by level)
- Has a ghost that is frightened: plus 200
- Has a ghost travelling toward PacMan: subtract 200
- Has a ghost travelling away from PacMan: do nothing
- Has a ghost travelling perpendicular: subtract 50
- Multiply the cell's value times a pecentage based on the number of steps to the cell, the more steps from the initial direction, the closer the value of the cell gets to zero.
and enqueue the three possible directions from the current cell.
- Once the queue is empty, find the highest score for each of the four possible initial directions and choose that.
It sounded good to me on paper but the ghosts surround PacMan extremely rapidly and he twitches back and forth in the same two or three cells until one reaches him. Adjusting the values for the ghost presence doesn't help either. My nearest dot BFS can at least get to level 2 or 3 before the game ends.
I'm looking for code, thoughts, and/or links to resources for developing a proper AI--preferably the former two. I'd like to release this on the Market sometime this weekend so I'm in a bit of a hurry. Any help is greatly appreciated.
FYI, this was originally posted on StackOverflow