性能优化3-分帧寻路+寻路任务统一管理

前言

当项目里的地图越来越大,一些性能上的问题开始逐渐出现,比如寻路。玩家在操控角色移动的时候,指引需要实时更新,同时一些npc也需要做移动,容易出现cpu占用率短时间过高,甚至掉帧的情况。

去年底的时候,由于希望在性能优化方面做一些研究,在论坛找到了江南百景图研发负责人的技术分享文章,其中提到了分帧寻路+寻路任务统一管理的优化思路。

针对地图很大、建筑物和人物都很多的情况下,这些算法一起执行就会很损耗性能。所以我们用了 分时寻路 ,就是把寻路过程由一帧分到若干帧去进行计算,这样就不会在某一个时间段集中进行大量运算,对游戏性能也不会有太大的影响。

统一管理寻路任务,同一时间只为一个角色服务。也许有人会问,那岂不是一个角色在哪里走、其他对象都在那边等着?其实真正在游戏里不会有这种奇怪的表现。首先每个角色寻路的起始和结束时间都不一样,再者这个同一时间是非常短的,就等于把角色寻路分配到了不同帧里,交替进行执行。

感觉方案很有意思,便尝试做了出来。寻路基于a* 算法实现,只支持四方向移动。a*算法在网上有大量文章,文末贴了一篇文章链接,本文中不会细说。

开发环境

浏览器:Chrome
开发语言:JavaScript
引擎版本:CocosCreator 2.4.3

词语缩写对照

分享文章:《江南百景图》的分享文章
分帧寻路:本文提到的优化技术,同分时寻路。
开放队列:a*算法中的开放队列(open list)。

研究过程

分享文章中讲的很清楚,就是把寻路这件事情拆成好几段,每帧做一段。
在a*算法中,每次会从开放队列中取出一个坐标,我们需要修改这里的代码,限制取坐标的最大数量

从开放队列取坐标时,需要保证每次取出来的都是最有价值的坐标(离终点最近),地图尺寸过大时, 保证坐标的正确取出也是不可忽视的损耗点。我们可以使用优先队列降低性能损耗,但js中没有内置的实现,所以这里我们还需要实现一个优先队列。

分享文章中提到,他们还将寻路任务进行统一管理。当某帧有多个寻路任务时,仍会出现单帧时间过长的问题,所以还是一步到位吧!
一般情况下,同屏npc且需要同时寻路的数量不会特别多,所以我们实现一个队列型的任务管理器即可。

实现思路

需求可大致拆分为如下步骤:

  1. 实现提交寻路任务的入口函数,存储寻路任务相关数据(起点、终点、障碍物等)。
  2. 实现寻路函数。
    1. 取出需要执行的任务,若任务为空则退出。
    2. 执行一次寻路,判断是否超出最大步数,是则退出,否则循环步骤b。
    3. 若完成寻路,加载下一个的任务。
  3. 新建寻路管理类,在游戏中持有寻路管理类,并每帧调用寻路函数。

方案涉及文件

文件名 说明
Game.js 游戏类,持有并调用寻路管理器
PathFinder.js 寻路管理类,实现分帧寻路、任务信息存储等功能
PriorityQueue.js 简易版优先队列

方案涉及类

类名 声明于 说明
PathFinder PathFinder.js 寻路管理类
RoadPoint PathFinder.js 路径点类,存储路径点的位置、父路径点等信息,并计算cost值
FindRoadTask PathFinder.js 寻路任务类,存储寻路的相关数据如碰撞信息、起点终点等
PriorityQueue PriorityQueue.js 简易版优先队列

实现代码解析

首先实现提交寻路任务的函数。若当前无任务则立即执行,有任务则加入等待列表

// PathFinder.js
/**
 *  添加一个寻路任务。此函数为外部调用入口
 * @param {FindRoadTask} task 寻路任务 
 */
addFindRoadTask(task) {
    if (!this._finding) {
        this._startFindRoadTask(task);
    } else {
        this._taskList.push(task);
    }
}

接着实现开始寻路任务的函数。取出并缓存寻路任务的相关数据,如最大步数、起点、终点等。

