寻路算法-重新启发
### 引子
在新地方, 第一个需要处理的任务就是寻路. 说起来, 跟我做的独立项目有一些类似, 场景都是动态的. 需要动态的碰撞检测, 动态的寻路. 而新项目的频率更高, 会有高频的场景变化, 并且路线会有不断的变化可能, 例如:
- 移动的可行走的平台
- 断桥
- 地洞
等等, 那么传统的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*算法便退化为Dijkstra算法, 为一个全量搜索
- 如果将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* 的变种算法考虑