PacMan: what kinds of heuristics are mainly used?
Beside A*, BFS, DFS and the like, what are other good path-finding algorithms/heuristics popularly used in Pacman? I don't think the ones I mentioned will work if there're more than one fruits for pacman to find.
I need some good path-finding algorithms that PacMan can use to finish the maze with the least possible step-count. I've tried to search around for a guideline, but so far no luck. A* with Manhattan distance is mentioned everywhere but it will only work with mazes with only one (or two? or maybe up to a few?) fruit to get.
BTW, to keep things simple, assuming that there're no ghosts around.
Some examples from the original PacMan problems: First, Second and Third
Answer
Heuristic which worked for me if you know the look of labyrinth:
- Find real distance between two currently furthest fruits in labyrinth - let's call that
x. - Find real distance from current Pacman position to the closer of previous two fruits - let's call that
y.
Then, answer is just: x + y.
Note that real distances are not Manhattan distances, but real distances in maze - you can calculate that (even precalculate if you want) because you know the look of labyrinth (you know all the walls, ...). This information (real distance between some two points in maze) is static because walls don't change.
The interpretation of this x + y formula could be something like this:
x- either way, you will have to travel this distance, at least at the endy- while you are at the some of the two furthest fruits, it's better to collect the food that is near to it so you don't have to go back
If you are solving this as a part of Berkeley AI class project, for calculation of real distance between two points you could use function mazeDistance(pos1, pos2, gameState) which is already implemented and is using your implementation of bfs. Also, this heuristic is admissible and consistent, at least for their test cases. By the way, with this heuristic I managed to expand just 376 nodes in trickySearch maze.