Pathfinding Algorithm For Pacman

Question

Hi, 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

BFS will always give the shortest path if no edge weights are used. If you have no need for edge weights, I would use that. You can always switch later.

Answer 2

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 3

Related question, which probably answers your question: Path finding in a Java 2d Game?

Answer 4

It depends. BFS is both complete and optimal (in the sense it finds the optimal solution)

The downside? It may take a long, long, LONG time to find it! Also, depending on the ramification factor of your problem you may run out of memory fast.

If you have no performance issues, then keep BFS, but if you want to try it in a huge maze then it may take a while to get the solution.

I suggest you try A*, the best search strategy IMHO. Even if you are not having problems with BFS, A* is a nice algorithm to implement, and you will learn a lot of cool stuff.

Answer 5

You may want to consider the anti-object approach that the original designers of Pacman used, you can read about it here and here.

However, to answer your question, use what works! If you are getting good results from BFS, use it. Just remember to abstract the pathfinding enough that you can replace it later if you find something better.

Good luck!

Answer 6

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.

If you really want to go whole-hog, check out the commented Z80 disassembly: http://www.lomont.org/Software/Games/PacMan/PacmanASM.html