// PathFinder.js
/**
* 开始执行寻路任务
* @param {FindRoadTask} task 寻路任务 
*/
_startFindRoadTask(task) {
    const { maxWalkPerFrame } = task.config;
    
    this._finding = true;
    this._nextRoadPointId = 0;
    this._maxWalkPointAmount = maxWalkPerFrame || Number.MAX_VALUE;
    
    // 重置任务相关数据,存储task相关数据
    this._resetData(task);
}

实现由外部调用的更新函数,应被每帧调用持续从开放队列中取出路径点,超出最大每帧寻路次数时停止。
this._waitQueue为前文提到的开放队列(优先队列),poll函数将取出离终点最近的点(理论上)。

// PathFinder.js
/**
* 此函数应由外部引用者每帧调用
*/
update() {
    if (this._finding) {
        this._findPath();
    }
}
/**
* 执行一次寻路
*/
_findPath() {
    let walkPointAmount = 0;
    
    while (walkPointAmount++ < this._maxWalkPointAmount) {
        // 无可到达的路径点 寻路失败
        if (!this._waitQueue.length) {
            this._findFail();
            break;
        }
        
        // 访问下一个最优先路径点
        const point = this._waitQueue.poll();
        this._onWalkPoint && this._onWalkPoint(point);
        const success = this._visitRoadPoint(point);
        
        if (success) {
            this._findSuccess();
            break;
        }
    }
}

寻路完成时,开始下一个寻路任务

// PathFinder.js
/**
* 寻路任务结束回调。不论寻路成功或失败都会调用本函数
*/
_onFindOver() {
    if (!!this._taskList.length) {
        this._startFindRoadTask(this._taskList.shift());
    } else {
        this._finding = false;
    }
}

最后,在Game中持有寻路管理类,每帧调用寻路管理类的update函数

// Game.js
onLoad() {
    this._pathFinder = new PathFinder();
},
update(dt) {
    this._pathFinder.update();
}

实现起来其实并不难。寻路的具体实现这里没有贴出来,可以自行实现或在源码中查看。

使用范例

在Game中创建寻路任务,并调用addFindRoadTask函数提交给寻路管理类。通过最后一个参数中的maxWalkPerFrame属性标记每帧最大访问路径点数量。当寻路完成时会调用onFindFinish函数, 并通过参数传递完整路径。

// Game.js
start() {
    // 测试用的起点、终点坐标
    let playerPos = { x: 2, y: 2 };
    let targetPos = { x: 70, y: 95 };

    // 读取地图的“wall”图层 初始化碰撞信息
    const { width, height } = this.tileMap.getLayers()[0].getLayerSize();
    const walls = new Array(height).fill(0).map(() => new Array(width).fill(false));
    const wallLayer = this.tileMap.getLayers().find((layer) => layer.getLayerName() === "wall");
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (wallLayer.getTileGIDAt(j, i)) {
                walls[i][j] = true;
            }
        }
    }
    // tiledmap坐标原点为左上角 需要反转y轴
    walls.reverse();

    let tsak1 = new FindRoadTask(playerPos, targetPos, walls, this.onFindFinish.bind(this));
    this._pathFinder.addFindRoadTask(tsak1);
}
/**
 * 寻路结束回调
 * @param {[RoadPoint]} path 路径点列表
 */
onFindFinish(path) {
    if (path) {
        for (const point of path) {
            const { x, y } = point;
            const node = cc.instantiate(this.nodePoint);
            this.nodePointParent.addChild(node);
            this.setNodePos(node, x, y);
        }
    } else {
        console.log("寻路失败");
    }
}

寻路结束时打印路径。this.nodePoint是一个蓝色小圆点,onFindFinish函数中会根据路径在地图上生成若干小圆点。
image
代码见文末附件,有需要可自取。比较简陋,以测试功能为主。
为了方便观察效果,游戏中有一个蓝色方块和一个红色方块,蓝色表示起始位置,红色表示终点位置。另外还有一个‘find’按钮,可以将游戏类update中对于寻路管理类的调用挪到按钮的点击事件中,实现手动模拟分帧的效果(点一下一帧)。
演示项目的地图中,灰色图块表示路,黑色图块表示障碍物。

效果对比

测试案例

一张100 * 100,方块大小32 * 32的地图。
同一起点,寻路四次,同一帧内提交任务。起点位于地图右下角区域,四个目标点分别位于地图四个角区域。

文字还是不够直观,上图吧!#狗头


数据为在游戏中统计前三秒(180帧)的寻路函数耗时,耗时并不是精准的,但可以作为参考。横轴为帧,纵轴为寻路函数在此帧中的耗时,单位为ms。
图中有三条不同颜色的折线,其中:
蓝色:不设置最大寻路次数(将会每帧执行一个寻路任务)。
绿色:设置每帧寻路次数为50
黄色:设置每帧最大寻路次数为100

可以明显看出,不设置寻路次数时,前4帧的耗时明显偏高设置最大次数的绿色和黄色曲线相对来说更平缓
什么?你说没有原始对照组?看着蓝色线想象一下,一帧里发生两个5ms耗时的寻路任务会怎么样:rofl:
由于最大寻路次数配置的不同,黄色线大约在80帧左右,耗时逐渐贴近0,绿色线则是在155帧左右。每帧执行多少次比较合适还得结合实际情况进行设置。

总结

  1. 大地图下的寻路是不可避免的性能问题,使用分帧寻路可以压平cpu的曲线,避免因为寻路导致的占用率突然上升甚至掉帧等情况。
  2. 同时间有多个寻路任务时,将按照队列顺序处理,先进先出。此方法足够满足一般寻路需求,若希望优化任务执行时的优先级,还可以参考cpu调度算法进行优化。
  3. 项目中把最大寻路次数的配置放到了提交任务时,每个任务可以配置不同的最大次数。也可以直接将次数限制直接写在管理器中。

代码中的a*不一定可靠,是我盲敲的:rofl:本文主要是分享思路,供参考

性能优化系列会有多篇文章,目前规划如下(不分先后):

其中除了列表渲染优化以外,优化思路都源于江南百景图的分享文章。

相关链接

如何重绘「江南百景图」?近300页 PPT 免费分享!
A*算法详解
源码 (1.1 MB)

22赞

如果终点一直在移动呢?怎么处理的?

1赞

那算法换成D* lite就行,也是可以靠局部信息寻路的 建房子和动态寻路demo

mark,大佬orz

能不能只存放寻路的拐点,这样数据会少一些。走动的时候按斜率来走动
能不能给获得的路径组加一个权重,标识那一条路径最方便,比如走这条路径不用转向,下一条路径拐点较少

尝试了一下,终点如果和角色一样四方向移动,也是可以寻路的。
方案中,任务是做成了一个FindRoadTask类,所以game中也是持有引用的,直接修改终点就好了。
就是寻路算法中要增加一个每帧判断,是不是终点自己跑过来以前访问过的坐标上了 :rofl:

拐点是可行的,我项目中有个另外的模块,寻路的实现就是存拐点,然后每次行动的时候奔着下一个拐点去就好了。
权重的问题我还在思考解决方案。因为像主角,目的地固定,每次移动都要重新寻路,但其实和上一次寻路的起始点就是隔壁,感觉是个很大的浪费。

我之前是这样想的,后来觉得有点难看,就没有用了

只想说, 大佬, 优秀! :laughing:

mark orz

有一个小技巧,就是npc休闲状态下 闲逛的时候不要走寻路系统,直接周围随机一个点走就行;这样能减少很多计算量

在PriorityQueue里加上
updateItem(item){

    let itemIndex = this._items.findIndex(v=>v.id == item.id)

    let itemP = this._items[Math.floor(itemIndex/2) * 2]

    while(itemP && itemP.cost > item.cost){

        this._items[itemIndex] = itemP

        this._items[Math.floor(itemIndex/2) * 2] = item

        let curIndex = Math.floor(itemIndex/2) * 2

        itemP = this._items[Math.floor(curIndex/2) * 2]

    }

}

在pathfinder这里调用会好一点

mark111