Pathfinding Algorithm For Pacman

Question

I wanted to implement the game Pacman. For the AI, I was thinking of using the A* algorithm, having seen it on numerous forums. However, I implemented the Breadth First Search for some simple pathfinding (going from point a to point b with certain obstacles in between) and found it gave the optimum path always. I guess it might be because in a game like pacman which uses simple pathfinding, there is no notion of costs in the graph. So, will it be OK if I use BFS instead of A* for pathfinding in Pacman?

Answer 1

For path-finding, note the following

• BFS will look at a lot more nodes than A* will, which makes it much slower
• A* will come up with the same answer as BFS
• A* is really easy to implement
  • Use Manhattan Distance as your heuristic - this is insanely easy to implement, and leads to very efficient searches
  • Look at http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html for more information (the entire series is really interesting)

If you're talking about the ghost AI, check out the page Chad mentioned: The Pac-Man Dossier - the ghosts actually just use the euclidean distance when determining how to make it to their target tiles, which makes them very bad at finding Pac Man in some cases.