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

这篇具有很好参考价值的文章主要介绍了性能优化3-分帧寻路+寻路任务统一管理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

前言

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

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

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

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

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

开发环境

浏览器:Chrome

开发语言:JavaScript

引擎版本:CocosCreator 2.4.3

词语缩写对照

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

开放队列:a*算法中的开放队列(open list)。

研究过程

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

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

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

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

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

实现思路

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

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

方案涉及文件

文件名

说明

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

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

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

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

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

效果对比

测试案例

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

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

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

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

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

图中有三条不同颜色的折线,其中:

蓝色:不设置最大寻路次数(将会每帧执行一个寻路任务)。

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

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

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

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

由于最大寻路次数配置的不同,黄色线大约在80帧左右,耗时逐渐贴近0,绿色线则是在155帧左右。每帧执行多少次比较合适还得结合实际情况进行设置。文章来源地址https://www.toymoban.com/news/detail-418500.html

总结

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

到了这里,关于性能优化3-分帧寻路+寻路任务统一管理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包