bla*_*ket 12 search artificial-intelligence
在像魔兽争霸3或帝国时代这样的游戏中,AI对手可以在地图上移动的方式几乎是无限的.地图很大,其他玩家的位置也在不断变化.
这些游戏中的AI路径查找工作原理如何？在这样的设置中,标准图搜索方法(例如DFS,BFS或A*)似乎是不可能的.
Dat*_*ith 15
以下是一粒盐,因为我没有第一人称寻路经验.
话虽如此,可能会有不同的方法,但我认为标准的图搜索方法,特别是(变体)A*对战略游戏来说是完全合理的.我所知道的大多数策略游戏似乎都基于一个平铺系统,其中地图由小方块组成,可以很容易地映射到图形.一个例子是星际争霸II(截图),我会在这个答案的其余部分继续使用它作为一个例子,因为我最熟悉它.
虽然A*可以用于实时策略游戏,但是通过对核心算法的调整必须克服一些缺点:
A*太慢了
由于RTS是通过定义"实时",等待计算完成将使玩家感到沮丧,因为单位将滞后.这可以通过几种方式解决.一种是使用多层A*,它在考虑较小的障碍之前计算粗略的路线.另一个明显的优化是将前往同一目的地的单位分组为一个排,并且只计算所有这些目的地的一个路径.
人们还可以构建一个导航网格,而不是将每个单个图块作为图形中的节点的天真方法,该网格具有更少的节点并且可以更快地搜索 - 这需要稍微调整搜索算法,但它仍然是A*核心.
A*是静态的
A*适用于静态图形,那么当景观发生变化时该怎么办？我不知道在实际游戏中如何做到这一点,但我想我的路径是反复进行的,以应对新的障碍或消除障碍.也许他们正在使用增量版的A*(PDF).
要观看星际争霸II的演示,请参阅此视频中的 7:50 .
A*有完美的信息
许多RTS游戏的一部分是未开发的地形.由于你无法看到地形,你的单位也不应该知道在哪里走路,但往往他们也会这样做.一种方法是惩罚步行穿过未开发的地形,因此单位更不愿意利用他们的全知,另一种方法是将全知科带走,只是假设未开发的地形是可步行的.这可能导致单位陷入死胡同,有时是玩家明显的死角,直到他们最终探索到目标的路径.
战争迷雾是另一个方面.例如,在星际争霸2中,地图上有可破坏的障碍物.已经证明,你可以命令一个单位移动到敌人的基地,如果你的对手已经摧毁了障碍物,它将开始不同的路径,从而为你提供你不应该拥有的信息.
总结一下:您可以使用标准算法,但您可能必须巧妙地使用它们.作为最后一个奖励:我发现Amit的游戏编程信息在路径方面很有趣.它还与进一步讨论该问题有关.