Pacman: how do the eyes find their way back to the monster hole?

Question

I found a lot of references to the AI of the ghosts in Pacman, but none of them mentioned how the eyes find their way back to the central ghost hole after a ghost is eaten by Pacman.

In my implementation I implemented a simple but awful solution. I just hard coded on every corner which direction should be taken.

Are there any better/or the best solution? Maybe a generic one that works with different level designs?

Answer 1

Actually, I'd say your approach is a pretty awesome solution, with almost zero-run time cost compared to any sort of pathfinding.

If you need it to generalise to arbitrary maps, you could use any pathfinding algorithm - breadth-first search is simple to implement, for example - and use that to calculate which directions to encode at each of the corners, before the game is run.

EDIT (11th August 2010): I was just referred to a very detailed page on the Pacman system: The Pac-Man Dossier, and since I have the accepted answer here, I felt I should update it. The article doesn't seem to cover the act of returning to the monster house explicitly but it states that the direct pathfinding in Pac-Man is a case of the following:

• continue moving towards the next intersection (although this is essentially a special case of 'when given a choice, choose the direction that doesn't involve reversing your direction, as seen in the next step);
• at the intersection, look at the adjacent exit squares, except the one you just came from;
• picking one which is nearest the goal. If more than one is equally near the goal, pick the first valid direction in this order: up, left, down, right.

Answer 2

I've solved this problem for generic levels that way: Before the level starts, I do some kind of "flood fill" from the monster hole; every tile of the maze that isn't a wall gets a number that says how far it is away from the hole. So when the eyes are on a tile with a distance of 68, they look which of the neighbouring tiles has a distance of 67; that's the way to go then.