基于改进JPS算法的电影群体动画全局路径规划

黄东晋, 雷 雪, 蒋晨凤, 陈燕敏, 丁友东

(1.上海大学上海电影学院,上海200072;2.上海大学上海电影特效工程技术研究中心,上海200072)

群体动画是群体行为动画的简称,是模拟在特定环境下一群生物行为的动画.在计算机动画的发展过程中,动画师发现绘制数目众多的个体不仅路径轨迹烦琐又困难,而且工作量大又效率不高.1987年,Reynolds[1]提出的行为动画解决了这个问题,其基本原理是群体的复杂动画可以通过每个个体的简单行为和个体间的交互行为来自动生成.近年来,群体动画在计算机图形学、虚拟现实、公共安全、影视技术等领域应用非常广泛,特别是在电影制作中的应用尤为突出.电影场景中的大规模群体动画能营造出令人震撼的视觉效果,如《魔戒》中的魔兽奇兵、《头号玩家》中的IOI队伍、《复仇者联盟3》中的野兽大军等都给观众留下很深刻的印象.群体动画已经成为现今电影制作中不可或缺的一部分,将群体动画与电影制作相结合的研究也引起了国内外专家学者的高度关注.

目前,电影群体动画制作主要使用Massive,Miarmy等软件来实现,其群体动画制作的路径规划主要是以镜头美感和视觉效果为出发点,多设置为静态路径,因而存在着逼真度较低、路径不连续、动画制作效率低等问题.随着群体动画在电影特效制作领域的应用越来越普遍,只注重电影镜头效果显然是不够的,其制作效率、重用性、智能性等均是当前电影群体动画制作中亟待解决的问题.

基于此,本工作提出了基于改进跳点搜索(jump-point search,JPS)算法的电影群体动画全局路径规划算法.该算法在JPS算法的基础上,可自动全局规划出群体从起点到目的点,且能自动避开障碍物的可编辑的运动路径;可根据群体密度信息,自动调整可编辑的路径节点,生成平滑的路径曲线;可根据密度信息进行路径的动态调整,使得智能体在群体运动过程中自动克服群体间碰撞和群体运动堵塞的问题.

1 相关工作

路径规划问题一直是相关研究领域的热点与难点,目前已应用在无人机[2]、机器人[3]、车辆应急[4]、水下滑翔机测试[5]等领域.例如,Yang等[6]利用多目标生物启发式算法研究了无人机最佳飞行路径规划,将禁用空域、地理位置条件、飞行风险和传感器部署统计等环境信息考虑到路径规划中.该算法在各种实际情况下具有动态环境适应性和高效性.熊慕舟等[7]为模拟行人路径决策过程,提出了双层路径规划系统.该算法能够同时考虑静态和动态环境问题,为仿真模型提供了良好的路径规划.王润芳等[8]采用基于自调整粒子群算法的路径拥堵状态下最优车辆路径挖掘算法,能够有效降低挖掘的复杂程度,缩短车辆行驶时间.

随着群体动画的应用越来越广泛,群体路径规划的研究也日益发展.例如,郑利平等[9]研究了质心约束的容量限制Power图下的覆盖路径规划算法,提出了基于PD-Lloyd算法的两种优化策略,但其路径平滑度和环境避障问题仍有待改善.周颐等[10]提出了虚实融合监控场景中的漫游路径规划算法,但该算法中视点评价的参考深度来自于单幅深度估计算法,与真实深度存在差距.吴云鹏等[11]提出了一种融入情绪模型的人群实时路径规划算法.该算法具有良好的高效性和健壮性,可适用于不同场景下的大规模人群路径规划,但该算法在高密度条件下规划的各个路径均存在拥堵情况.Drake等[12]提出了一种增量移动的路径规划算法,通过牺牲最优性来降低复杂度,实现目标移动情况下的路径实时更新.Devi等[13]受猴子行为及其自然行为的启发,将Monkey算法应用于最优机器人路径规划和开放式车辆路径等优化问题中,以寻找最优解.Liu等[14]进行了基于开放环境的强化人口检测与多出口路径疏散算法设计,完成了对公共场所人口稠密区域的检测,并为其提供疏散通道以便快速疏散.Cao等[15]开展了基于遗传算法的AUV全局路径规划研究,根据自主水下航行器路径规划的特点,可在短时间内为自主水下航行器规划最佳路径.Sumana等[16]基于粒子群优化算法,在动态环境中为任务分配目的实施最近邻搜索方法.该算法能够避免多种类型的碰撞,从而有效地规划最佳路径,处理动态环境.

针对当前电影场景中群体动画路径规划存在的问题,如何在保证群体动画的路径逼真度、制作效率和智能性的同时,很好地解决群体运动堵塞和个体碰撞问题,是本工作主要研究的方向.

2 群体路径规划

2.1 JPS算法

JPS算法是Harabor等[17]提出的一种全局路径规划算法,在保留A*算法框架的同时,进一步优化了A*算法寻找后继节点的操作.JPS算法并不是直接获取当前节点的所有非关闭可到达邻居节点来进行拓展的策略,而是根据当前节点的方向并基于跳点搜索的策略来拓展后继节点,可大大减少搜索空间,提高搜索效率和速度.JPS算法是基于无权重格子,在没有预处理的情况下寻路最快的算法,且占用内存很少.本工作将JPS算法应用在电影群体动画路径规划中,旨在提高群体动画的制作效率.

JPS算法是基于网格寻路的算法,能高效解决寻找起点和终点的全局路径,但实验得出的路径轨迹是线段序列,在位置上是连续的,但在方向偏转时会存在不连续的状况.当遇到障碍物时,虽然能绕过障碍物,但会与障碍物靠得太近,使得智能体在障碍物周围的运动轨迹存在折线、堵塞等问题,如图1所示.

图1 JPS算法寻路图Fig.1 JPS algorithm path finding diagram

2.2 算法优化

本工作主要对JPS算法进行优化,分为路径曲线编辑和群体碰撞避免两个方面.路径曲线编辑是将JPS算法生成的路径节点作为Bezier曲线的控制点,使用Bezier曲线进行路径调整.群体碰撞避免是通过引入群体密度信息来动态改变智能体的运动.

2.2.1 路径曲线编辑

Bezier曲线用一系列数据点和控制点来控制曲线状态,其中数据点确定曲线的起始位置和结束位置,控制点确定曲线的弯曲程度,通用公式为

本工作将Bezier曲线应用到路径规划算法中,采用二阶Bezier曲线对JPS算法进行优化,具体步骤如下:①采用JPS算法对群体路径进行初步规划,将生成的路径节点作为可编辑节点;②对可编辑节点信息进行预处理,确定控制点,生成Bezier曲线,调整路径;③根据Bezier曲线的凸包性来调整生成的Bezier曲线.当障碍物在控制点生成的特征三角形内部时,不需要Bezier曲线调整路径;当障碍物在控制点生成的特征三角形外部时,选择当前跳点和跳点附近的两个节点作为生成二阶Bezier曲线的控制点,生成曲线调整路径(见图2).

图2 可编辑节点判定Fig.2 Edit node decision

2.2.2 群体碰撞避免

在群体动画模拟中,密度信息是群体的一个重要特征,表现了群体运动的合理性.正确合理的模拟才能体现出群体动画的真实性.本工作将群体密度信息作为重要因素引入到路径规划算法的研究中.在自然情况下,智能体在低密度群体中能以较快的速度运动,受其他智能体的影响也较小,并在较短的时间内抵达目标位置;反之,智能体在高密度群体中运动缓慢,容易发生碰撞,从起点到达终点的时间也相对较长.电影场景中的群体动画一般是大规模群体向同一个目标位置运动.由于目标位置相同,会导致群体运动陷入堵塞、相互碰撞的状态,不能很好地实现模拟效果.因此,在电影场景中进行大规模群体动画路径规划时,密度信息尤为重要.

本工作在JPS算法规划好的路径节点上设置群体密度信息,并根据密度信息调整智能体的速度以及运动方向.在初始状态下,设置节点密度值都为0.当智能体进入节点后,则更新节点的密度值,并记录当前的密度值.当节点密度值大于某一个值时,则将当前节点作为障碍物,后继智能体动态地改变其自身路径.在任意时刻t的节点密度值为

式中,ρ0表示上一时刻的节点密度值,∆t表示时间间隔,ρv表示密度信息的变化速度.

分析多种人群密度移动速度模型(如P&M模型、Fruin模型、N&M模型等[18])可知,N&M模型可适用于不同地形条件下的研究.该模型将速度与人群密度用线性关系式表示,并针对不同地形,选取不同的线性系数.本工作采用N&M模型作为参考,设置速度与密度的线性关系式为

