Pacman pathfinding heuristic

Question

How do I go about implementing an admissable heuristic function for a pacman game such that it finds the shortest path from a given location that includes multiple goals(all remaining dots). Currently i'm using an A* search with manhattan distances as the heuristic. I take the sum of all manhattan distances from a node to every remaining dot that has not yet been eaten and that is my H(n). The algorithm takes extremely long to complete and i'm not really sure about how to tiebreak.

Answer 1

Well, I'm assuming you're taking the edX course in Artificial Intelligence.

Taking the sum of the difference between your current position and each food pellet will not be admissible as you need to take into account that eating one pellet may get you even closer to another pellet.

Depending on the size of the grid and how sparse it is, what you can do is run a BFS from your pacman's current location to find the nearest pellet. You can then use that distance as an admissable heuristic.