flow-field-path-search

流场寻路算法认识

Flow field pathfinding algorithm implementation

  • 主要解决问题

    1. 大规模的队伍寻路,并且相互碰撞产生的通道挤压效果

    2. 类似于魔兽或者星际争霸或者各种宣传视频的大批量单位寻路

  • 寻路算法及其效率方面

    1. 算法:A星,变种A星,Dijkstra, Flow Field PathFinding

    2. 效率:

      A星 主要是一个拓扑,启发式搜索,主要维护close和open表,每次从open表取一个代价最小的点出来拓扑(四方向/八方向),检查更新代价,放去open表,当前点放去close表,效率方面的话单挑路径是挺可观的,拓扑结束open表为空或者当前到达了目标点。优化方面可以open表做堆,减少取点的判断,把点划分一下区域(导航网格);
      Dijkstra, Flow Field PathFinding 算法主要维护close和open表,是把整个网格都拓扑一遍,拓扑结束点是open表为空,把所有点的代价都算上去,单路径上面比A星差很多

  • 算法思路

    1. 把所有的单位分组实现,复用A星的路径,但是不好的地方就是路径一样,做不了分散走的效率,通过狭窄通道的时候会卡住,单位多,效率变差

    2. 把目标点进行Dijkstra拓扑网格出来,生成流场,每次运动只需要根据流场的当前点寻找到下一个点就可以了,这样的对于挤压方面或者说通道上也不需要再次寻路,这个点不行换点就好,每次只找当前点的下一个点。

  • 算法效果图预览:

    1. 场景地图初始状态

      其中黑色是代表不能通过的路径,绿色是通过的路径代价较大(比空白区大)

    2. 场景拓扑代价状态

      其中65536代表的是不可通过路径,数字代表终点到这个点的代价

    3. 场景生成流场状态

      箭头表示的是方向流场方向

  • 算法实现

    暂无实现

  • 算法效果预览

  • 效率对比

    网格大小:200*200

    耗时:

    算法 寻路单位个数 用时
    A* 1 ≈18MS
    优化A* 1 ≈8MS
    Dijkstra 1 ≈58MS
    A* 3000 很长
    优化A* 3000 数十秒
    Dijkstra 3000 ≈58MS

    效率方面,Dijkstra单次效率远低于其他的效率,但是数量多的情况效率会高很多,原因是因为Dijkstra只会生成一次寻路,整个场景上的所有单位公用。

  • 优化方向

    1. 可以考虑导航网格进行优化
    2. 更新障碍可能会产生重新刷新整个网格,可以考虑只刷新跟附近相关
  • 参考文章:

    https://blog.csdn.net/klyhssrs/article/details/51578398

    https://www.cnblogs.com/zblade/p/7608275.html

打赏

扫一扫,分享到微信

微信分享二维码

请我喝杯咖啡吧~

支付宝
微信