Pathfinding Algorithm For 2 Pacmans

Question

I'm trying to implement Pacman. It works fine, but so far, the ghosts aren't using any pathfinding, but instead just decide randomly on each path junction which path to take. So you can imagine that it isn't really difficult for Pacman to win the game ;)

So I read a little bit about path finding algorithms in Pacman and here on SO I found a really good answer: http://stackoverflow.com/questions/2604022/pathfinding-algorithm-for-pacman

The answers are referring to http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter%204

This is all fine, but in my implementation of Pacman, there are two Pacmans which are played by two different players. So I wonder how to adapt the pathfinding algorithms, so that the ghosts are not always chasing one player.

Any thoughts on how to modify the algorithm so that the ghosts are more or less equally fair to both players?

Answer 1

(Haven't looked but) I'm guessing that all the ghost algorithms base their behaviour on the relative positions of the ghost and 'the player' - well, simply have each ghost change its mind about which of the two players it uses as 'the player' in its algorithm, every so often.

Determining what exactly "every so often* means here is going to be a question for playtesting - should it be on a fixed schedule? Vary per ghost? Vary based on the relative proximity of the two players? Randomly - on a uniform / Poisson / other distribution?

There are as you can see many possibilities. Bear in mind that you want to avoid both behaviour which is 'too good' and behaviour which is 'too stupid'...

Answer 2

If you can query the distance and direction to any one Pacman from any one Ghost and also the number of Ghosts (and which Ghosts) are currently chasing any one Pacman, you should be able to make a pretty good and simple AI with some creativity.

Answer 3

I think the easiest strategy is to make each ghost chase the player closest to it. Proximity can be calculated using Manhattan distance (there was a link to it in the pathfinding question) or Euclidean distance or by a path length to the players. The last option means that you will have to compute paths to both players. Try all these options and choose one to your taste.

Also, on a side note. All people answering the pathfinding question didn't mention Dijkstra's algorithm which is even slower than BFS :) but allows to search all shortest paths only once. That is, if you implement A* or BFS and have n ghosts you will make at least n pathfinding queries. With Dijkstra you can do it only once starting from the player. But it all depends. If your game field is too large, Dijkstra is not the best choice. Try, experiment and maybe it'll suit you.

Answer 4

I think you keep the pathfinding algorithms described on this web page you mentioned. That will make the game feel more true to the original. The only problem then is to determine how many ghosts chase a particular Pacman. I think this behavior should include scenarios where all of the ghosts are chasing one player. So, an algorithm is needed to determine if 1, 2, 3, or 4 ghosts are chasing a player. The algorithm could be based on the point difference between the players. So, the player in the lead would get chased by more ghosts. The algorithm should probably factor in the number of lives left for the player. So, if the player in the lead has fewer lives, the algorithm should delay increasing the number of ghosts chasing the player in the lead. The frequency of change in the number of ghosts chasing a player should also not happen too often. If a ghost changes the player being chased too much, then the ghost will seem to not really be chasing either. Just like the web page mentioned, getting a good behavior is going to take some experimentation. I think keeping it simple at first is key because sometimes complex looking behavior can be achieved by using a few simple rules. Good luck and I would love to see what you come up with. Please post a link when you get done!

Answer 5

I don't know if this coincides with your notion of "fairness", but I imagine one would like to prevent the case where one player happened to be the closer target to all 4 ghosts and so they end up ganging up on him and following him around, never again to chase the other player. This would be a possible result of the rule to have the ghost always follow the closest player.

You might consider first allocating fairly 2 ghosts to player 1 and 2 other ghosts to player 2, and then have them chase their targets (and reassigning this every so often). Although, if I were a ghost in the real world I wouldn't care if all my friends and I were ganging up on one pacman.

Instead of BFS or Dijkstra, I would use depth first search to depth 3 or 4, using Cartesian distance between your ghost and the Pacman at the leaves of this search tree and picking the value of the best leaf up to the root. For a small lookahead, it would be faster and easier to code compared to BFS and Dijkstra. Depth limited search should give you pretty intelligent behavior for your ghosts, assuming your gameboard does not have spiraling corridors where the number of moves required to escape the spiral is greater than 3 or 4. It also means the running time of the algorithm doesn't increase with larger and larger boards as does BFS and Dijkstra, again assuming you don't have spiraling corridors.