前言
当项目里的地图越来越大,一些性能上的问题开始逐渐出现,比如寻路。玩家在操控角色移动的时候,指引需要实时更新,同时一些npc也需要做移动,容易出现cpu占用率短时间过高,甚至掉帧的情况。
去年底的时候,由于希望在性能优化方面做一些研究,在论坛找到了江南百景图研发负责人 其中提到了分帧寻路+寻路任务统一管理的优化思路。
针对地图很大、建筑物和人物都很多的情况下,这些算法一起执行就会很损耗性能。所以我们用了 分时寻路 ,就是把寻路过程由一帧分到若干帧去进行计算,这样就不会在某一个时间段集中进行大量运算,对游戏性能也不会有太大的影响。
统一管理寻路任务,同一时间只为一个角色服务。也许有人会问,那岂不是一个角色在哪里走、其他对象都在那边等着?其实真正在游戏里不会有这种奇怪的表现。首先每个角色寻路的起始和结束时间都不一样,再者这个同一时间是非常短的,就等于把角色寻路分配到了不同帧里,交替进行执行。
感觉方案很有意思,便尝试做了出来。寻路算法基于a*实现,只支持四方向移动。a*算法在网上有大量文章,文末贴了一篇文章链接,本文中不会细说。
开发环境
浏览器:Chrome
开发语言:JavaScript
引擎版本:CocosCreator 2.4.3
词语缩写对照
分帧寻路:本文提到的优化技术,同分时寻路。
开放队列:a*算法中的开放队列(open list)。
研究过程
分享文章中讲的很清楚,就是把寻路这件事情拆成好几段,每帧做一段。
在a*算法中,每次会从开放队列中取出一个坐标,我们需要修改这里的代码,限制取坐标的最大数量。
从开放队列取坐标时,需要保证每次取出来的都是最有价值的坐标(离终点最近),地图尺寸过大时, 保证坐标的正确取出也是不可忽视的损耗点。我们可以使用优先队列降低性能损耗,但js中没有内置的实现,所以这里我们还需要实现一个优先队列。
分享文章中提到,他们还将寻路任务进行统一管理。当某帧有多个寻路任务时,仍会出现单帧时间过长的问题,所以还是一步到位吧!
一般情况下,同屏npc且需要同时寻路的数量不会特别多,所以我们实现一个队列型的任务管理器即可。
实现思路
需求可大致拆分为如下步骤:
- 实现提交寻路任务的入口函数,存储寻路任务相关数据(起点、终点、障碍物等)。
- 实现寻路函数。
-
- 取出需要执行的任务,若任务为空则退出。
- 执行一次寻路,判断是否超出最大步数,是则退出,否则循环步骤b。
- 若完成寻路,加载下一个的任务。
- 新建寻路管理类,在游戏中持有寻路管理类,并每帧调用寻路函数。
方案涉及文件
文件名 |
说明 |
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); }
实现由外部调用的更新函数,应被每帧调用。持续从开放队列中取出路径点,超出最大每帧寻路次数时停止。
// 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耗时的寻路任务会怎么样🤣。文章来源:https://www.toymoban.com/news/detail-418500.html
由于最大寻路次数配置的不同,黄色线大约在80帧左右,耗时逐渐贴近0,绿色线则是在155帧左右。每帧执行多少次比较合适还得结合实际情况进行设置。文章来源地址https://www.toymoban.com/news/detail-418500.html
总结
- 大地图下的寻路是不可避免的性能问题,使用分帧寻路可以压平cpu的曲线,避免因为寻路导致的占用率上升甚至掉帧等情况。
- 同时间有多个寻路任务时,将按照队列顺序处理,先进先出。此方法足够满足一般寻路需求,若希望优化任务执行时的优先级,还可以参考cpu调度算法进行优化。
- 项目中把最大寻路次数的配置放到了提交任务时,每个任务可以配置不同的最大次数。也可以直接将次数限制直接写在管理器中。
到了这里,关于性能优化3-分帧寻路+寻路任务统一管理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!