使用 A* 搜索算法解决忒修斯和牛头怪的谜题

问：

我最近看了这个视频，它使用 BFS 搜索算法解决了忒修斯和牛头怪的难题。如果你不熟悉它，这是一个谜题，忒修斯和牛头怪被放在一个瓷砖迷宫里，忒修斯必须在不被牛头怪抓住的情况下逃脱。每忒修斯移动一个格，牛头怪就会移动两次。然而，牛头怪的行为是这样的，它只能直接向忒修斯移动，而且它总是会尝试水平移动，然后再尝试垂直移动。因此，可以利用这一点来逃离迷宫。如果您有兴趣尝试玩它，可以在此处找到该游戏的一个很好的实现。

我现在尝试在 Kotlin 中实现我自己的求解器，但使用 A* 算法而不是 BFS。但是，我在这样做时遇到了麻烦，我不确定为什么我的代码不起作用。与传统的 A* 算法不同，其中有一个存储代理位置的节点对象，我有一个存储忒修斯和牛头怪位置的状态对象。然后，我使用一系列辅助函数来确定忒修斯和牛头怪的下一个可能位置，这样忒修斯就不会撞到墙上、迷宫里或牛头怪（函数 getNextStates）。从那里开始，我使用一个非常传统的 A* 算法实现，该算法仅考虑 Theseus 的位置（函数 aStar），并使用辅助函数根据 Theseus 的位置从目标计算启发式。