CN101739509A

CN101739509A - 一种大规模虚拟人群路径导航方法

Info

Publication number: CN101739509A
Application number: CN200910260146A
Authority: CN
Inventors: 卢光辉; 罗伟平; 陈雷霆; 谭浩; 蔡洪斌; 何晓曦; 曹跃
Original assignee: University of Electronic Science and Technology of China
Current assignee: University of Electronic Science and Technology of China
Priority date: 2009-12-25
Filing date: 2009-12-25
Publication date: 2010-06-16
Anticipated expiration: 2029-12-25
Also published as: CN101739509B

Abstract

本发明涉及了一种大规模虚拟人群路径导航方法，该方法包括：步骤1，处理静态场景物体，生成“静态局部势能”；步骤2，根据“静态局部势能”，针对每个“目标点”，生成对应的“全局势能场”；步骤3，处理“面”型动态物体，生成“动态局部势能”；步骤4，处理“点”型动态物体，更新“碰撞检测网格”；步骤5，对每个个体，计算得到各种势能作用力，求得最终导航力，并根据最终导航力更新个体状态。本发明的有益效果是：采用静态局部势能场生成全局导航势能，简化了全局势能的运算过程，能够快速对目标点进行全局最优路径导航；将动态物体分类考虑，能够快速进行动态物体间的碰撞避免；群体中的个体采用独立的感知和决策，允许表现多样的行为特征。

Description

一种大规模虚拟人群路径导航方法

技术领域

本发明涉及一种大规模虚拟群体在复杂环境下的路径导航方法，特别涉及一种高效率的多层次局部碰撞避免和全局最优路径寻找方法。

背景技术

群体动画在游戏领域、群体心理学、交通仿真及城市规划等方面有着广泛的应用。然而，实时的群体行为仿真一直是个具有挑战性的课题，这是因为群体行为模型中不仅包含单个角色的运动和环境约束，而且存在个体与个体之间的大量动态交互影响，更为重要的是群体行为必须及时反应动态变化的各种环境。另外，人群不同于动物群体，由于人类智能的复杂性，致使对人群的仿真不得不更多的考虑个体的行为多样性。这使得人群路径导航运算变得异常复杂。特别是在群体规模增大的时候，复杂度将呈非线性增长。

路径导航技术已经被广泛研究，大体上可以将其分为三类：路径图(roadmaps)、单元分解(cell decomposition)和势能场。路径图方法通过路径连接自由空间，表示成网络拓扑图，然后搜索该数据结构从而找到一条行走路径。这种方法一般基于特定的应用，难于对复杂环境进行灵活表示和扩展。单元分解法将自由空间分解成特定单元，从而使用单元间的邻接信息进行路径搜索。这种方法由于要针对每个起点进行复杂的运算，针对大规模人群的寻径难于保证实时效率。势能场方法将环境细分成规则网格，网格单元中存储势能信息。障碍物对其周围的单元产生排斥势能；同时目标点对单元产生吸引势能。只要对势能进行梯度计算，沿着梯度方向行进便能实现目标点导航。基于这种方式的碰撞避免能够灵活反应每个个体的特殊状况及当前环境。然而，对目标寻径存在局部极小值问题，不能保证到达最终目标点。“流群体”方法提出针对特定目标点的耗费势能场计算，将拥塞避免、碰撞避免统一到全局路径规划当中，有效解决了大规模群体的运动，而无需显式的碰撞避免运算。然而，由于要及时对势能场进行更新计算，当目标点个数和势能场表示精度增加时，无法满足实时要求。

发明内容

为了克服现有技术中路径导航技术存在的不足，本发明提供了一种大规模虚拟人群寻径导航方法，提高大规模虚拟群体在复杂环境下的路径导航效率，实现灵活平滑的导航路径。

本发明所采用的技术方案是：

步骤1，处理静态场景物体(如：地形、树木、房屋)，生成“静态局部势能”。

步骤2，根据“静态局部势能”，针对每个“目标点”，生成对应的“全局势能场”。

步骤3，处理“面”型动态物体(如：汽车)，生成“动态局部势能”。

步骤4，处理“点”型动态物体(如：人)，更新“碰撞检测网格”。

步骤5，对每个个体，计算得到各种势能作用力，求得最终导航力，并根据最终导航力更新个体状态。

