PacMan character AI suggestions for optimal next direction

Question

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:

1. Initialize a score counter for each direction with a value of zero.
2. Start at the current position and use a BFS to traverse outward in the four possible initial directions by adding them to the queue.

3. 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:

   1. Has a dot: plus 10
   2. Has a power up: plus 50
   3. Has a fruit: plus fruit value (varies by level)
   4. Has a ghost travelling toward PacMan: subtract 200
   5. Has a ghost travelling away from PacMan: do nothing
   6. Has a ghost travelling perpendicular: subtract 50
   7. 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.

4. 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 manually cross-posted on GameDev.StackExchange

Answer 1

Have a way to change PacMan into a "path following" mode. The plan is that you detect certain circumstances, calculate a pre-drawn path for PacMan to follow, and then work out early exit conditions for that path. You can use this for several circumstances.

When PacMan is surrounded by ghosts in three of the four directions within a certain distance, then create an exit path that either leads PacMan away from the ghosts or towards a power up. The exit situation would be when he eats the power up or ceases to be surrounded.

When PacMan eats a power up, create a path to eat some nearby ghosts. The exit situation would be when there are no ghosts on the path, recalculate the path. Or if there are no ghosts nearby, exit the mode entirely.

When there are less than half the dots left, or no dots nearby, enter a path to go eat some dots, steering clear of the ghosts. Recalculate the path when a ghost comes nearby, or exit it entirely if several ghosts are nearby.

When there are no situations which warrant a path, then you can revert back to the default AI you programmed before.

Answer 2

You can use Ant Colony Optimisation techniques to find shortest visible path that leads to many icons to eat or can get many score.

Answer 3

If PacMan gets stuck in a position and starts to twitch back and forth then it suggests that the different moves open to him have very similar scores after you run your metric. Then small changes in position by the ghosts will cause the best move to flip back and forth. You might want to consider adding some hysteresis to stop this happening.

Setup: Choose a random move and record it with score 0.

For each step:

1. Run the scoring function over the available moves.
2. If the highest score is x% greater than the record score then overwrite the record score and move with this one.
3. Apply the move.

This has the effect that PacMan will no longer pick the "best" move on each step, but it doesn't seem like a greedy local search would be optimal anyway. It will make PacMan more consistent and stop the twitches.

Answer 4

I don't know a lot about AI or specific algorithms, but here are some things you could try that might just get you close enough for government work :)

For the problem with ghosts surrounding him quickly, maybe the ghost AI is too powerful? I know that there's supposedly specific behaviors for each ghost in classical Pacman, so if you haven't incorporated that, you may want to.

To eliminate backtracking, you could create an weight penalty for recently traversed nodes, so he's less inclined to go back to previous paths. If that's not enough to kick him in one direction or another, then you can logarithmically increase the attraction penalty, so one path will become significantly more attractive than the other at a very quick rate.

For the problem of him getting caught by ghosts, you might be able to change from a general goal-based algorithm to an evasive algorithm once the ghosts have reached a dangerous node proximity.

Answer 5

You might benefit of knowing how the bots "reason" (as explained in this excellent dossier). For example, knowing the chase/scatter pattern of the ghosts will allow you to get the dots in "dangerous" locations, and so on.

I am adding this answer knowing that it's not the best solution you were looking for (since you wanted to deliver next week..) but maybe will be of use to somebody reading this in the future. Sortof a time capsule :)

Answer 6

You should check out this description of Antiobjects, which is the technique used by the Pacman ghosts to traverse the maze. In particular, note:

Each of these antiobjects or agents has an identical and simple algorithm which it runs at every turn of the game. Instead of making Ghosts smart enough to solve "shortest path" problems around the maze, a notion of "Pac-Man scent" is created instead and each tile is responsible for saying how much Pac-Man scent is on its tile.

So you consider a similar scent-based technique to control Pacman, perhaps where Pacman preferred traversing a path with a smaller amount of scent; this would reduce the chance of him going over old ground.