search - 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

好吧，我假设您正在学习 edX 人工智能课程。

不允许将您当前位置与每个食物颗粒之间的差值相加，因为您需要考虑到吃一个颗粒可能会让您更接近另一个颗粒。

根据网格的大小和它的稀疏程度，您可以做的是从 pacman 的当前位置运行 BFS 以找到最近的颗粒。然后，您可以将该距离用作可接受的启发式方法。