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

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?

Solution 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.

Solution 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.

Solution 3:

For an alternative to more traditional pathfinding algorithms, you could take a look at the (appropriately-named!) Pac-Man Scent Antiobject pattern.

You could diffuse monster-hole-scent around the maze at startup and have the eyes follow it home.

Once the smell is set up, runtime cost is very low.

Edit: sadly the wikipedia article has been deleted, so WayBack Machine to the rescue...

Solution 4:

You should take a look a pathfindings algorithm, like Dijsktra's Algorithm or A* algorithm. This is what your problem is : a graph/path problem.

Solution 5:

Any simple solution that works is maintainable, reliable and performs well enough is a good solution. It sounds to me like you have already found a good solution ...

An path-finding solution is likely to be more complicated than your current solution, and hence more likely to require debugging. It will probably also be slower.

IMO, if it ain't broken, don't fix it.

EDIT

IMO, if the maze is fixed then your current solution is good / elegant code. Don't make the mistake of equating "good" or "elegant" with "clever". Simple code can also be "good" and "elegant".

If you have configurable maze levels, then maybe you should just do the pathfinding when you initially configure the mazes. Simplest would be to get the maze designer to do it by hand. I'd only bother automating this if you have a bazillion mazes ... or users can design them.

(Aside: if the routes are configured by hand, the maze designer could make a level more interesting by using suboptimal routes ... )