Jump to content

  • Log In with Google      Sign In   
  • Create Account

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.

  • You cannot reply to this topic
7 replies to this topic

#1 kvsingh   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?

Sponsor:

#2 Asik   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

#3 Emergent   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.

#4 stonemetal   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.

#5 Kimera   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]

#6 LorenzoGatti   Crossbones+   -  Reputation: 2764

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.

#7 Steadtler   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.

#8 Emergent   Members   -  Reputation: 971

Like
0Likes
Like

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.




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