式中,k为线性系数,取值0∼1.

综上可知,将密度信息引入全局路径规划中,可使智能体有效避免周围智能体,真实模拟群体间的行为,从而有效地提高了计算效率,使群体运动更加流畅.

3 实验结果与分析

本工作将所提出的群体路径规划算法在Unity游戏引擎上进行仿真实验.硬件环境为Intel(R)Xeon(R)CPU E5-2620 v4@2.10 GHz的处理器,64 GB的内存,NVIDIA TITAN Xp的显卡.软件环境为Unity 2017.3.1f1.本工作通过设计两个实验来验证本算法的有效性:①实验一,优化JPS算法的路径规划仿真实验;②实验二,优化JPS算法在不同群体规模和不同路径长度条件下的应用效果验证.

3.1 实验一

首先,本工作将虚拟场景进行网格划分,设置起点、终点以及障碍物位置.然后,采用本JPS优化算法生成可编辑的路径,并利用Bezier曲线进行路径调整.同时,结合障碍物周围路径节点的密度信息动态改变智能体的速度以及运动方向.

图3为优化前后的路径生成仿真对比结果.可以看出,本工作提出的群体路径规划算法能够很好地解决路径中存在的折线、偏转角度大、不平滑等问题.图4为群体运动过程中的群体避障仿真结果.可以看出,本工作提出的群体路径规划算法能够很好地解决大规模群体的运动堵塞和个体碰撞问题.

图3 路径生成结果对比Fig.3 Comparisons of the path generation results

3.2 实验二

图4 群体避障仿真结果Fig.4 Results of the population density information obstacle avoidance renderings

为了证明优化后的群体路径规划算法在群体动画应用中的有效性,本工作针对本算法在不同群体规模和不同路径长度条件下的应用效果进行了验证.首先,分别设置100,500和1 000人共3个不同规模的群体来进行对比实验,获取JPS算法在场景中生成的可编辑的路径节点.初始化群体密度,针对不同规模群体在障碍物周围的路径节点上对应设置不同的群体密度上限.整个群体运动过程的实验数据如表1所示,对应的群体仿真结果如图5所示.从表1可以看出:不同规模的群体规划路径相同,寻路时间相同;群体规模越大,在障碍点的群体密度就会变大,碰撞次数增加,造成运动堵塞现象(在本实验中设置为当节点群体密度超过规定的上限).智能体根据节点密度信息调整个体的速度及运动方向,这样就降低了避障时的群体平均速度,有效减少了碰撞次数.从实验结果可以看出,本工作提出的群体路径规划算法具有智能性和高效性.

表1 不同群体规模的测试结果Table 1 Test results of the different groups scale

然后,以群体规模为100人为实验对象,分别设置100,500和1 000 m共3个不同路径长度来进行对比实验,结果如表2所示.可见,本算法的寻路效率是高效的,规划的路径越长,寻路时间就越长.3个不同路径长度对应的仿真实验结果如图6所示.可以看出,规划的路径曲线与群体的实际运动路径存在一定的差异性.当路径长度为100 m时,由于路径较短,群体以群聚的运动形式避过障碍点抵达目的地,其路径规划曲线与实际的群体运动效果一致.当路径长度为500和1 000 m时,路径较长,障碍点较多,在群体运动过程中,智能体不断调整个体的运动状态及其运动路径,慢慢形成以队列的形式绕过障碍点抵达终点,其实际运动路径与规划路径存在偏差.实验结果表明,在不同路径长度条件下,本算法都能有效地实现路径规划,很好地实现群体的运动仿真.

图5 不同群体规模的仿真结果Fig.5 Simulation results of the diff erent groups scale

表2 不同路径长度的寻路结果Table 2 Pathfinding results of the different path lengths

图6 不同路径长度的仿真结果Fig.6 Simulation results of the diff erent path lengths

4 结束语

本工作提出了一种新的电影群体动画路径规划算法,能够产生有效的全局路径,逼真地模拟大规模群体运动.在运动过程中能根据群体密度信息解决智能体之间的碰撞,以及运动堵塞等问题,在高密度群体状态下也能有效减少智能体个体的碰撞次数.本算法具有高效、重用等优点,能在不同的电影场景中得到很好的应用.下一步的研究工作是继续完善群体智能路径规划算法,并整合到电影预演系统中,提高电影的摄制效率和质量.