基于差分进化和稀疏A*算法的游戏地图智能寻径方法

齐 燕,常晋义

(1.苏州托普信息职业技术学院 信息技术学院,江苏 昆山 215311; 2.常熟理工学院 计算机科学与工程学院,江苏 常熟 215500)

0 引言

随着人工智能(AI)技术的发展,越来越多的产业与人工智能相结合产生了较好的应用效果,例如：路径规划、计算机视觉、服务式机器人等[1-3]．其中,智能寻径方法[4]因人工智能算法的成熟而受到了越来越多的关注,并成为目前的研究热点．

近年来,游戏行业的发展也将寻径方法带入到了游戏产业,Non-Player Character(NPC)的出现也造成了游戏地图中的智能寻径方法的广泛应用．若想使得NPC角色更加灵活与智能化,游戏设计研究者必须开发一个较好的寻径方法来搜寻最佳路径．较为经典的Dijkstra算法[5]可以较好地完成寻找路径这一任务,但是存在最终路径并非最优路径且算法稳定性较差等问题．Greedy算法[6]也是寻径算法中的一种,该算法通过导出局部最大值或者最小值来寻找最优路径,但Greedy算法只取局部最优,并不需要考虑当前的决定对之后决策的影响,所以尽管Greedy算法给出了接近于最优的结果，但是还不能给出最优路径．目前在游戏地图寻径问题上应用最广泛的是A*算法[7],是采用一种直接搜索的方法来求得静态网络中的最优路径．A*算法通过比较当前路径栅格的8个邻居的启发式函数值F来逐步确定下一个路径栅格,但是无法计算出来存在多个最小值的情况,即不能出现最优解．同时,A*算法当面临地图较大且复杂的时候运行速度较慢,并不能应用到实时场景当中．

为了解决A*算法在游戏地图寻径当中面临的问题,本文提出了一种基于差分进化和稀疏A*算法的游戏地图智能寻径算法,该算法通过对A*算法进行剪枝处理[8-9]去除冗余操作,从而实现实时要求并且通过差分进化算法来提高总体的全局寻优能力．

1 预备知识

1.1 差分进化算法

差分进化算法是一种有效的全局优化方法,主要是基于群体式搜索,然后通过交叉、变异、选择等操作来求得最终的最优解的一种方法．具体如算法1[10]所示.

算法1 Differential Evolution Algorithm，DE

Input:种群:M;交叉因子:D;迭代次数T

t←1

fori-1 toMdo

forj=1 toDdo

end

end

while (|f(Δ)|≥ε)or (t≤T)do

fori=1 toMdo

⟹(Mutation and Crossover)

forj=1 toDdo

end

⟹(Selection)

iff(ui,t)

xi,t←ui,t;

iff(xi,t)

Δ←xi,t;

end

else

xi,t←xi,t;

end

end

t=t+1

end

return the best Δ

1.2 A*算法

A*算法[11]是一种应用在游戏地图中寻找最短路径的较有效的方法,其使用直接搜索方式,并且采用启发式函数来计算终点距离起点的最小代价[12]．A*算法不仅仅在游戏地图寻径当中应用,目前还在智能机器人的最短路径规划以及封闭式场景货车最佳路线的规划中使用[13-15]．代价函数是A*算法中最重要的一步．

定义1V={vi|i∈1,2,…}表示在游戏地图中起点距终点所经过的路径节点集合,vi表示在游戏地图中起点距终点中的某一节点．

定义2 对于节点vn,其代价函数f(vn)可定义如下:

f(vn)=σ(vn)+ρ(vn)

(1)

其中,σ(vn)为起点距离当前节点的实际代价,而ρ(vn)为当前节点距终点的预估代价．

根据定义2可知,代价函数f(vn)也称为距离函数,是启发式函数的一种,在游戏地图寻径中,代价即距离．预估代价ρ(vn)越接近于真实值,其代价函数功能就越强．当ρ(vn)=σ(vn)时,A*算法即变为Dijkstra算法,即通过增加横向节点数目来提高算法的寻径能力,同时,随着横向节点的增多,其运行速度也同样会变慢,使得算法的整体效率变慢．所以如何确定实际代价σ(vn)与预估代价ρ(vn)在总体代价函数f(vn)中的权重是非常重要的．

ρ(vn)必须满足代价真实性原则与代价一致性原则．代价真实性即ρ(vn)的取值不能超过当前节点距目标节点的真实代价．而代价一致性原则要求ρ(vn)满足式(2)所示条件:

ρ(vi+1)+κ(vi,vi+1)≥ρ(vi)

(2)

其中,κ(vi,vi+1)为节点vi距下一节点vi+1的真实代价,而ρ(vi+1)为下一节点vi+1距最终节点的预估代价．

定理1 如果ρ(vi)≤ρ(vi+1)+κ(vi,vi+1),那么距最终节点所有路径f(vn)全部为单调费递增函数．

证明首先假设vi+1为vi的下一个目标节点,则

f(vi+1)=σ(vi+1)+ρ(vi+1)=σ(vi)+σ(vi,vi+1)+ρ(vi+1)≥σ(vn)+ρ(vn)

(3)

A*算法是一个较为经典的寻径问题的解决方案,但是当其应用在游戏地图寻径问题上时,因为游戏地图寻径需要较低的时延,所以其效率与准确率产生了一定的冲突,并不能通过有效的手段来控制在较低的时延下产生较好的路径规划.本文提出了一种基于差分进化和稀疏A*算法的游戏地图AI智能寻径算法来应对此问题．

2 主要结果

在A*算法研究的基础上,使用差分进化方法结合稀疏A*算法来生成最佳游戏地图路径,主要是因为在实际应用场景中,游戏地图中的NPC是实时变化的,角色在线不能完全按照初始路径规划方法来确定唯一路径,需要试试检测当时所在路径点距离终点的动态最佳路径. 所以,建立了一种重规划算法来确定游戏最佳路径,同时考虑了路径的最优性与路径重规划的实时性．由于A*算法耗时较长并不能作为实时的路径重规划算法,为了避免算法搜索空间中的无用中间步骤与节点,对A*算法进行剪枝处理,称为稀疏A*算法．首先,设计了以下稀疏A*算法的代价函数,稀疏A*算法与A*算法相类似,需要同时对实际代价与预估代价设计．具体如下所示.

ρ(vn)为角色P在游戏地图中节点vn处的预估代价

ρ(vn)=w1*Γ(P)

(4)

其中,w为角色P实际代价的权重系数,而Γ为相邻路径距离之和,Γ可由以下计算得到

(5)

其中,Si.i+1为两个相邻节点的距离．

σ(vn)为角色P在游戏地图中节点vn处的实际代价,将其设置为当前节点vn与目标节点vm的欧氏距离,则为

(6)

其中,(xn,yn)为当前节点vn的横纵坐标,而(xm,ym)为目标节点vm的横纵坐标．

所以,稀疏A*算法的总体代价函数f(vn)为

f(vn)=w1*Γ(P)+w2*σ(vn)

(7)

其中,w2为实际代价函数的权重系数．

稀疏A*算法的算法流程如图1所示.

图1 稀疏A*算法的算法流程

根据稀疏A*算法的流程,其具体稀疏A*算法如算法2所示.

算法2 A*Algorithm

Input:Game map data

Set the start and end pointsviandvjof this Path;

Put the inaccessible points in the Close table,and the start points in Open table;

While Current node is not a target point

Calculate cost of all feasible successors

f(vn)=w1*Γ(P)+w2*σ(vn)

Fori=1to total number of reachable grids

If Nodes are in the Open table and cost less

Update Open table

End

Ifnodevinot within Open table

Putvijoin Open table

End

End

Sorting the nodes in the Open table by cost;

If Open table ≠ø

Put node with smallest cost into Close table

Else

No accessible trail

End

End

Output:the best path

