我很难在一个简单的精英风格的游戏中为人工智能编写寻路程序。
这个游戏中的世界是由几个“虫洞”连接的“系统”，一艘船可以从它所处的系统跳到它所连接的任何系统，每转一次。人工智能仅限于知道它应该知道的事情；它不知道什么链接来自它没有去过的系统（尽管它可以从它看到的系统中计算出来，因为链接是双向的）人工智能的其他部分根据船舶库存中的货物以及船舶在通过的系统上记住的东西的价值来决定船舶需要到达哪个系统。
问题是，我不知道如何解决找到目标系统路径的问题。我不能用一个*；没有路径就无法确定到另一个系统的“距离”。我还需要这个算法是有效的，因为它将需要运行约100次，每次球员轮流。
有人知道合适的算法吗？
最佳答案
我最终实现了一个双向贪婪的广度优先搜索版本，非常适合这个目的。简单地说，我只是让程序检查每个连接到它的起始节点，然后每个连接到的节点，然后每个连接到的节点直到找到目标节点。
通常人们会建立一个合适的路径列表并选择最短的路径，但我尝试了不同的方法；我让程序并行运行两个搜索，一个从起点开始，一个从终点开始。当“from”搜索找到“to”搜索的最后一个节点时，认为找到了路径。
然后，它通过检查路径上的每个节点是否连接到路径中更上一层的节点并删除它们之间的每个节点来优化路径。
这种时髦的算法是否真的比直接的bfs好还有待观察。
关于algorithm - 知识有限且无距离启发式的寻路，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20933955/