步骤3到步骤5将循环执行，直到用户要求停止路径导航。

其中，步骤1包括：

步骤1.1：使用地形计算出一个初始的静态势能场。

步骤1.2：使用其他静态对象的包围盒求解其势能影响，并叠加到原有静态势能场上。

进一步地，在步骤2中，将全局网格精度设为局部网格的1/3，构建路径拓扑图，并计算图中每条线段的权值。当完成对每条线段的权值计算后，就可以通过Dijkstra最短路径算法求出整个全局势能场。为了便于计算，在每个网格点上存储一个指向其最近邻接点的向量作为全局路径导航作用力

而不是存储到达目标点A的单独路径，最终求得全局目标导航势能。各个网格顶点上的全局路径导航作用力

构成二维全局势能场G_g。

进一步地，在步骤3中，“面”型动态物体的势能作用力计算与静态物体非常类似，考虑运动物体速度因素的影响，其计算模型稍微进行了些调整。假设考虑速度在s秒内的影响，物体从A点，s秒后运动到B点，其在该过程中所占用的地理面积形成的几何图形记为AB，则该“面”型物体的动态局部势能计算模型即为几何图形AB的静态局部势能计算模型，求得的势能作用力为动态局部势能作用力

具体计算过程如步骤2所示。

进一步地，在步骤4中，“点”型物体(个体)被放入“碰撞检测”网格，网格大小一般取个体的感知半径大小。个体根据其当前所在位置，将其信息索引放入相应格子中。每个个体直接从其附近的格子中获悉周围个体的信息，从而避免复杂的碰撞检测运算。当个体从一个格子走入另外一个格子后，个体从前一个格子中注销，然后注册到另外一个格子中。为了解决个体在网格边缘来回晃动带来的感知“抖动”，采用阀值区域控制的方法，只有超过某个模糊边界后才进行更新。更新步骤如下：

步骤4.1，取得个体之前所在格子，并求得格子中心位置P₁。

步骤4.2，令P₂为个体当前位置，计算个体到该格子中心的距离S，根据S的数值考虑是否需要更新，否则个体从之前所在格子中注销，并根据个体当前位置P₂求得新格子索引，并将信息注册到新格子中。

进一步地，步骤5包括：

步骤5.1，求解个体所受周围其他个体的避免作用力。

步骤5.2，求解个体所受静态局部势能作用力、动态局部势能作用力及全局路径导航作用力。

步骤5.3，求得最终导航力并更新个体状态。

进一步地，在步骤5.2中，设个体所在位置为x，则点x的静态局部势能作用力、动态局部势能作用力及全局路径导航作用力均采用双线性插值方式求得。

进一步地，步骤5.3包括：

步骤5.3.1，根据个体所在的位置计算最终导航力。

步骤5.3.2，更新个体状态。个体状态更新包括个体速度、个体朝向、个体位置更新。

与现有技术相比，本发明的有益效果是：对场景进行预处理，生成静态局部势能场，能够对任意复杂场景进行有效的碰撞避免，碰撞避免运算复杂度与场景复杂度无关；采用静态局部势能场生成全局导航势能，简化了全局势能的运算过程，能够快速对目标点进行全局最优路径导航；将动态物体分类考虑，能够快速进行动态物体间的碰撞避免，碰撞避免复杂度与动态物体数目趋于线性关系；群体中的个体采用独立的感知和决策，允许表现多样的行为特征。

附图说明

图1为本发明所述一种大规模虚拟人群路径导航方法的流程图；

图2为本发明所述求解地形势能的顶点及向量；

图3为本发明所述方形、圆形、线形及其复合体的势能作用方式

图4为本发明所述全局势能的构建过程；

图5为本发明所述动态物体的势能作用方式；

图6为本发明所述碰撞检测网格；

图7为本发明所述双线性插值方式。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合附图对本发明作进一步的详细描述。

该群体路径导航方法主要是通过将事物分类，分层构建各种势能场，最终通过求得各种导航向量并加权叠加求得最终路径方向。系统中场景首先离散为2维网格。在系统运行过程中，步骤3到步骤5将循环执行，直到用户要求停止路径导航。

参见图1所示的流程图给出了本方法的实现过程

