Pathfinding Algorithm For Pacman

path-finding pacman
Karan picture Karan · Apr 9, 2010 · Viewed 32.6k times · Source

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

Chad Birch picture Chad Birch · Apr 9, 2010

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.

Related questions

PacMan: what kinds of heuristics are mainly used?

Beside A*, BFS, DFS and the like, what are other good path-finding algorithms/heuristics popularly used in Pacman? I don't think the ones I mentioned will work if there're more than one fruits for pacman to find. I need some …

Read More
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 …

Read More
Difference and advantages between dijkstra & A star

I read this: http://en.wikipedia.org/wiki/A*_search_algorithm It says A* is faster than using dijkstra and uses best-first-search to speed things up. If I need the algorithm to run in milliseconds, when does A* become the …

Read More