寻路算法-重新启发
25 Aug 2019
引子
在新地方, 第一个需要处理的任务就是寻路. 说起来, 跟我做的独立项目有一些类似, 场景都是动态的. 需要动态的碰撞检测, 动态的寻路. 而新项目的频率更高, 会有高频的场景变化, 并且路线会有不断的变化可能, 例如:
- 移动的可行走的平台
- 断桥
- 地洞
等等, 那么传统的navmesh, 或者说那种dynamic navmesh, 也基本上效率跟不上了. 因此, 就可能需要重新审视寻路系统, 开发适合项目需求的一套性能和效果得以平衡的寻路系统了.
寻路算法-审视
Dijkstra算法
这是一种一定正确的算法, 他会遍历整个区域的行走节点, 从而找到一条真正的最短路径. 然而弱点也显而易见, 效率过低, 基本不可用.
Greedy Best-First Search算法
俗称贪心算法, 从起点到终点, 每次都从临近的可行走节点, 选择一个当前的”最佳”解, 一般是欧式空间里, 距离终点最近的哪那一个节点. 逐步往下, 不走回头路.
贪心算法一定能找到一条可行路线, 但一般不是最优的. 优点在于复杂度很低, 效率高. 弱点, 当然就是很难找到最优解, 路径看起来非常”短视”.
A*算法
A*算法是对Dijkstra算法的一种优化, 他引入了一种启发式搜索, 核心是一个cost函数
f(n)=g(n)+h(n)
g是路径的实际消耗, 而h是剩余距离的预估消耗, 预估消耗一般使用欧式距离, 以保证搜索是收敛的.
因此,A*搜索在Dijkstra的基础上, 加入的一个h(n), 使得搜索可以往”更为可行”的方向进行,而放弃那些不太有可能性的方向,此为”启发”的含义
可以看到
- 如果将cost函数变为f(n) = g(n), 那A*算法便退化为Dijskstra算法, 为一个全量搜索
- 如果将cost函数变为f(n) = h(n), 那A*算法便退化为贪心算法, 准确性降低
A*可以说是一种较为准确,又较为快速的寻路算法
寻路算法-应用回顾
道路生成时的应用
cost函数
在之前开发过程生成地形时, 其实就从头写过一个类似A*算法的启发式路径搜索算法. 核心的cost函数依然为:
f(n) = g(n) + h(n)
h这个启发函数依然是使用的欧式距离. 而改造了g函数, 一般的g函数就是实际的”行走”距离.
g的cost来自于几个方面:
- 坡度消耗, 坡度越陡峭, 消耗越高, 因此最后的路径会倾向于选择缓坡, 形成盘山公路样式的路径
- 水域消耗, 越接近水域, 消耗越高, 最终的路径会尽量离水域较远
- 曲率消耗, 行走时会持续计算最近三个路径点的曲率, 曲率越高, 消耗越高, 最终路径会尽量选择较为平直的路径
- 阻挡消耗, 水,峭壁是阻挡体, 消耗正无穷, 此路不通
寻路网格
在3d空间的寻路和2d空间不同, 因此, 是将地形按照一定的grid, 采样出一个寻路的2d node空间. 然后, 在实际需要生成的时候, 从node空间中, 采样出以起始,终点的中心为原点, 起始,终点长度为半径的一个圆形的子空间. 所有的路径最终在这个空间中进行.
效率
效率直接和g(n)函数的设计有关, 当g(n)消耗很平均的时候, 搜索次数会十分高, 因为路径会展开得非常快. 同时, 采样和g(n) h(n)函数的运算速度也息息相关. 这方面都有较大提升空间, 而因为当时的道路生成的时效性要求不高, 所以我是将实现进行分帧, 相当于在背景运行, 可以慢慢的完成最终的道路生成
现在的思路
navMesh本身是一种在静态空间内十分高效的一种寻路解决方案, 基于体素的导航面生成, 也能非常好的处理在3D空间内的寻路. 这是2d寻路算法无法比拟的. 然而在动态空间中, 他本身的生成消耗, 可能大于了其对寻路优化的贡献.
因此, 可能会考虑从基础的A*算法上进行优化与扩展, 以在动态环境中提供既可以高效更新导航数据, 又能快速寻路的算法.
导航数据
思路
在环境初始化, 改变时, 对修改区域的环境进行重采样, 分布到一个2d node空间 对node进行连通性梳理, 传统的2d grid, 联通性就是4或8方向. 而为了能够达到各方向行走, 我们可以在2层-3层空间内进行联通
问题
对于多层的可行走区域, 暂时没有很好的想法, 目前可以考虑将空间分为多层2d空间, 在部分地方, 进行跨空间的联通
寻路
基础
h(n), 考虑为欧式距离
基础的g(n), 可以就考虑为实际的行走欧式距离
这样的算法足够简单,也足够收敛. 并且,在构建联通性时,可以直接将每一个step的g(n)缓存在节点上,更加高效
进化
g(n), 可类似之前道路生成算法, 加入一些游戏性相关的cost计算, 让路径避开一些”不好”的区域
优化
在进行搜索时,可以考虑加速的的容器结构 ARA* , D* , B* 等 A* 的变种算法考虑
blog comments powered by Disqus