什么是在所有类型的游戏中使用的路径查找算法？(在角色移动的所有类型中,无论如何)Dijkstra曾被使用过吗？我真的不想编码任何东西; 只是做一些研究,但如果你粘贴伪代码或其他东西,那就没问题了(我可以理解Java和C++).
我知道A*就像在2D游戏中使用的算法.这很棒,但是那些不是基于网格的2D游戏呢？像帝国时代,或链接的觉醒.没有明确的方形空间可供导航,所以他们做了什么？
3D游戏有什么作用？我已经读过这个东西http://www.ai-blog.net/archives/000152.html,我听说这是一个关于这个主题的伟大权威,但它并没有真正解释如何,一旦网格设置,路径查找完成.如果A*是他们使用的,那么在3D环境中如何完成？花键究竟是如何为圆角设计的？
Dijkstra算法计算图表中可从起始位置到达的所有节点的最短路径.对于普通的现代游戏来说,这既不必要又非常昂贵.
您对2D和3D进行了区分,但值得注意的是,对于任何基于图形的算法,搜索空间的维数都没有区别.您链接的网页讨论了航点图和导航网格; 两者都是基于图形的,原则上可以在任何数量的维度上工作.虽然没有"明显的方形空间移动到"外,还有是不连续的"槽",在空间的AI可以移动并已经由游戏设计师经过精心奠定的.
总之,A*实际上是在3D游戏中使用的算法,与2D游戏一样多.让我们看看A*是如何工作的:
我在这里没有讨论过一些细节,但这应该足以看出A*基本上与你的空间维数无关.您还应该能够了解为什么这适用于连续空间.
有一些密切相关的算法可以处理标准A*搜索中的某些问题.例如,递归最佳优先搜索(RBFS)和简化的内存限制A*(SMA*)需要较少的内存,而学习实时A*(LRTA*)允许代理在计算完整路径之前移动.我不知道这些算法是否实际用于当前的游戏.
至于拐角的圆角,可以通过距离线(其中拐角由圆弧替换)或者使用任何类型的样条函数进行全路径平滑来完成.
此外,依赖于搜索空间上的梯度(空间中的每个点与值相关联)而不是图形的算法是可能的.这些可能不适用于大多数游戏,因为它们需要更多的时间和记忆,但无论如何都可能很有趣.示例包括各种爬山算法(默认为实时)和潜在的现场方法.
还存在从连续空间程序性地获得图的方法,例如细胞分解,Voronoi骨架化和概率路线图骨架化.前者会产生与导航网格兼容的东西(尽管可能很难使其与手工制作的导航网格同样有效),而后者则产生的结果更像是航点图形.所有这些以及潜在的野外方法和A*搜索都与机器人技术相关.
资料来源: