前言

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

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

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

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

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

开发环境

浏览器：Chrome

开发语言：JavaScript

引擎版本：CocosCreator 2.4.3

词语缩写对照

分帧寻路：本文提到的优化技术，同分时寻路。

开放队列：a*算法中的开放队列（open list）。

研究过程

分享文章中讲的很清楚，就是把寻路这件事情拆成好几段，每帧做一段。

在a*算法中，每次会从开放队列中取出一个坐标，我们需要修改这里的代码，限制取坐标的最大数量。

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

分享文章中提到，他们还将寻路任务进行统一管理。当某帧有多个寻路任务时，仍会出现单帧时间过长的问题，所以还是一步到位吧！

一般情况下，同屏npc且需要同时寻路的数量不会特别多，所以我们实现一个队列型的任务管理器即可。

实现思路

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

1. 实现提交寻路任务的入口函数，存储寻路任务相关数据（起点、终点、障碍物等）。
2. 实现寻路函数。

1. 1. 取出需要执行的任务，若任务为空则退出。
   2. 执行一次寻路，判断是否超出最大步数，是则退出，否则循环步骤b。
   3. 若完成寻路，加载下一个的任务。

1. 新建寻路管理类，在游戏中持有寻路管理类，并每帧调用寻路函数。

方案涉及文件

方案涉及类

实现代码解析

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

// 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);
}

实现由外部调用的更新函数，应被每帧调用。持续从开放队列中取出路径点，超出最大每帧寻路次数时停止。

// 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函数中会根据路径在地图上生成若干小圆点。

代码上传于git仓库，有需要可自取。比较简陋，以测试功能为主。

为了方便观察效果，游戏中有一个蓝色方块和一个红色方块，蓝色表示起始位置，红色表示终点位置。另外还有一个‘find’按钮，可以将游戏类update中对于寻路管理类的调用挪到按钮的点击事件中，实现手动模拟分帧的效果（点一下一帧）。

演示项目的地图中，灰色图块表示路，黑色图块表示障碍物。

效果对比

测试案例

一张100*100，方块大小32*32的地图。

同一起点，寻路四次，同一帧内提交任务。起点位于地图右下角区域，四个目标点分别位于地图四个角区域。

文字还是不够直观，上图吧！#狗头

数据为在游戏中统计前三秒（180帧）的寻路函数耗时，耗时并不是精准的，但可以作为参考。横轴为帧，纵轴为寻路函数的耗时，单位为ms。

图中有三条不同颜色的折线，其中：

蓝色：不设置最大寻路次数（将会每帧执行一个寻路任务）。

绿色：设置每帧最大寻路次数为50。

黄色：设置每帧最大寻路次数为100。

可以明显看出，不设置寻路次数时，前4帧的耗时明显偏高。设置最大次数的绿色和黄色曲线相对来说更平缓。

什么？你说没有原始对照组？看着蓝色线想象一下，一帧里发生两个5ms耗时的寻路任务会怎么样🤣。

由于最大寻路次数配置的不同，黄色线大约在80帧左右，耗时逐渐贴近0，绿色线则是在155帧左右。每帧执行多少次比较合适还得结合实际情况进行设置。

总结

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