Pathfinding Algorithm For Pacman
Author
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?
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, rightAnd then there are many more details that make the ghost behavior varied and unpredictable.
http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter 3
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.
2 - A* is just a more efficient version of BFS which is guided by a heuristic.
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.
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]
[Edited by - Kimera on April 12, 2010 10:25:23 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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