在本实施例中，环境采用鬼火引擎(irrlicht)编辑器生成的场景，并转换成能识别的行为对象。同时，加入行人、车辆及各种障碍物等。

步骤1.1：使用地形计算出一个初始的静态势能场。计算方式如下：

如图2所示v1...v8为某网格顶点X周围的八个顶点。将该九个平面顶点垂直映射到地形上，求得3维空间向量

令

\overset{&RightArrow;}{V_{\max}} = Max ({\overset{&RightArrow;}{V}}_{1} . . . {\overset{&RightArrow;}{V}}_{8}),

Max函数表示求出与水平面夹角最大的向量。

\overset{&RightArrow;}{V_{grd}} = \frac{\overset{&RightArrow;}{V_{\max}} * \overset{&RightArrow;}{V_{\max}} . y}{| \overset{&RightArrow;}{V_{\max}} | * \sqrt{\overset{&RightArrow;}{V_{\max}} . x^{2} + \overset{&RightArrow;}{V_{\max}} . z^{2}}};

则该点的地形势能作用力为：

\overset{&RightArrow;}{F} = - λ * \overset{&RightArrow;}{V_{grd}},

其中λ为地形行走难度，例如λ＝0.7。

步骤1.2使用其他静态对象的包围盒求解其势能影响，并叠加到原有静态势能场上。计算方式如下：

采用物体包围盒边沿及其平行扩展作为势能等高线，势能作用力方向垂直几何边缘，参见如图3。作用力大小采用类似库伦力的方式计算。引入两个参数——影响范围δ和影响力度λ。影响范围δ表示几何体对其边界以外周围δ单位以内的点存在影响；影响力度λ表示几何体对影响范围以内的点的影响程度比例参数。设以几何体外部某点P为终点且距离其边缘最短的距离向量为

则该几何体对点P处的势能影响为：

情形1.2.1，当

δ < = | \overset{&RightArrow;}{S} |

且P处于物体外部，则

\overset{&RightArrow;}{F} = 0;

情形1.2.2，当

δ > | \overset{&RightArrow;}{S} |

且P处于物体外部，则

\overset{&RightArrow;}{F} = \frac{\overset{&RightArrow;}{S} * (λ * (δ - | \overset{&RightArrow;}{S} |))}{{| \overset{&RightArrow;}{S} |}^{2}};

情形1.2.3，当P处于物体内部，则

\overset{&RightArrow;}{F} = \overset{&RightArrow;}{S} * \infty .

所有处于几何体边缘或内部的点所受力大小为无穷大；所有处于物体作用范围δ外的点所受力大小为0。图3显示了方形、圆形、线形及其复合体的势能作用方式。

至此，各个网格顶点上的静态局部势能作用力

构成二维静态局部势能场G_s。

步骤2，根据“静态局部势能场”，针对每个“目标点”，生成对应的“全局势能场”。

如图4所示，a图是采用步骤1构建好的静态局部势能场G_s。现要求解对目标点A的全局导航势能。这里将全局网格精度设为局部网格的1/3，构建路径拓扑图(图4b)，图中每条线段的权值采用如下公式计算：

W_XY是线段XY的权值，

是在位置i的静态势能值，因此

表示从点X到点Y的静态势能模值的和，Len(XY)表示从点X到点Y的距离，ω₁、ω₂分别代表局部势能和距离对全局势能的影响权值，例如ω₁＝ω₂＝0.5。

当完成对每条线段的权值计算后，就可以通过Dijkstra最短路径算法求出整个全局势

各个网格顶点上的全局路径导航作用力

构成二维全局势能场G_g。

“面”型动态物体的势能作用力计算与静态物体非常类似，考虑运动物体速度因素的影响，其计算模型稍微进行了些调整。如图5所示，假设考虑速度在s秒内的影响，物体从A点，s秒后运动到B点，其在该过程中所占用的地理面积形成的几何图形记为AB，则该“面”型物体的动态局部势能计算模型即为几何图形AB的静态局部势能计算模型，求得的势能作用力为动态局部势能作用力

具体计算过程如步骤2所示。

记求解到的动态局部势能场为G_d，由各个网格顶点上的动态局部势能作用力

构成。

