虚拟场景中有宽度物体移动路径的优化方法

吴拥民,张 斌

(1.闽江学院计算机科学系,福州350108;2.网龙网络有限公司程序研发部,福州350003)

虚拟场景中有宽度物体移动路径的优化方法

吴拥民1,2,张 斌2

(1.闽江学院计算机科学系,福州350108;2.网龙网络有限公司程序研发部,福州350003)

提出一种虚拟场景中有宽度物体移动路径的优化方法,在地图掩码数据经过寻路算法搜索后,得到一组连续路径节点组成的节点集,从起始节点出发,沿着路径节点找出离起始节点最远且没有障碍物遮挡的可见节点,作为下一个起点,循环往复直至节点集的终止节点,并顺序连接这些可见节点,即可得到优化路径。通过合并节点集中的多余节点,使路径更平滑,从而减少物体移动过程中改变方向的次数,解决有宽度物体无法通过狭窄通道后,须重新计算路径的问题,达到了更好的用户体验效果。

虚拟场景;寻路算法;优化方法;有宽度物体;最远可见节点;节点合并

1 概述

随着电子游戏的不断发展,在虚拟的游戏场景中,经常需要实现虚拟物体从一点向另一点移动的功能。在该过程中,要判断是否有可行路线,以及最优路线选择等,这便是寻路过程。寻路算法的基本思路就是图的遍历算法与最短路径算法,遍历算法分为广度优先搜索[1]与深度优先搜索[2],最短路径算法分为非启发式的Dijkstra搜索[3]与启发式的A*搜索[4]。

启发式的A*搜索算法被广泛用于电子游戏中。文献[5]介绍了该算法在网络游戏中的具体实现方法。文献[6]在启发式的A*搜索算法基础上,以Bresenham算法获取直线路径的节点集合,对A*搜索算法的寻路效率提高极为有限。文献[7]在启发式的A*搜索算法基础上,以二叉堆优化A*的开启列表提高了查找速度,并针对大地图采用低密度网格的宏观寻路与高密度网格的微观寻路的分层寻路思路。文献[8]基于分层寻路思路,给出了双层 A*寻路的具体实现方法。文献[9]提出一种基于定位点和路径复用的寻路算法,是在给定的约束条件(静态障碍物环境下)对启发式的A*搜索算法的一种优化,针对游戏中大量移动的角色也可成为障碍物的情形下,则该算法无效。

在游戏场景中,寻路效果的好坏不仅仅是个算法问题,其本质是一种以玩家为中心的体验服务。游戏中具有AI的NPC角色,应该按照玩家意想的状态进行运动,而不是漫无目的地自由运动,尤其是在运动到某个既定的目的地时,不走直线而是不停地变换方向,就会导致玩家感觉失去对NPC的控制能力,整个游戏的用户体验就会受到极大的削弱。

文献[10]试图以一种用户调查的方法理解、审视、定义用户体验,同时提出了很难给出一种通用的用户体验定义。文献[11]从游戏可玩性为切入点来研究MMORPG的用户体验问题。少有文献研究具有良好用户体验的虚拟角色的行为,长期以来高度依赖游戏设计师的理念,改善虚拟角色行为的用户体验。文献[12]为了描述如何创建和解析不舒适的惊险和难忘的体验,从4种基本形式:本能,文化,控制,隐私,研究了不舒适的交互体验。其中控制强调:人机交互准则早就主张,轨迹的控制应回归于用户;也就是说,好的设计是:人控制界面,而不是界面控制人。玩家感觉失去对NPC的控制能力,就是一种典型的用户放弃了控制机器而产生的不适感。因此,减少智能物体在移动过程中的转向次数,不但能提高移动速度,而且能改善用户体验。

文献[1-9]提出的方法都只是以降低时间复杂度为目标,但无法解决游戏场景中,跟玩家高度互动且具有AI的NPC角色,在移动过程出现频繁转向或因通路狭窄而重新计算路径,给玩家带来不好的用户体验的问题。同时,移动路径的重新计算会导致内存占用不规则的涨落,系统空间复杂度变得极为不稳定。为解决这个问题,本文提出一种虚拟场景中有宽度物体移动路径的优化方法。

2 移动路径方法的问题

启发式的A*搜索算法及其各种优化搜索算法都需要一种与地图相关的数据,称为地图数据。地图数据中有一种是将场景划分成多个相同大小的平面方格,每个方格代表一个区域,也称为一个路径节点,每个节点有自己的属性,比如是否为障碍物节点等。每个节点有个中心点,即该平面方格的中心点。称这种地图数据为掩码数据。每个区域可以根据区域编号得到该区域的邻近区域节点。在路径搜索时,寻路算法搜索起始节点的相邻节点,再搜索相邻节点的相邻节点,直至搜索到终止节点,从而得到从起始节点到终止节点的完整路径。这种方式简单实用,被大量运用于2D场景,也适用于较简单且不包含层次关系的3D场景。如图1为含掩码数据的地图,阴影部分格子为不可走区域,即属于障碍物节点,其他格子为可走区域。

图1 含掩码数据的地图

由上文的介绍可以看出,若使用的是掩码地图数据,经过寻路算法搜索之后,将获得一组连续的路径节点,其中,首尾分别为起始节点S和终止节点E,以下简称为节点集。如图2所示,2个中心有正方形的节点分别为起始节点和终止节点,中心有圆点的节点为搜索后获得的节点。理论上,虚拟物体只需沿着这些路径节点的中心点行进就可以到达目的地。

图2 A*寻路算法获得的一组连续路径节点

如果这一组节点数量太多,路径不够平滑,会导致物体在移动过程中频繁变换移动方向,降低移动速度还占用额外存储空间,从而给玩家带来不好的用户体验。

另一方面,游戏中的虚拟物体一般具有宽度属性。若物体有宽度属性,说明该物体有抽象外围轮廓,则该物体在与其他物体相互作用时,在空间中会受该轮廓的影响。若经过一个狭缝区域时,对于无宽度物体,理论上只要有一个无限小的缝隙就可以通过,但对于有宽度物体,狭缝的大小必须满足物体外围轮廓的尺寸才可通过。由于有宽度物体的约束,会导致有宽度物体在不能通过狭缝通路时重新寻路,加剧了不良的用户体验。

3 移动路径的优化方法

虚拟场景中有宽度物体移动路径的优化方法基本思路是:通过合并节点集中的多余节点,让路径更平滑,就可以减少物体移动过程中改变方向的次数,以达到路径优化的效果。具体流程如图3所示。

图3 移动路径优化方法的执行流程

执行流程的步骤如下:

步骤1使用地图掩码数据,经过寻路算法搜索后,得到一个由一组连续路径节点组成的节点集,节点集首尾分别为路径的起始节点S和终止节点E;并检查节点集的数据是否有效。所谓有效是指:节点集首尾分别为路径的起始和终止节点,并且除了起始节点外所有的路径节点与自己的前一个节点在逻辑位置上是相邻的,如图4所示。

图4 节点集中各节点在逻辑上的相邻关系

步骤2先将起始节点S作为判断起点,在所有剩余节点中查找起始节点S可见的最远节点,该最远节点为第一最远节点T1,再将第一最远节点T1作为判断起点查找可见的最远节点,得到第二最远的节点T2,再由第二最远节点T2作为判断起点查找可见的最远节点,得到第三最远节点T3,然后按此规律一直查找下去,直到可见的最远节点为终止节点E为止。所述可见是指有宽度物体在从判断起点到目标节点的途中不会有障碍物;所述可见的最远节点是指离判断起点最远的目标节点。

步骤3将起始节点S,第一最远节点T1,第二最远节点T2,第三最远节点T3,……,终止节点E的中心点顺次连接起来,所得到的连线即为优化路径,如图5所示。

图5 移动路径优化后的最终路径

在步骤2中,查找可见的最远节点采用二分法查找:即先判断离判断起点最远处的节点是否可见,若不可见,则判断该判断起点与该最远处的节点的中间位置节点是否可见,以此规律遍历下去,直到找到该判断起点的可见的最远节点。具体步骤如下:

