我最近看了这个video，它使用BFS搜索算法解决了一个忒修斯和牛头怪的难题。如果你不熟悉它，它是一个难题，忒修斯和牛头怪被放在一个瓷砖迷宫，忒修斯必须在不被牛头怪抓住的情况下逃脱。每当忒修斯移动一个瓷砖，牛头怪移动两次。然而，牛头怪的行为是这样的，它只能直接向忒修斯移动，它总是试图在垂直移动之前水平移动。因此，这可以被利用，以逃离迷宫。如果你有兴趣尝试玩它，可以找到一个很好的游戏实现here。
我现在尝试在Kotlin中实现my own solver，但使用A* 算法而不是BFS。然而，我这样做有困难，我不确定为什么我的代码不工作。而不是传统的A* 算法，其中有一个节点对象存储代理的位置，我有一个状态对象，它存储了忒修斯和牛头怪的位置。然后我使用一系列辅助函数来确定忒修斯和牛头怪的下一个可能位置，这样忒修斯就不会运行了。从那里，我使用了A* 算法的一个非常传统的实现，它只考虑Theseus的位置（函数aStar），并使用一个助手函数来计算基于Theseus从目标的位置的启发式算法。
1条答案
按热度按时间hrysbysz1#
这是我看到的bug。
1.忒修斯不能在你的解算器中等待。他站在原地是有效的。也就是说，你需要移动
0 to 0。1.在求解器中，牛头怪可以在球门处抓住忒修斯。但在游戏中，如果忒修斯到达球门，即使牛头怪可以追上，他也会赢。因此在
getNextStates中，不要丢失牛头怪在球门处抓住忒修斯的状态。1.游戏中有牛头怪和忒修斯不能穿过的墙。你需要一个表示法，让你注意到你不仅需要法律的开始和结束位置，你还需要没有穿过墙。
1.你的
gScore需要是州的得分，而不是忒修斯所在位置的得分。你的游戏中的获胜路径是lddrdduuluuuuurrrrr。（l =左，r =右，u =上，d =下，w =等待）忒修斯需要被允许在陷阱牛头怪之后返回他的路径。这不是一个重复的位置，因为它关系到牛头怪已经被陷阱。