“点”型物体(个体)被放入“碰撞检测”网格，网格大小一般取个体的感知半径大小。个体根据其当前所在位置，将其信息索引放入相应格子中。每个个体直接从其附近的格子中获悉周围个体的信息，从而避免复杂的碰撞检测运算。如图6所示，处于A点的个体从其所在格子及周围的九个格子中获得个体信息。当个体从一个格子走入另外一个格子后，个体从前一个格子中注销，然后注册到另外一个格子中。为了解决个体在网格边缘来回晃动带来的感知“抖动”，采用阀值区域控制的方法，只有超过某个模糊边界后才进行更新。令θ为区间[0，1]的模糊控制参数(例如θ＝0.5)；S_grid为网格单元大小。更新步骤如下：

步骤4.1，取得个体之前所在格子，并求得格子中心位置P₁。

步骤4.2，令P₂为个体当前位置，计算个体到该格子中心的距离S＝|P₁-P₂|。当S＜(1.0+θ)*S_grid时，无需更新；否则个体从之前所在格子中注销，并根据个体当前位置P₂求得新格子索引，并将信息注册到新格子中。

步骤5.1，求解个体所受周围其他个体的避免作用力。

假设某个体的位置为P_x；速度为朝向为在碰撞检测网格中，从该个体周围的九个格子中读取其他个体的信息。设该个体周围有n个个体，位置分别为P₁...P_n，速度分别为

朝向分别为

则所受周围的第i(i＝1...n)个个体避免作用力

的叠加求解过程如步骤5.1.1到步骤5.1.3所示。fSigma为个体之间的作用范围，例如取fSigma＝1.2，初始时避免作用力

的值为0，步骤5.1.1到步骤5.1.3执行n次，

的最终结果为该个体所受周围的n个个体避免作用力。

步骤5.1.1，求个体间距离向量：

{\overset{&RightArrow;}{S}}_{i} = P_{x} - P_{i} .

若

| {\overset{&RightArrow;}{S}}_{i} | > fSigma,

则对第i个个体的避免作用力计算结束；否则执行步骤5.1.2。

步骤5.1.2，令

为的垂直单位向量；若与夹角小于90度且

与夹角小于45度，则

{\overset{&RightArrow;}{K}}_{i} = {\overset{&RightArrow;}{K}}_{i} * (- 0.5);

步骤5.1.3，令

fTemp = (fSigma - | {\overset{&RightArrow;}{S}}_{i} |) / (| {\overset{&RightArrow;}{S}}_{i} | * | {\overset{&RightArrow;}{S}}_{i} |),

叠加避免作用力：

{\overset{&RightArrow;}{F}}_{a} + = ({\overset{&RightArrow;}{S}}_{i} / | {\overset{&RightArrow;}{S}}_{i} |) * (fLambda * fTemp) + {\overset{&RightArrow;}{K}}_{i} * fTemp,

其中fLambda表示个体间的避免作用强度，例如fLambda＝1.0；

设个体所在位置为x，则点x的静态局部势能作用力、动态局部势能作用力及全局路径导航作用力均采用双线性插值方式求得。如图7所示，

和

分别代表x周围4个网格顶点上的某种势能作用力(静态局部势能作用力、动态局部势能作用力或者全局路径导航作用力)，K为网格大小，m、n分别代表距格子边的距离，则点x的势能作用力为：

{\overset{&RightArrow;}{F}}_{x} = [((K - m) {\overset{&RightArrow;}{F}}_{1} + {\overset{&RightArrow;}{F}}_{2} m_{2}) (K - n) + ((K - m) {\overset{&RightArrow;}{F}}_{3} + m {\overset{&RightArrow;}{F}}_{4}) n] / K

步骤5.3，求得最终导航力并更新个体状态。

步骤5.3.1，个体所在的位置计算最终导航力

其中α、β、γ和

为混合因子，体现的是场景中各种作用力的影响程度，α是个体所受周围的其他个体避免作用力的影响程度因子、β是静态局部势能作用力影响程度因子、γ是全局路径导航作用力影响程度因子，

是动态局部势能作用力影响程度因子，具体值根据个体当前所关心的不同侧重点进行适当调整。例如当个体在等待交通灯时，不需要全局路径导航，则可取α＝0.5、β＝0.5、γ＝0.0和

个体速度

更新：

