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, is it really necessary to use A* for pathfinding in Pacman, or can we do it just by using BFS?

**0**

7 replies to this topic

Sponsor:

###
#2
Members - Reputation: **136**

Posted 08 April 2010 - 05:03 PM

Pac-Man doesn't use A*. The basic algorithm is:

And then there are many more details that make the ghost behavior varied and unpredictable.

http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter 3

If you are on an intersection:

get a vector from ghost to target (usually pac-man)

select direction most similar to that vector

(for example if the vector is (-3, 4) you do max(abs(-3), abs(4)) = 4

which is the Y coordinate, so we would go in the positive-y direction

(up or down depending on your coordinate system))

while that direction isn't available (blocked by wall)

select other direction, in the following order of preference: up, left, down, right

And then there are many more details that make the ghost behavior varied and unpredictable.

http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter 3

###
#6
Crossbones+ - Reputation: **3178**

Posted 13 April 2010 - 08:54 PM

Anything that the player can predict and plan for is a good ghost AI.

For example: walk continuously following tunnel bends, turn up to 90 degrees towards Pacman at every fork (going straight or right in case of ties), turn back whenever you have LOS to Pacman behind you.

Or: walk to the adjacent open square that is closest to Pacman (straight line, not actual walking distance) if it is closer than the current one, otherwise stand still without dithering. (Dumb but still dangerous)

Or: chase Pacman whenever you have LOS and go back to a predetermined patrol route when you don't. For example you could compute shortest paths between all pairs of open squares in the map, and select a few squares crossed by the greatest number of paths as chokepoints to visit.

For example: walk continuously following tunnel bends, turn up to 90 degrees towards Pacman at every fork (going straight or right in case of ties), turn back whenever you have LOS to Pacman behind you.

Or: walk to the adjacent open square that is closest to Pacman (straight line, not actual walking distance) if it is closer than the current one, otherwise stand still without dithering. (Dumb but still dangerous)

Or: chase Pacman whenever you have LOS and go back to a predetermined patrol route when you don't. For example you could compute shortest paths between all pairs of open squares in the map, and select a few squares crossed by the greatest number of paths as chokepoints to visit.

###
#7
Members - Reputation: **220**

Posted 14 April 2010 - 03:02 AM

I did a pacman AI a couple of years ago. With discreet levels that short, its very easy to use Dijkstra to build a "shortest path matrix", i.e. a matrix M where M(i,j) contains the next node you have to go in the shortest path between i and j. Compute this matrix when you save the map and voila! O(1) complete and optimal pathfinding.

###
#8
Members - Reputation: **977**

Posted 14 April 2010 - 12:14 PM

Quote:

Original post by Steadtler

I did a pacman AI a couple of years ago. With discreet levels that short, its very easy to use Dijkstra to build a "shortest path matrix", i.e. a matrix M where M(i,j) contains the next node you have to go in the shortest path between i and j. Compute this matrix when you save the map and voila! O(1) complete and optimal pathfinding.

As a side note, the Bellman Ford algorithm has the same asymptotic time complexity as calling Dijkstra over and over in a loop like this, but is overall much simpler, so if GP wants to do this and doesn't have some Dijkstra code sitting around, it'd probably be easier to implement Bellman-Ford. Plus, since it's simpler, even though the asymptotic complexity is the same, the constants are probably better. The memory complexity is a little better too, I suppose, since you don't need a separate queue; you just need the matrix. Not that this small benefit really matters for an algorithm that performs a stored precomputation anyway.