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
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..]