稀疏A*算法可以较好地寻找到最优路径,并可以在面临任何突发情况下可以更好地进行重规划,但是稀疏A*算法在游戏地图寻径当中可能陷入局部最优的情况,从而较难发现游戏地图中的全局最优路径.因此,引入差分进化算法来对稀疏A*算法进行优化,通过差分进化和稀疏A*算法相结合,克服了差分进化方法寻径中不能重规划的缺点,同时也加强了稀疏A*算法在寻找全局最优路径上的能力．本文提出的基于差分进化和稀疏A*算法的游戏地图智能寻径算法如算法3所示.

算法3 Game Map Path-Finding Method Based on Differential Evolution and Sparse A*Algorithm

Input:Game map data

Use Differential Evolution to plan an optimal path〈vi,…,vj〉 for an NPC from the start pointvito the goal pointvj;

The NPC advances along 〈vi,…,vj〉,constantly detecting whether NPC has reached the target point as it does so;

If NPC not reach the end

Reprogramming using the sparse A*algorithm;

Else

Statistical optimal path;

Output:the best path

3 仿真实验结果及分析

为了验证本文提出的游戏地图寻径方法的有效性和可应用性,选取山脉地形与城市建筑群地形对本文算法与原稀疏A*算法进行仿真试验,实验所采用的硬件平台与软件环境具体为:CPU:IntelCorei7-9700K;显卡:GTX 2060;内存:16 G;操作系统:Windows 10;仿真软件:Matlab.

在山脉地形上对所提出的算法进行仿真试验.首先在实验中设置NPC的起点与终点,其中,在游戏地图中的起点为(0,0,0),然后将游戏地图寻径的终点设置为(100,100,100)．在实验中,假设该NPC为匀速前进,其速度为3 m/s,图2和图3是稀疏A*算法在游戏地图寻径上的表现,分别为2维平面上的展示和3维实际平面上的展示．

图2 稀疏A*算法在山脉地形上的表现(2维) 图3 稀疏A*算法在山脉地形上的表现(3维)

接下来,将稀疏A*算法在山脉地形上进行仿真试验,同样的,地图中的起点为(0,0,0),终点同样设置为(100,100,100)．图4和图5是本文算法寻径的表现,分别为2维平面上的展示和3维实际平面上的展示．

图4 本文方法在山脉地形上的表现(2维) 图5 本文方法在山脉地形上的表现(3维)

由图2-5可以看出,本文方法相较于稀疏A*算法有着较好的路径规划能力且在遇到山脉等情况时会进行重规划而进一步选取更优的路径．

最后将稀疏A*算法在城市建筑群地形上进行仿真试验.图6-9为稀疏A*算法与本文算法寻径的表现,分别为2维平面上的展示和3维实际平面上的展示．

图6 稀疏A*算法在城市建筑群地形上的表现(2维) 图7 稀疏A*算法在城市建筑群地形上的表现(3维)

图8 本文方法在城市建筑群地形上的表现(2维) 图9 本文方法在城市建筑群地形上的表现(3维)

由图6-9可以看出,本文方法相较于稀疏A*算法在面临城市建筑较多的情况下可以更早地规避城市建筑,具有更优的路径规划．

本文方法是稀疏A*算法的改进算法,因此与稀疏A*算法在性能上进行比较是有必要的．接下来对所提出的算法与稀疏A*算法在运行时间、路径长度和总体代价上进行了对比,表1为本文方法与稀疏A*算法的性能比较,可以看出本文方法所规划出来的路径距离更短,总代价更小．

表1 本文方法与稀疏A*算法的性能对比

4 结语

人工智能技术迅速发展,已经在各方面取得了重要的成就,本文针对A*算法在游戏地图寻径中容易陷入局部最优导致不能找到最优路径,且由于差分进化算法不能进行重规划的问题,提出了一种新的游戏地图AI技术寻径方法.该方法基于差分进化和稀疏A*方法相结合,在游戏地图寻径上取得了较好的结果．仿真实验证明了本文算法相较于稀疏A*算法具有更低的总体代价、更短的路径长度，能够较好地适用于游戏地图的寻径研究．