• Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!

We're also offering banner ads on our site from just \$5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.

# Pathfinding Algorithm For Pacman

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

7 replies to this topic

### #1kvsingh  Members   -  Reputation: 100

Like
0Likes
Like

Posted 08 April 2010 - 11:40 AM

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?

### #2Asik  Members   -  Reputation: 136

Like
0Likes
Like

Posted 08 April 2010 - 05:03 PM

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

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

### #3Emergent  Members   -  Reputation: 971

Like
0Likes
Like

Posted 12 April 2010 - 11:33 AM

1 - The first path found by BFS is optimal so long as all edges in your graph have the same cost.

2 - A* is just a more efficient version of BFS which is guided by a heuristic.

### #4stonemetal  Members   -  Reputation: 288

Like
0Likes
Like

Posted 12 April 2010 - 12:03 PM

A* would be helpful if you were searching a larger world space. In pacman the world is usually small enough that it doesn't matter.

### #5Kimera  Members   -  Reputation: 100

Like
0Likes
Like

Posted 12 April 2010 - 03:25 PM

I read a while ago that there are 4 separate A.I.s, one for each of the ghosts in Pacman: follow, intercept, wander, and camp the wrap-around tunnel thing.

[Edited by - Kimera on April 12, 2010 10:25:23 PM]

### #6LorenzoGatti  Crossbones+   -  Reputation: 2734

Like
0Likes
Like

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.

### #7Steadtler  Members   -  Reputation: 220

Like
0Likes
Like

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.

### #8Emergent  Members   -  Reputation: 971

Like
0Likes
Like

Posted 14 April 2010 - 12:14 PM

Quote:
 Original post by SteadtlerI 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.

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS