Pathfinding Algorithm For Pacman
Members - Reputation: 100
Posted 08 April 2010 - 11:40 AM
Members - Reputation: 136
Posted 08 April 2010 - 05:03 PM
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.
Crossbones+ - Reputation: 3178
Posted 13 April 2010 - 08:54 PM
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.
Members - Reputation: 220
Posted 14 April 2010 - 03:02 AM
Members - Reputation: 977
Posted 14 April 2010 - 12:14 PM
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.