PacMan: what kinds of heuristics are mainly used?

Question

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 1

Heuristic which worked for me if you know the look of labyrinth:

1. Find real distance between two currently furthest fruits in labyrinth - let's call that x.
2. 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 end
• y - 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.

Answer 2

You comment says you are looking for shortest path. This problem is a variation of TSP on a planar graph, and thus is NP-Hard.

Possible heuristics function for A* that can solve the problem but is not admissible [thus the path found is not guaranteed to be optimal]:

Sum of manhattan distances from all fruits to the agent.

You can also use an edmissible heuristic, of #fruits - but it will take a long time.

If you are looking for optimal, well - it is hard. You can try all permutations of fruits, and check the total distance you need to travel. This solution is factorial in the number of fruits, and if it is greater then 20 - with naive bruteforce - it will take too long. You can somehow make it better by reducing the problem to TSP, and use dynamic-programming solution, which is also exponential, or some heuristical solutions to TSP.

---

One can also improve the non-admissible heuristic solution to provide an any-time algorithm:

iteratively run A* with a decreasing heuristic function: h(v) = h'(v) / m, where h' is the heuristic function on last iteration of A*, and m > 1. This guarantees that at some point, your heuristic function h will be admissible - and the solution found will be optimal. However, each iteration is expected to take much longer then the previous one [exponentially longer..]