Pathfinding Algorithm For Pacman [closed]

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

Well this depends, do you actually want to make the ghosts work like they do in Pac-Man?

Here's a description of how the ghosts' chase AI works (they each work differently). Make sure to read the above Chapter too about how they actually try to get to their target tile. That page is a wonderfully in-depth analysis of Pac-Man, interesting read.

Answer 2

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.