一些与Pacman路径寻找相关的问题

Question

我学习了A*、BFS和DFS算法，并且能够很好地实现它们。然而，在解决吃豆人寻路问题时，会遇到一些问题。假设迷宫只有两种类型：一种是所有空格都有元素，即没有空白方块，每个方块上要么是吃豆人，要么是要收集的物品，要么是墙；另一种只有少量物品（4个或更少）。

1. 如果要收集多个物品，BFS和DFS应该如何实现？在这种情况下，它们是否仍然能够产生最优结果？

2. 对于全有物品的地图来说，哪种算法/启发式函数最好呢？到目前为止，我想到的是一种贪心启发式函数，但由于地图上有太多要收集的物品，因此它非常随机，不是解决此类迷宫问题的好方法。

3. 在使用A*算法处理只有几个物品的地图时，有没有一种好方法确定首先拿取哪个物品？我考虑过使用曼哈顿距离作为粗略估计，但在某些棘手的情况下，这似乎不正确。

- IcySnow

---

第二个问题似乎有一点简单...pacman只想吃掉所有的好东西，所以他必须访问图中的每一个节点，任何图遍历方法都可以。也就是说，除非有某种限制（比如在移动X次后被幽灵吃掉），并且好东西有不同的价值？其他两个问题都很棒，我会尽力解决它们，因为没有更好的事情可做...你不会碰巧写了一个小型的pacman框架，可以节省我的时间吗？;) - jjm

关于问题2：唯一的限制是Pacman找到的路径应该是步数方面好（或最优的）。如果我让Pacman毫无头绪地移动，只访问每个开放的方块一次，那么这样做是行不通的，对吧？至于框架的事情，真的很抱歉，但我没有任何框架:( - IcySnow

Answer 1

1）我在这种情况下使用BFS或DFS会遇到的问题是效率低下，特别是在完整地图的例子中。要让这两种算法能够处理多个目标，你可以构建搜索过程，使其不止于找到第一条路径，但这仍然无法为地图上的每一块食物提供“最优”路径。或者你可以从Pacman到最近的食物，然后从那个食物到下一个最近的食物，以此类推，找到这些路径，再对比它们，找到真正的最优路径，但我不想考虑那会花费多长时间。

2）我可能会坚持使用贪婪的A*算法，只关注最近的食物（我认为在大多数情况下，曼哈顿距离都没有问题，因为Pacman的地图已经是一个网格；对于一些边缘案例，墙壁会阻止Pacman接近最近的食物，但这是一个难解决的问题）。曼哈顿距离可能是一个不错的选择，可能可以根据食物密集度进行修改，例如：（曼哈顿距离）/（3x3方格内所有食物的总数）。

3) 除了在每个物品上使用路径查找，然后选择最短路径外，我认为曼哈顿距离在少量物品的情况下也可以胜任。它不总是选择最佳路径，但对于游戏而言，100%最优的AI通常不是最好的目标。

在这种情况下，我想尝试贪婪A*算法，以权重偏向物品集群作为一个简单、相当快速的解决方案。

一个更复杂的解决方案，应该能够返回更接近最优路径的Pacman跟随算法，是使用一种算法来找到最小生成树http://en.wikipedia.org/wiki/Minimum_spanning_tree，但我不知道实现起来有多容易。这里有一个讨论两种最小生成树算法优点的问题：Kruskal vs Prim

- David M

Answer 2

算法不会因为添加更多的食物而改变，唯一改变的是状态空间。您必须考虑一种新的方式来表示您的问题。当您只有1种食物可供食用时，您只需要知道Pacman的x、y位置。例如，当您有3个点要吃时，您必须将这些信息添加到您的模型中。您可以添加3个布尔变量来指示Pacman是否通过了该点。现在，您的状态空间是由以下类型的节点组成的图形：

 ((x,y),FALSE,FALSE,FALSE) -> state that indicates that pacman has not eat any food
 ((x,y),FALSE,TRUE,FALSE) -> state that indicates that pacman has eat only one food
 ((x,y),TRUE,TRUE,TRUE) -> this is the goal state

要解决这个问题，你只需要在新模型中运行相同的算法。BFS和A*总是会给出最优解。问题是：你放置的食物越多，找到解决方案的速度就越慢。因此，这些算法无法在合理的时间内给出答案。你需要想出新的解决方法。

- Bruno Calza