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?
Answer
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.