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

news/2024/5/24 11:39:57/

前言

当项目里的地图越来越大,一些性能上的问题开始逐渐出现,比如寻路。玩家在操控角色移动的时候,指引需要实时更新,同时一些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函数中会根据路径在地图上生成若干小圆点。

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

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

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

效果对比

测试案例

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

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

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

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

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

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

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

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

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

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

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

总结

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

http://www.ppmy.cn/news/48141.html

相关文章

java基于mvc的停车收费系统mysql

系统需要解决的主要问题有&#xff1a; (1)车位管理模块 添加车位、查看车位状态、车位信息查询等。 (2)客户信息管理模块 客户基本信息录入、客户信息查询等。 (3)卡业务办理 添加卡信息、查余额查询、卡充值。 (4)车辆信息管理模块 车牌信息录入等。 (5)收费管理 可以调整相应…

<a> 元素相关属性及方法

<a> 元素 <a>元素用来设置链接。除了网页元素的通用接口&#xff08;Node接口、Element接口、HTMLElement接口&#xff09;&#xff0c;它还继承了HTMLAnchorElement接口和HTMLHyperlinkElementUtils接口。 目录 属性 URL 相关属性accessKey 属性download 属性href…

linux及openEuler破解root密码

第一步&#xff1a;开机的时候按键盘的字母 E 键&#xff0c; 进入引导模式 第二步&#xff1a;进入引导模式 &#xff1a;找到linux这一行&#xff0c;按键盘上的end 键&#xff0c;跳转到行尾&#xff0c;输入&#xff1a; init/bin/sh 修改完后&#xff0c;按键盘上的 ctr…

上海车展:比亚迪宋L概念车全球首发,这是要硬扛特斯拉?

纵观2023年的新能源汽车市场&#xff0c;特斯拉可以说当仁不让地成为了全球最为“吸睛”的车企之一。凭借一系列令无数人瞠目结舌的降价举措&#xff0c;特斯拉给全球汽车市场带来了强烈冲击。虽然特斯拉上海工厂已经接近满负荷运转&#xff0c;但是面对雪片般飞来的订单依然供…

python学习——缺失值、重复值处理、排序及替换

文章目录 1 缺失值处理1.1 查看缺失值 df.isnull()1.2 统计缺失值 df.isnull().sum()1.3 删除缺失值 df.drop()1.4 填充缺失值 df.fillna()1.4.1 固定值填充 df.fillna(value)1.4.2 线性插值填充 df.fillna(df.interpolate()) 2 重复值处理2.1 查看重复值 df.duplicated()2.2 筛…

docker简单教程(三)常用操作

docker简单教程&#xff08;三&#xff09;常用操作 文章目录 docker简单教程&#xff08;三&#xff09;常用操作1&#xff1a;查看所有容器列表&#xff1a;docker ps -a2&#xff1a;查看正在运行的容器列表&#xff1a;docker ps3&#xff1a;运行容器&#xff1a;docker r…

测牛学堂:2023软件测试linux和shell脚本入门系列(shell的运算符)

shell中的注释 以# 开头的就是shell中的注释&#xff0c;不会被执行&#xff0c;是给编程的人看的。 shell中的运算符 shell中有很多运算符。 按照分类&#xff0c;可以分为算术运算符&#xff0c;关系运算符&#xff0c;布尔运算符&#xff0c;字符串运算符&#xff0c;文件…

把树莓派改造成无线软路由器(2)-----无线路由器模式(独立无线路由器)

本文目录 1、准备工作2、安装无线AP和管理软件3、设置网络路由3.1、树莓派的无线网络接口IP配置3.2、启用路由和IP伪装3.3、为无线网络配置DHCP和DNS服务 4、确认无线配置5、配置 AP 软件6、运行wifi无线AP 树莓派可用作网络中的一个wifi无线路由器。让使用无线接入的计算机和设…

sqlserver用SQL脚本进行备份和还原操作

--1.1备份数据库脚本 USE [master] GO BACKUP DATABASE [Test] TO DISK D:\Test\Test_20230419.bak GO --1.2还原数据库,注意一定要用NORECOVERY还原备份 USE [master] GO RESTORE DATABASE [Test] FROM DISKND:\Test\Test_20230419.bak WITH FILE 1, MOVE NTest TO ND:\Test…

后缀数组的应用:最长公共子串