{\overset{&RightArrow;}{V}}_{a} = {\overset{&RightArrow;}{V}}_{a} + t * η * {\overset{&RightArrow;}{F}}_{all} .

其中t为更新时间间隔，例如t＝2，η为作用力迭代影响程度，例如η＝0.05；

个体朝向

更新：

{\overset{&RightArrow;}{D}}_{a} = {\overset{&RightArrow;}{D}}_{a} + t * ω * {\overset{&RightArrow;}{V}}_{a} / | {\overset{&RightArrow;}{V}}_{a} | .

其中t为更新时间间隔，例如t＝2，ω为转身速度，例如ω＝0.1；

个体位置P_a更新：

P_{a} = P_{a} + t * {\overset{&RightArrow;}{V}}_{a} .

其中t为更新时间间隔，例如t＝2。

本发明不限于上述实施例，对于本领域技术人员来说，对本发明的上述实施例所做出的任何显而易见的改进或变更都不会超出仅以举例的方式示出的本发明的实施例和所附权利要求的保护范围。

Claims

1.一种大规模虚拟人群路径导航方法，其特征在于：该方法包括的步骤如下：

步骤1，处理静态场景物体，生成“静态局部势能”；

步骤2，根据“静态局部势能”，针对每个“目标点”，生成对应的“全局势能场”；

步骤3，处理“面”型动态物体，生成“动态局部势能”；

步骤4，处理“点”型动态物体，更新“碰撞检测网格”；

2.根据权利要求1所述的一种大规模虚拟人群路径导航方法，其特征在于：步骤1还包括：

步骤1.1：使用地形计算出一个初始的静态势能场；

3.根据权利要求1所述的一种大规模虚拟人群路径导航方法，其特征在于：在步骤2中，将全局网格精度设为局部网格的1/3，由静态局部势能场构建路径拓扑图，并计算图中每条线段的权值。

4.根据权利要求3所述的一种大规模虚拟人群路径导航方法，其特征在于：在步骤2中当完成对每条线段的权值计算后，通过Dijkstra最短路径算法求出整个全局势能场。

5.根据权利要求1所述的一种大规模虚拟人群路径导航方法，其特征在于：在步骤4中，“点”型物体被放入“碰撞检测”网格，网格大小一般取个体的感知半径大小。

6.根据权利要求5所述的一种大规模虚拟人群路径导航方法，其特征在于：在步骤4中，个体根据其当前所在位置，将其信息索引放入相应格子中，每个个体直接从其附近的格子中获悉周围个体的信息，从而避免复杂的碰撞检测运算。

7.根据权利要求6所述的一种大规模虚拟人群路径导航方法，其特征在于：在步骤4中，当个体从一个格子走入另外一个格子后，个体从前一个格子中注销，然后注册到另外一个格子中。

8.根据权利要求7所述的一种大规模虚拟人群路径导航方法，其特征在于：在步骤4中，为了解决个体在网格边缘来回晃动带来的感知“抖动”，采用阀值区域控制的方法，只有超过某个模糊边界后才进行更新，更新步骤如下：

步骤4.1，取得个体之前所在格子，并求得格子中心位置；

步骤4.2，取得个体当前位置，计算个体到该格子中心的距离，根据个体当前位置求得新格子索引，并将信息注册到新格子中。

9.根据权利要求1所述的一种大规模虚拟人群路径导航方法其特征在于：步骤5包括以下步骤之一：

步骤5.1，求解个体所受周围其他个体的避免作用力；

步骤5.2，求解个体所受静态局部势能作用力、动态局部势能作用力及全局路径导航作用力；

步骤5.3，求得最终导航力并更新个体状态。

10.根据权利要求9所述的一种大规模虚拟人群路径导航方法，其特征在于：在步骤5.2中，设个体所在位置为x，则点x的静态局部势能作用力、动态局部势能作用力及全局路径导航作用力均采用双线性插值方式求得。

11.根据权利要求9所述的一种大规模虚拟人群路径导航方法，其特征在于：步骤5.3包括：

步骤5.3.1，根据个体所在的位置计算最终导航力；

12.根据权利要求2-11中所述的任一种大规模虚拟人群路径导航方法，其特征在于：步骤3到步骤5将循环执行，直到用户要求停止路径导航。