假设节点集为P,终止节点为Pn,要查找节点Pi(0≤i≤n)能看到的最远节点;

查找开始前,设置t,pass和block3个临时变量:Ppass为当前Pi能看到的最远节点,pass初始值i;Pblock为不能看到的最近节点,block初始值n;Pt为当前要判断能否可见的节点,t初始值n;

判断(Pi,Pt)两点是否可见:若不可见,则block=t,t=pass+(block-pass)/2,返回重新判断(Pi,Pt)两点是否可见;若可见,则当t==n或者t==block-1时,节点Pt为Pi能看到的最远节点;

否则pass=t,t=pass+(block-pass)/2,然后返回判断(Pi,Pt)两点是否可见;

如此反复判断,最终找到Pi能看到的最远节点Pt,如图6所示。

图6 查找可见最远节点的二分查找法流程

在步骤2中,判定可见最远节点的方法是:计算有宽度物体从判断起点到目标节点的移动过程的矩形区域外围,所有位于该矩形区域内的完整节点和部分节点即为扫描节点集,判断该扫描节点集中是否有障碍物节点,若有则不可见,若无则可见,如图7所示。

图7 可见最远节点的判定流程

具体过程如下:

(1)假设物体占地区域长度为横向节点数L,宽度为竖向节点数W,判断起点为节点A,目标节点为节点B。

(2)定位所述有宽度物体的重心节点,计算重心节点的规则,如图8所示,从4个方向到达物体边缘的距离left,top,right,bottom,得到以下数据:

图8 物体重心节点的计算规则

(3)计算有宽度物体移动过程的矩形区域外围,如图9所示,得出该矩形区域的2个对角线顶点所在节点的坐标分别为(minX,minY),(maxX,maxY),其中:

图9 有宽度物体移动过程的矩形区域外围

(4)根据物体上下边缘点轨迹获取扫描节点集,假设节点A与节点B的中心点连接起来直线的方程式为f(x):y=ax+b,在二维空间下,直线形态归纳为以下4种情况:

1)x=b,表示有宽度物体朝水平方向移动,所述矩形区域中的所有节点就是扫描节点集,如图10左边矩形。

2)y=b,a=0,有宽度物体朝垂直方向移动,所述矩形区域中的所有节点就是扫描节点集,如图10右边矩形。

图10 物体水平或垂直移动时的扫描节点集

3)y=ax+b,a＞0,有宽度物体正向倾斜移动,通过A,B两节点的坐标求出a,b的值,设上、下边缘点的轨迹直线分别为ft(x):y=ax+bt,fb(x):y=ax+bb;根据二维数学几何知识可得:bt=b+m,bb=b-n。

根据重心节点在物体中的位置固定,计算得出m与n的值分别为:

通过以上计算,求出直线fb(x)与ft(x)的方程式:

两直线fb(x)与ft(x)中间的区域与步骤2.3中获得的矩形区域的重叠部分即为扫描节点集所在区域,只要横坐标x从minX开始遍历至maxX,依次计算直线fb(x)和ft(x)在该横坐标下的纵坐标为扫描起始纵坐标和扫描终止纵坐标,即可获得所有扫描节点集中的节点,如图11所示。

图11 物体正向倾斜移动时获取的起止纵坐标

4)y=ax+b,a＜0,有宽度物体反向倾斜移动,通过A、B两节点的坐标求出a,b的值,设上、下边缘点的轨迹直线分别为ft(x):y=ax+bt,fb(x):y=ax+bb;根据二维数学几何知识可得:bt=b+m,bb=b-n。

根据重心节点在物体中的位置固定,计算得出m与n的值分别为:m=|a|×(right+0.5)+top+ 0.5,n=|a|×(left+0.5)+bottom+0.5。

通过以上计算,求出直线fb(x)与ft(x)的方程式:

两直线ft(x)与fb(x)中间的区域与步骤2.3中获得的矩形区域的重叠部分即为扫描节点集所在区域,只要横坐标x从minX开始遍历至maxX,依次计算直线fb(x)和ft(x)在该横坐标下的纵坐标为扫描起始纵坐标和扫描终止纵坐标,即可获得所有扫描节点集中的节点,如图12所示。

图12 物体反向倾斜移动时获取的起止纵坐标

(5)对所获得的扫描节点集中的每个节点进行属性判断,只要有一个节点是障碍物节点,则A,B两节点不可见,否则A,B两节点可见。

4 优化方法的评测

优化方法具有如下优点:

(1)基于两点之间线段最短[13]的公理,合并无障碍路径中多余节点的方法是一种高效的最优化方法。

(2)减少了路径节点的数量,从而节省了移动路径节点的内存空间。对比图4与图5可知,优化前的路径节点数量为19,优化后的路径节点数量为5,优化比为4∶1。当虚拟场景中有数万个智能物体在移动时,节省的移动路径节点的内存空间将相当可观。

(3)减少了物体在移动过程中的转向次数,可以提高移动速度。物体每次转向,都会向服务器发送验证信息,根据统计经验,国内网络状况导致的网络延迟,平均每次验证需消耗200 ms左右。因此,有效地减少物体转向次数,可以提高因网络延迟所导致的运行效率。同样对比图4与图5可知,优化前物体在移动过程中的转向次数为10,优化后物体在移动过程中的转向次数为4,优化比为2.5∶1。

优化方法已经在一款商业游戏《英魂之刃》中应用,《英魂之刃》是全球首款次世代MOBA页游,支持跨平台游戏,目前已正式登陆腾讯QQ游戏平台。在短短的5个月测试期间,PCU已经突破5.8万人,日活跃超过25万人,周活跃超过50万人,并且以每周10%增长率递增。《英魂之刃》的每个游戏玩家都会自动带领10个具有AI的NPC角色参与游戏,当游戏玩家增加到一定的数量,会导致NPC角色充斥整个游戏,成为动态的障碍物。《英魂之刃》的游戏服务器有2类:大厅服务器(LPS)与 战斗服务器(BS),都部署在CPU为至强2640虚拟机上。LPS部署的物理机被分割为2台虚拟机,BS部署的物理机被分割为3台虚拟机。

LPS(只有单台虚拟机承载):

1万人,CPU占用8%,内存占用约3 GB;

2万人,CPU占用12%,内存占用约5 GB;

3万人,CPU占用16%,内存占用约7 GB;

5万人,CPU占用20%,内存占用约9 GB。

BS(共计36台虚拟机承载):

1 000人,CPU占用30%,内存占用2.5 GB,每秒平均转向0.57次;

1 300人,CPU占用50%,内存占用3.5 GB,每秒平均转向0.61次;

1 600人,CPU占用75%,内存占用4.5 GB,每秒平均转向0.68次。

以上数据表明,在游戏玩家稳步递增的过程中,服务器内存没有呈现指数级的暴涨,智能物体的移动转向次数相当稳定。商业级的《英魂之刃》应用验证了优化方法的效果,相比较提供理想环境中的测试数据,更具商业与理论双重价值。

文献[12]从4种基本形式:本能,文化,控制,隐私,研究了不舒适的交互体验。其中控制强调:人机交互准则早就主张,轨迹的控制应回归于用户;也就是说,好的设计是:人控制界面,而不是界面控制人。如果理解游戏的本质是一种以玩家为中心的体验服务,那么游戏中具有AI的NPC角色,应该按照玩家意想的状态进行运动,而不是漫无目的地自由运动,尤其是在运动到某个既定的目的地时,不走直线而是不停地变换方向,就会导致玩家感觉失去对NPC的控制能力,整个游戏的用户体验就会受到极大的削弱。这是一种典型的用户放弃了控制机器而产生的不适感。因此,减少移动过程中的转向次数不但能提高智能物体的移动速度,而且能改善用户体验。

5 结束语

本文提出的优化方法本质上也是A*搜索算法的一种改进,与文献[6]中应用Bresenham算法具有相似的思路,但减少了结果集中的节点数量;与文献[8]的分层寻路方法相比,其时间复杂度基本在一个量级上。分层寻路思想的实际是一种3D渲染技术中LOD算法在寻路中的应用,但对数据制作提出了更高的要求,会成倍加大数据制作的成本,而优化方法则不会;文献[9]中基于定位点和路径复用的寻路算法,是一种针对静态障碍物环境下的优化算法,但约束条件太强,其适用情景极为有限,而优化方法适用于静态与动态障碍物环境,具有广谱的效果。

本文方法适合虚拟场景中低速运动且带有AI的NPC角色的移动路径计算,这类NPC角色与玩家的互动强调良好的用户体验。然而优化方法不适合类似汽车、飞机等具有高速运动特征的虚拟物体的移动路径计算,需要作进一步的研究。

[1] 维基百科.广度优先搜索[EB/OL].(2013-03-01). http://zh.wikipedia.org/wiki/%E5%B9%BF%E5% BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7% B4%A2.

[2] 维基百科.深度优先搜索[EB/OL].(2013-03-01).http:// zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4% BC%98%E5%85%88%E6%90%9C%E7%B4%A2.

[3] 维基百科.迪科斯彻算法[Z].2013-03-01.

[4] 维基百科.A*搜寻算法[Z].2013-03-01.

[5] 陈和平,张前哨.A*算法在游戏地图寻径中的应用与实现[J].计算机应用与软件,2005,22(12):118-120.

[6] 王同喜,孙淑霞.基于A*和Bresenham相结合的网络游戏寻路算法设计与实现[J].成都理工大学学报:自然科学版,2007,34(4):456-459.

[7] 詹海波.人工智能寻路算法在电子游戏中的研究和应用[D].武汉:华中科技大学,2006.

[8] 蔡方方,杨士颖,张小凤,等.双层A*算法在游戏寻路方面的研究[J].微型电脑应用,2010,26(1):26-28.

[9] 梁 毅,周 刚.基于定位点和路径复用的大型多人在线游戏寻路寻路算法[J].计算机应用,2010, 30(12):3215-3217.

[10] Law E L C,Roto V,Hassenzahl M,et al.Understanding, Scoping and Defining User Experience:A Survey Approach [C]//Proc.of the 27th International Conference on Human Factors in Computing Systems.New York,USA:ACM Press,2009:719-728.

[11] 陈 东.大型多人在线角色扮演类游戏用户体验研究[D].大连:大连海事大学,2007.

[12] Benford S,Greenhalgh C.Uncomfortable User Experience [J].Communications of the ACM,2013,56(9):66-73.

[13] 百度百科.两点之间线段最短[EB/OL].(2013-05-17).http://baike.baidu.com/view/5187378.htm#1_1.

编辑 顾逸斐

Optimization Method of Moving Path for Object with a Width in Virtual Scene

WU Yong-min1,2,ZHANG Bin2
(1.Department of Computer Science,Minjiang University,Fuzhou 350108,China;
2.Program R&D Department,NetDragon Websoft Inc.,Fuzhou 350003,China)

The optimization path finding algorithm computes a moving path of the object with a width in game scene, which searches a continuous node composed of a node-set from map mask.Starting from the initial node,along the path from start node to find the farthest node and no visible obstacles,as a starting point,move in circles until the termination node set.Then sequentially connect these visible nodes,which can get optimal path.The redundant node with node set, makes the path smooth,reduces the times of changing direction in the process of moving objects,eliminates the object with a width not pass through a narrow channel,needs to re-compute the path problem,which achieves a better user experience.

virtual scene;path finding algorithm;optimization method;object with a width;farthest and visible node;node merging

1000-3428(2014)10-0308-06

A

TP301.6

10.3969/j.issn.1000-3428.2014.10.057

吴拥民(1968-),男,副教授、硕士、CCF会员,主研方向:软件体系结构,分布式系统,游戏引擎;张 斌,助理工程师。

2013-10-06

2013-12-23E-mail:yongminwu@sohu.com

中文引用格式:吴拥民,张 斌.虚拟场景中有宽度物体移动路径的优化方法[J].计算机工程,2014,40(10):308-313.

英文引用格式:Wu Yongmin,Zhang Bin.Optimization Method of Moving Path for Object with a Width in Virtual Scene [J].Computer Engineering,2014,40(10):308-313.