题目描述 假设 str1 长度为 N N N&#xff0c;str2 长度为 M M M&#xff0c;求 str1 和 str2 的最长公共子串。 思路分析 示例&#xff1a;str1 “12abcd456”, str2 “7abcd89”&#xff0c;则str1和str2的最长公共子串为 abcd。 注意&#xff0c;子串是连续的。 动…

C. Anna, Svyatoslav and Maps(floyd + 思维)

Problem - C - Codeforces 给你一个有n个顶点的无权图&#xff0c;以及由m个顶点的序列p1,p2,...,pm给出的路径&#xff08;该路径不一定简单&#xff09;&#xff1b;对于每个1≤i<m&#xff0c;有一个弧从pi到pi1。 如果v是p的子序列&#xff0c;v1p1&#xff0c;vkpm&a…

JavaScript有几种数据类型,分别是什么?

在JavaScript中&#xff0c;我们可以分成两种类型&#xff1a;基本类型 复杂类型&#xff08;引用类型&#xff09; 两种类型的区别是&#xff1a;存储位置不同 基本类型主要为以下六种&#xff1a; Number、String、Boolean、Undefined、Null、Symbol 复杂类型/引用类型统称为…

C++ const关键字

参考资料&#xff1a; 【C const的各种用法详解】【const用法深入浅出】 - COS - 博客园 (cnblogs.com) const的基本概念&#xff1a; const名叫常量限定符&#xff0c;用来限定特定变量&#xff0c;以通知编译器该变量是不可修改的。习惯性的使用const&#xff0c;可以避免在函…

PostgreSQL环境搭建和主备构建

目录 1 Windows 上安装 PostgreSQL2 docker安装PostgreSQL2.1 检索当前镜像2.2. 拉取当前镜像2.3 创建挂载文件夹2.4 启动镜像2.5 查看日志2.7 查看进程2.8 使用连接 3 postgresql主从主备搭建3.1 安装好网络源&#xff08;主1.11、从1.12&#xff09;3.2 安装postgresql&#…

Python OpenCV 3.x 示例:1~5

原文&#xff1a;OpenCV 3.x with Python By Example 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 本文来自【ApacheCN 计算机视觉 译文集】&#xff0c;采用译后编辑&#xff08;MTPE&#xff09;流程来尽可能提升效率。 当别人说你没有底线的时候&#xff0c;你最…

一定要会的算法复杂度分析

本文首发自「慕课网」&#xff0c;想了解更多IT干货内容&#xff0c;程序员圈内热闻&#xff0c;欢迎关注"慕课网"&#xff01; 原作者&#xff1a;s09g|慕课网讲师 我们知道面对同一道问题时可能有多种解决方案。自然地&#xff0c;我们会将多种方法进行比较。那么…

同样是测试,朋友到了30k,我才12K,这份测试面试8股文确实牛

程序猿在世人眼里已经成为高薪、为人忠诚的代名词。 然而&#xff0c;小编要说的是&#xff0c;不是所有的程序员工资都是一样的。 世人所不知的是同为程序猿&#xff0c;薪资的差别还是很大的。 众所周知&#xff0c;目前互联网行业是众多行业中薪资待遇最好的&#xff0c;…

Leetcode33.搜索旋转排列数组

搜索旋转排列数组 一、题目描述&#xff1a;二、解决思路和代码1. 解决思路2. 代码 一、题目描述&#xff1a; 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length…

【Unity VR开发】结合VRTK4.0:添加遮蔽追踪器

语录&#xff1a; 恋爱应该是双方扶持对方共同完成自己的目标&#xff0c;而不是虚幻的思想、肤浅的物质、和纸醉金迷的生活。 前言&#xff1a; 遮蔽追踪器&#xff08;Trackers.ObscuranceTracker&#xff09;是基于游戏对象存在或不可见之间切换对象的状态&#xff0c;从而遮…

Ajax超详解(新手入门指南)

文章目录 1. AJAX简介2. 前后端交互3. XHR3.1 XMLHttpRequest对象3.2 获取模拟的后端数据3.3 获取网络数据3.4 使用json-server模拟服务器3.4.1 安装node.js3.4.2 安装并使用json-server 3.5 常见的请求方式3.5.1 GET请求3.5.2 POST请求3.5.3 PUT请求3.5.4 PATCH请求3.5.5 DELE…