（计算机应用技术专业论文）群体行为规划技术的研究与实现.pdf

赳 k 分类号 u d c 洼l 密级 1 8 1 0 g 1 学位论文 群体行为规划技术的研究与实现 ( 题名和副题名) 罗伟平 ( 作者姓名) 指导教师姓名谭浩教授 电壬科撞太堂送都 ( 职务、职称、学位、单位名称及地址) 申请专业学位级别硕士 专业名称计算机应用技术 论文提交日期2 0 1 0 0 4论文答辩日期2 0 1 0 0 5 学位授予单位和日期电壬科撞太堂 答辩委员会主席 评阅人 2 0 1 0 年月日 注1 ：注明国际十进分类法o d e ) 的类号。 - 处 k 独创性声明 删j i j j i j j j l i j j j j j j j i j j j j j j i j i j j i j j j j j j j j j 删 y 18 0 2 5 9 7 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：势曜一日期：z p 年夕脾日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 日期：2 d f 0 丛 k 摘要 摘要 群体动画在计算机游戏、影视动漫、城市建筑规划等很多方面都有着广泛的 应用。然而，对大规模群体行为进行模拟尤其是实时模拟是一件复杂而艰巨的工 作。因为对群体行为的仿真不仅涉及到高层的决策过程，还同时要考虑底层事物 的表示以及事物之间的交互计算。更为麻烦的是，个体与个体之间以及个体与环 境之间的复杂约束关系决定了在群体规模增大的时候，仿真运算复杂度将呈非线 性增长。为此，本文提出构建一个高效的群体行为引擎来解决这一问题。本文首 先讨论了行为系统的设计，然后着重研究了在路径规划算法方面进行改进及系统 实现中使用加速技术来提高系统性能，最后介绍了群体的建模方法以及行为引擎 如何被用来进行快速实现。 构建行为引擎的目的在于简化群体仿真应用的开发过程。它的难点在于如何 对行为仿真中的各种元素进行抽象、组织和融合。本文将行为引擎设计为信息管 理模块、路径规划模块，以及系统控制模块三分部分。每个功能模块的作用和设 计都做了比较详细的讲解。它预置了一些关键算法来提高行为仿真质量，同时也 给用户提供了很好的扩展接口。 路径规划是大规模群体仿真性能消耗的最主要部分。本文提出了一种基于势 能场的实时高效的群体导航方法。该方法将局部势能场与全局势能场相结合，有 效的解决了局部势能场中的极小值问题，同时又避免了全局势能场无法满足局部 灵活性的问题。 并行计算技术是目前最为流行的计算加速方法之一。本文分析了如何对碰撞 避免和行为个体的更新进行适当修改，以适应并行执行。同时介绍了o p e n m p 并 行方案如何被用在行为引擎中实现并行运算。另外，本文探讨了另一种简化运算 的方法l o d 技术，并介绍了它如何用在行为仿真中以简化运算。 最后，本文介绍了群体行为的建模方法，并以交通仿真和室外逃生系统为例， 将重点放在如何利用行为引擎系统进行快速的群体建模实现，同时也作为行为引 擎系统有效性的验证。随后，本文对目前的研究成果进行了总结，并对将来进一 步的工作进行了展望。 关键词：群体行为仿真，行为引擎，路径规划，并行加速，行为l o d ，群体建模。 么 a bs t r a c t i nc o m p u t e r g a m e s ，f i l m sa n du r b a n d e s i g n i n g ，c r o w ds i m u l a t i o nw i t hc o m p u t e r s h a y eaw i d er a n g eo fa p p l i c a t i o n s h o w e v e r , l a r g e - s c a l ec r o w ds i m u l a t i o no fb e h a v i o r , e s p e c i a l l vr e a l t i m es i m u l a t i o n ，i sac o m p l e x a n da r d u o u st a s k 。t h ec r o w ds i m u l a t i o no f b e h a v i o ri n v o l v e sn o to n l yh i g h 1 e v e ld e c i s i o n m a k i n gp r o c e s s ，b u t a l s ot a k i n gi n t o a c c o 僦t h a tt h eb o t t o mo ft h i n g s ，a sw e l la st h ec a l c u l a t i o no ft h ei n t e r a c t i o nb e t w e e n 0 b e c t s t h em o r et r o u b l e s o m ei st h a tt h ec o m p l e xr e l a t i o n s h i p so fo b j e c t sm a k et h e s i 脚【u l a t i o ns h o wan o n 1 i n e a ri n c r e a s ei nc o m p u t a t i o n a lc o m p l e x i t yw i t hc r o w ds i z eg e t l a r g e r t h i sp a p e rp r o p o s e st ob u i l da ne f f i c i e n tb e h a v i o re n g i n et os o l v et h i sp r o b l e m f i r s t ，t h i sp a p e rd i s c u s s e st h ed e s i g n i n go fb e h a v i o rs y s t e m a n d t h e nt h i sp a p e rf o c u s e d o ns t u d y i n ga s p e n so ft h ep a t hp l a n n i n ga l g o r i t h ma n ds y s t e mi m p l e m e n t a t i o nw i t h a c c e l e r a t i o nt e c h n i q u e st oi m p r o v es y s t e mp e r f o r m a n c e f i n a l l y , t h i sp a p e ri n t r o d u c e d 廿l em e t h o d so fc r o w dm o d e l i n ga n dh o wt h eb e h a v i o re n g i n et o b eu s e df o rf a s t i m p l e m e n t i n gi t t h eb e h a v i o re n g i n ea i m st os i m p l i f yt h ed e v e l o p m e n tp r o c e s so fa p p l i c a t i o na b o u t c r o w ds i m u l a t i o n i t sd i f f i c u l t yl i e si nh o wt oa b s t r a c ta n do r g a n i z et h ev a r i o u se l e m e n t s o fs i m u l a t i o n t h i sp a p e rw i l ld i v i d et h ee n g i n ei n t ot h r e ep a r t s ：t h em o d u l eo f i n f o r m a t i o nm a n a g e m e n t ，t h em o d u l eo fp a t hp l a n n i n ga n dt h em o d u l eo fc o n t r o l l i n g e a c h 如n c t i o n a lm o d u l eh a sad e t a i l e de x p l a n a t i o n t h ee n g i n ep r c l o a d san u m b e ro f k e ya l g o r i t h r n st oi m p r o v e t h eq u a l i t yo fs i m u l a t i o n ，a n da l s op r o v i d e sg o o de x t e n s i o n s f o ru s e r s p a t hp l a n n i n gi st h em o s t c o n s u m e dp a r to ft h es i m u l a t i o np e r f o r m a n c e t h i sp a p e r p r o p o s e s ar e a l t i m ea n de f f i c i e n tn a v i g a t i o nm e t h o dw i t hp o t e n t i a l t h em e t h o d c o m b i n e st h el o c a lp o t e n t i a lw i t ht h ee ) o b a lp o t e n t i a l i ti sa ne f f e c t i v es o l u t i o no ft h e m i n i m u mv a l u ep r o b l e mw i t hl o c a lp o t e n t i a l ，w h i l ea v o i d i n g 酉o b a lp o t e n t i a lc a nn o t m e e tt h el o c a lf l e x i b i l i t y p a r a l l e lc o m p u t i n gt e c h n o l o g i e sa l ec u r r e n t l yt h em o s tp o p u l a ro n eo f t h em e t h o d s o fc a l c u l a t i o ns p e e d u p t h i sp a p e ra n a l y z e sh o wt ou s ep a r a l l e lc o m p u t i n gt e c h n o l o g i e s f o rm ec o l l i s i o na v o i d a n c ea n db e h a v i o ro fi n d i v i d u a lu p d a t e s t h ep a p e ra l s o n a b s t r a ( 了r i n t r o d u c e dh o wt ou s eo p e n m pt e c h n o l o g yt od e v e l o pt h ee n g i n ef o rr e a l i z a t i o no f p a r a l l e lc o m p u t i n g i na d d i t i o n ，t h ep a p e re x p l o r e s a n o t h e rm e t h o d o fs i m p l i f i e d o p e r a t i o n l o dt e c h n i q u e s ，a n dd e s c r i b e sh o wi ti su s e di nt h eb e h a v i o rs i m u l a t i o n t o s i m p l i f yt h eo p e r a t i o n f i n a l l y , t h ep a p e rd e s c r i b e st h em e t h o do fm o d e l i n gc r o w db e h a v i o rt oi m p l e r n e n t t r a f f i cs i m u l a t i o na n do u t d o o re s c a p es y s t e m i tf o c u s e so nh o wt oi m p l e m e n tr a p i d l y c r o w dm o d e lw i t ht h ee n g i n es y s t e m i ti sa l s oa sav a l i d a t i o no ft h ee f f e c t i v e n e s so f e n g i n es y s t e m s 。s u b s e q u e n t l y , t h i sp a p e rs u m m a r i z e st h er e s e a r c hr e s u l t sa n dl o o k st o f u r t h e rw o r k k e y w o r d ：c r o w ds i m u l a t i o n ，b e h a v i o re n g i n e ，p a t hp l a n n i n g , p a r a l l e ls p e e d u p ， b e h a v i o rl o d ，c r o w dm o d e l i n g i i i 目录 目录 第一章绪论1 1 1课题研究背景1 1 2国内外研究现状3 1 2 1 群体模型的构建3 1 2 2 环境描述与路径规划一5 l - 2 3 群体行为仿真中的运算加速技术7 1 3课题研究内容和意义8 1 3 1 课题研究内容9 1 3 2 课题创新点9 1 - 4 论文章节组织1 0 第二章群体行为规划介绍1 1 2 1群体行为规划的研究内容1 1 2 2群体行为规划的相关问题1 2 2 3群体行为规划的关键技术1 3 2 3 1 行为设计1 3 2 3 2 碰撞避免1 4 2 3 3 路径导航1 5 2 4 本章小结1 9 第三章群体行为引擎的架构与实现2 0 3 1高层系统框架2 0 3 2 行为子系统框架2 l 3 3各子功能模块设计2 2 3 3 1 信息描述及管理模块2 2 3 3 2 路径规划模块2 5 3 3 3 系统控制模块2 6 3 4 本章小结2 8 第四章基于势能场的路径规划实现2 9 4 1 算法思想2 9 4 2 信息描述3 0 i v 目录 4 3 导航算法3 1 4 3 1 势能场表示及存储3 1 4 3 2 静态局部势能场3 2 4 3 3 动态局部势能3 3 4 3 4 全局势能场3 4 4 4 结果分析3 5 4 5 本章小结3 6 第五章行为系统实现中的加速技术3 7 5 1并行加速技术3 7 5 1 1 可并行性分析3 7 5 1 2 基于o p e n m p 的并行方案实现4 0 5 1 3 优化结果分析4 1 5 2 行为l o d 技术4 2 5 2 1 算法思想4 2 5 2 2 优化碰撞避免4 3 5 3 本章小结4 4 第六章群体行为建模与实现4 5 6 1 群组模型4 5 6 2 决策模型4 7 6 3基于行为引擎系统的实现4 8 6 3 1 行人和车流量仿真4 8 6 3 2 室外群体逃生仿真5 1 6 4实现结果分析5 3 6 4 1 仿真效果5 3 6 4 2 对比分析5 4 6 5 本章小结5 5 第七章总结与展望5 6 7 1本文研究总结5 6 7 2 前景展望5 7 致谢5 8 参考文献5 9 攻硕期间取得的研究成果6 3 v 主要术语表 主要术语表 v l i 图索弓 图索引 图1 1 流群体中的大规模人群运动4 图2 1 群体行为构建过程1 1 图2 - 2 路径图示例15 图2 - 3 基于局部势能场的导航图1 7 图2 4 失效的导航1 7 图2 5 单向绕行18 图2 - 6 提前试探两格子后的路径1 8 图2 7 二次试探后的路径一l9 图3 1 群体动画系统总体结构2 0 图3 - 2 行为控制框架示意图2 l 图3 3 信息管理类图2 2 图3 4 路径规划类关系示意图2 5 图4 1 路径规划算法步骤2 9 图4 2 环境信息组织结构3 0 图4 3 双线性插值3l 图4 - 4 规则几何体的势能作用力示意图3 2 图4 5 梯度计算示意图3 2 图4 6 动态势能作用力3 3 图4 7 碰撞检测网格3 3 图4 8 从做左到右：局部势能分布图路径拓扑图求解到的全局势能3 4 图4 9 导航效果测试3 5 图4 1 0 实际应用截图3 5 图5 1 行为个体更新过程3 9 图5 2 分离出的更新过程( 左图为过程a ，右图为过程b ) 4 0 图5 3 “f o r 并行执行过程4 0 图5 _ 4i d d 示意图4 2 图6 1 群体分组示意图4 5 图6 2 共性与多样性4 6 图6 3f s m 决策树4 7 图6 _ 4f s m 示例图；4 8 图6 5 交通建模决策模型4 9 图6 - 6 交通汽车建模决策模型5 0 图6 7 室外逃生人群建模决策模型5 2 图6 8 交通仿真系统效果图5 3 图6 9 室外逃生仿真系统效果图5 4 v n 表索引 表索引 表3 1 信息管理器接口2 3 表3 - 2 地形接口2 4 表3 3o b j e c t 接口定义2 4 表3 _ 4p a t h e r 接口定义2 6 表3 5a g e n t c o n t r o l l e r 行为接口2 6 表3 - 6v e h i c l e c o n t r o l l e r 接口定义一2 7 表3 7e v e n t c o n t r o l l e r 接口定义2 8 表4 1 行为引擎性能测试3 6 表5 - 1o p e n m p 优化对比4 1 表5 - 2l o d 层次分布4 3 表6 - 1 交通灯属性描述4 9 表6 - 2 交通仿真中的行人接口5 0 表6 3 交通仿真中的车辆接口5 1 表6 _ 4 交通仿真中环境规划接口51 表6 5 地震仿真中的行为个体接口5 2 表6 6 引擎实现对比5 5 v i u 第一章绪论 第一章绪论 群体动画在很多方面都有着广泛的应用。例如：游戏中大量n p c 的自动战斗； 影视动漫中的大规模行军；城市建筑规划中通过模拟危险情况下的人群逃生情况 来衡量安全通道设计的合理性。然而，群体动画模拟一直是计算机动画技术中具 有挑战性的研究课题，涉及计算图形学、人工智能、物理仿真等多个领域。特别 是其中对群体行为的实时仿真，其实时性能要求对于当前的硬件水平来说更是一 大挑战。个体与个体之间以及个体与环境之间的复杂约束关系决定了在群体规模 增大的时候，运算复杂度将呈非线性增长。 基于以上问题，本课题依托“虚拟环境下群体动画实时模型与绘制技术 ( 2 0 0 7 a a 0 1 2 3 2 2 ) ”项目展开，目标是构建一个高效的群体动画行为模拟引 擎模块。本课题将分析并研究实时群体行为中的多种行为规划技术，通过改进和 综合利用这些技术，以较少的计算量实现实时交互，促使行为引擎能够满足各种 实时应用的需要。并对引擎的具体实现进行深入的研究与实现。 1 1 课题研究背景 群体普遍存在于现实世界当中，因此，群体模拟在虚拟现实相关的应用中非 常得到重视。群体动画技术用于通过计算机模拟虚拟的人群和动物群体。近几年， 随着计算机性能的提高，群体动画技术得到了广泛的使用。它被用于影视动漫制 作当中，用来代替真实的演员，模拟大规模的战争场面，从而降低制作成本。例 如冰河世纪和指环王系列电影中都使用了m a s s i v e t l 】商业群体制作软件来 模拟大规模群体场景。由于这些应用不需要太多实时性和交互性要求，因而群体 动画技术在该领域得到了广泛运用。 相对来说，群体动画技术在实时性方面的应用中却仍然较少。一方面是由于 绘制大量逼真的3 d 人物模型和动作需要强大的图形处理单元的支持；另一方面是 由于传统的群体行为仿真无法达到应有的效果和实时性要求。尽管若此，这种状 况正在改变，在某些对运算实时性和交互性要求较强的领域，群体动画技术的需 求开始变的日益迫切起来。主要包括如下几个方向： 1 计算机游戏中的群体动画 电子科技大学硕士学位论文 在当前的计算机游戏中，由于资源、性能和生产方面的昂贵代价，虚拟群体 使用仍然很少。然而，伴随着实时策略游戏( r t s y 7 】) 的流行，情况开始改变。 戏种族的数量和军队的大小很大程度上直接决定了游戏的效果和可玩性。游戏 心的重点转向群体的渲染和行为计算速度，而不再是需不需要群体的问题。 随着网络游戏成为互联网上最具商业前景的新兴产业之一，大规模多人在线 时游戏成为了许多游戏厂商的首选，对实时群体的需求也提升到了一个新的程 。这类游戏往往在一个开阔的地方存在着大量的玩家和一群群的n p c 怪物。如 有效的处理玩家之间，玩家与n p c 之间以及n p c 之间的实时行为交互以及和环 的交互正在成为提升这类游戏质量的瓶颈。事实上，很多网络游戏在开发过程 ，直接忽略了角色间的相互碰撞，并极大简化n p c 群体的处理，有些甚至干脆 不运动。这极大地影响了游戏的真实性，降低了游戏质量。有些玩家甚至戏称 种情况为“打木桩”。可见，实时高效的群体仿真将会对游戏的品质起到非常重 的提升作用。 3 交通仿真与城市建筑规划中的群体动画 交通仿真中，可以通过仿真行人和车辆来对道路的流量进行测试，从而确定 道路宽度和十字路口交通灯设计的合理性。而在建筑的规划中，可以通过模拟发 生火灾或地震等紧急情况下的人群疏散情况来测试建筑布局和安全通道等方面的 设计是否符合要求【4 7 】。不幸的是，由于群体渲染和行为运算方面的昂贵代价，在 当前大多数的建筑数字展示中，我们还只能看到漂亮的“幽灵城市 。 多方面的实际应用需求正在吸引更多的学者进行群体动画技术的相关研究。 而其中最为关键的就是如何有效的处理大规模群体的实时行为仿真。 2 第一章绪论 1 2 国内外研究现状 群体行为的相关研究可以追溯到1 9 世纪末，那时，国外些学者就已经开始 研究集体行为。尽管如此，尝试用计算机模型来模拟人群行为则是在最近才开始 的，很多这方面的工作都是在9 0 年代中期和末期开始的。目前，群体行为研究存 在于计算机图形学、物理学、训练系统、安全科学和机器人技术学等多个领域， 而大致又可分为群体建模、虚拟环境表示、路径规划等方面。 1 2 1 群体模型的构建 群体通常被认为是具有一组共同特性的个体集合。对群体行为模型的研究， 从控制层次上看，可以分为如下三类： 1 基于全局控制的自顶向下方法 这种方法将个体看作简单的粒子，通过对整个群体应用运动规则来表现群体运 动效果。粒子系统首先用于制作火、烟雾和爆炸等计算机动画特效，由r e e v e s 2 3 】 于1 9 8 3 年首先提出。文献【2 】首先借用粒子系统思想，并使用动力学来模拟群体运 动。c r a i gr e y n o l d s 的b o i d s l 3 】系统首次完整指出了一个群体行为的控制规则。中心 吸引力、速度跟随和相互排斥力为其三条约束群体运动的规则。该模型能够很好 的表现群体的运动方式，成为群体模拟常用模型之一，常常被用来模拟成群飞鸟、 以及羊群等。但由于b o i d s 系统约束过于简单，并没有考虑群体之外的环境因素， 很少被用于对大规模人群进行模拟。由于人群运动和流体运动之间很多地方比较 相识，流体的运动方式也常用于模拟人群运动。h u g h e s 2 4 将流体力学应用于群体， 将人群描述成一个连续的密度场模型，并通过一对微分方程来构建人群的动力学， 然后通过一个扩展的势能函数驱动人群运动，以使人群向达到人群密度最佳的状 态移动。最近发表于s i g g r a p h 上的一篇称为流群体 1 0 的文章扩展了这一思想。 它通过人群分布来构建群体密度场，用密度场来决定每个个体的运动速度。然后 通过距离、时间、地形不适度等因素来构建微分方程，最后构建基于目标点最小 耗费的全局势能场，从而驱动人群的运动。该模型的主要特点是将碰撞避免、拥 塞避免、全局寻径等多种复杂运算统一了起来。图1 1 展示了基于流群体的大规 模人群运动仿真。 3 电子科技大学硕士学位论文 图1 - 1 流群体中的大规模人群运动 基于全局控制的群体模型有着很多优点。首先，运算比较简单，能够通过较 少的代价模拟出较为真实的群体运动特征，比较适合于模拟较大规模群体运动。 其次，全局控制方式能够方便地对群体的整体特征进行处理，例如群体的全局最 优路径控制。尽管如此，由于全局控制方式将规则应用于整个群体，因此缺少表 征多样个体的灵活性。另外，由于这些规则通常来自于对现实群体观察认知的结 论。因此，无法将该模拟系统用来研究未知的群体行为表现。 2 基于智能代理控制的自底向上方法 和基于全局控制的方法完全不同，基于个体控制的方法试图通过精确模拟每 个个体的智能行为，将多个具有某些共同特征和联系的智能个体放在一起，让它 们之间相互竞争、合作、交流与通信，通过个体之间相互交互作用，从而涌现形 成群体特征。这种方式通常被称为基于代理( a g e n t ) 的群体模型。 文献【4 】通过模拟具有感觉能力的行动者，组成群体分布行为模型，并使用该 模型来模拟行人移动，用以研究人群的社会行为。h e l b i n g 5 】等人提出了局部规则 ( 1 0 c a lr u l e s ) 的概念，用以控制集体行为。涂晓嫒博士【7 】结合分布式人工智能学 科的智能体( a g e n t ) ，进一步将“人工生命”的理论方法用于对群体行为的仿真， 提出了基于人工生命理论的计算机行为动画方法。该方法指出个体以“代理( a g 饥t ) 一 4 第一章绪论 实现自主感知，具有人工视觉和感知环境的能力。该模型可以生动逼真的模拟鱼 的行为。人工鱼作为自治智能个体，由生物力学模型、感知模型、动机模型和行 为选择机制共同构成。人工鱼有饥饿，性欲和恐慌等状态，其基本行为有进食、 避障、交配、逃跑等。人工鱼模型根据内部状态和外部环境，通过一系列的优先 级规则集来选择基本行为，实现鱼的捕食、繁衍、群集、逃逸等生物活动，从而 组成了一个生动逼真的海洋生态系统。此后，基于代理的方式在生物学研究、集 群研究以及虚拟社会等方面得到了广泛的采用。 基于智能代理的行为模拟是最为自然的群体建模方法，它试图通过模拟群体 形成的本质来构建行为动画。然而，由于个体智能的复杂性，虚拟代理方式往往 工作在大型计算工作站中，并不适合于游戏娱乐等实时性要求较强的普通计算机。 3 基于多层次控制的综合方法 近些年来，随着计算及性能的进一步提高，研究的重点趋向于解决大规模人 群对动态环境的实时交互问题。虚拟代理方式运算量过大，不适合大规模人群实 时仿真。而基于全局的粒子系统方法却又缺少个体灵活性。为此，人们试图综合 两者的优缺点，同过在不同粒度层次上进行控制，减少运算量，提出了多层次群 体控制的方法。 “【1 2 】等人提出了一种领导者跟随者的简化群体模型，通过只对领导者执行某 些复杂运算，例如全局路径规划，从而降低系统开销。文献 8 则在一个交互式的 虚拟环境下，构建出了很多运动的自治的虚拟人，这些虚拟人的运动通过多种层 次进行控制。s o r a i a 6 】采用类似的方法，对群体层次分组进行进一步的抽象和扩展， 从而建立了v i c r o w d 模型。该模型系统地抽象了人群行为，划分并定义了群体不 同的属性、行为层次和控制层次。该模型定义了虚拟人三个不同层次的集合：群 体( c r o w d ) 、团队( g r o u p ) 和个体( a g e n t ) 。不同的行为运算作用于不同的层次， 最终共同组成群体行为。v i c r o w d 模型会受到场景、情节和群体行为模式等因素的 限制，是比较通用的群体行为运动建模方法。但是v i c r o w d 模型目前来说还仅仅 是群体运动模型的一个框架，其框架中的每一个层次都有待进一步的充实和完善。 1 2 2 环境描述与路径规划 环境描述和路径规划两者之间紧密相关。虚拟环境的数据结构的建立很多时 候是为了便于路径规划算法的实现。而环境信息除了用于寻径之外，还用于群体 5 电子科技大学硕士学位论文 决策时与环境间的交互。因此，有时为了满足交互需求，又需要对路径规划相关 算法进行改进。 1 2 2 1 环境信息表示 环境信息描述和行为决策紧密相关，环境模型的目的就是促使群体与环境进 行很好的交互。环境一致的行为将大大提高群体行为的逼真度，相反，一个有悖 常理的运动( 例如：穿墙、在水面行走等) 将降低影响仿真效果。 很多研究工作关注于如何构建真实的环境模型，避免那些“违规行为 的发 生。文献 9 提出了i m p r o v 系统，该系统在环境构建中预先定义好了行动者的交 互行为。f a r e i l c 【1 3 】等构建了一个综合信息环境模型( i n f o r m e ae n v i r o n m e n t ) ，用以 模拟都市环境中的群体运动仿真。该模型将各种环境语义和几何信息抽象成环境 实体( 例如：住处、街道、交叉路口等) ，并在实体中存储满足该特定环境下的可 能行为( 例如：街道一走、椅子一坐) 。t h o m a sa n dd o n i k i a n 1 4 】提出了另一种用于 行为规划的城市环境模型。该模型的重点在于仿真交通环境中的汽车和行人。该 模型包含一个区域树和路径网络拓扑结构图。区域中包含有方向信息，以及在交 叉路口可能的转向。s u n g ”】等人采用称为境况( s i t u a t i o n s ) 的数据结构来将行为 信息与环境进行联系。在同一地点可以允许多种境况进行叠加，然后选择符合该 叠加境况总和的行为进行运动。 另一方面，很多环境信息描述直接和路径规划紧密相关。文献 1 6 】将环境描述 成由简单几何多边形组成，用于快速的寻径及碰撞检测。文献 1 8 贝j j 将环境描述成 细小规则网格，每个格子中代表当前位置是否可以行走。 9 1 0 】进一步将环境描述 成具有耗费数值的网格，每个格子中存储的是当前位置行走的不适度，从而便于 利用微分方程求解全局势能场。 对环境的描述很多时候并不局限于一种方法，为了达到不同的计算目的和需 求，我们常常可以综合利用多种方式对其进行多层次描述。 1 2 2 2 路径规划 完整的路径规划通常包括碰撞避免和路径寻找两部分，在避免行走过程中碰 撞周围的障碍物和其他行人的同时，必须有效的朝着目标点行进。在机器人技术 和行为动画领域，路径规划已经被广泛研究，大体上可以将其分为三类：路径图 ( r o a d m a p s ) 、单元分解( c e l ld c c , o m p o s i t i o n ) 和势能场。 路径图方法通过路径来连接可行走的自由空间，表示成网络拓扑图，然后搜 6 第一章绪论 索该数据结构从而找到一条行走路径。例如可视顶点图法( v i s i b i l i t yg r a p h ) 和 v o r o n o i 图法等。 单元分解法将自由空间分解成特定单元，从而使用单元间的邻接信息进行路 径搜索。k a l l m a n n 1 6 】等人提出了一种快速路径规划算法，该方法使用基于完全的 动态局限性的d e l a u n a y 三角测量。d 1 8 】等人则使用了一种改进的a 宰算法，用于 在由高度图表示的地形网格上进行快速路径规划。 势能场方法将环境细分成规则网格，网格单元中存储势能信息。障碍物对其 周围的单元产生排斥势能；同时目标点对单元产生吸引势能。只要对势能进行梯 度计算，沿着梯度方向行进便能实现目标点导航。a d e l a t 2 2 】等人改进m i h o k o n i i t s u m a t 2 1 】的库伦力形式的势能场计算，使a g e n t 问的避免能够灵活反应每个个体 的特殊状况及当前环境。然而，基于势能场的寻径方式存在局部极小值问题，不 能保证到达最终目标点。尽管“侧滑力 和“沿边走 策略被提出用于解决此问 题。仍然，势能场的信息局部性特征无法保证全局最优寻径，从而使群体路径行 为显得“笨拙 。文献【1 0 结合环境中的各种路径影响因素( 拥塞程度、路径长 度等) ，提出针对特定目标点的耗费势能场计算，将拥塞避免、碰撞避免统- n 全 局路径规划当中，有效解决了大规模群体的运动，而无需显式的碰撞避免运算。 文献【1 1 】采用了类似的路径规划算法，不同的是其仅将该方法用于全局导航，而将 局部避免单独分离出来，使得群体的一致性和个体差异得到很好的平衡。 1 2 3 群体行为仿真中的运算加速技术 除了群体模型和相关算法的改进，一些较为通用的运算加速技术和思想同样 开始被研究用于群体行为的仿真实现。 1 2 3 1 运算并行化 随着计算机硬件结构向着多处理并行化发剧”1 1 4 0 ，计算机软件中的并行加速 技术开始成为研究热点。群体行为运算中，每个个体更新的相对独立性很好地适 合于对其进行并行处理。 图像处理单元( g p u 【4 1 1 ) 是一个高并行的运算硬件，通常用于进行图形成像运 算处理。然而，g p g p u 3 8 】技术被用来将g p u “改造 用于更为通用的并行运算。 早些时候就有人通过g p u 运算来实现b i o d s 系统。s h o p f 1 1 】等人采用g p u 并行 运算成功对上万规模的群体行为进行了仿真。实现中采用了“流群体【l o 】”的相关 算法并进行了并行化改进。所有的群体信息数据和运算结果都以纹理的方式存储。 7 8 第一章绪论 1 3 1 课题研究内容 本课题的重点在于解决动态环境中对大规模群体的仿真运算量过大的问题。 目标是实现一个高效的群体动画行为模拟引擎模块。支持大量个体( 上千个) 的 群体行为实时模拟，支持可供研究级别的行为逼真度，为具体群体模型的实现提 供一个灵活高效的调用接口。本课题首先对群体行为引擎的架构进行了研究与实 现，然后着重讨论了实现中采用的相关加速技术、环境信息表示及路径规划方法， 并细致介绍了该行为引擎如何被应用于对特定群体进行建模和实现。主要包括如 下工作： 1 研究并实现一个灵活统一的行为引擎架构。抽象各类行为实体并进行合理 的结合，以使行为引擎很好地融合多种行为影响因素，方便的应用于各类 群体仿真中。 2 研究并实现行为引擎中环境信息表示和路径规划相关算法。使用多层次的 信息描述并利用全局规划和局部规划相融合的方法，解决众多个体之间的 交互及虚拟世界中快速查询的问题，以使行为引擎满足仿真大规模群体的 需要。 3 探索行为引擎实现中的相关加速方法。使用o p e n m p t 4 5 】对行为引擎中的并 行加速进行实现。并使用行为l o d 技术对碰撞避免算法进行加速处理。 4 讨论行为引擎如何用来对群体模型进行实现。实现了城市交通和大型剧场 环境下大规模人群的仿真，用以演示相关研究及实现成果。 1 3 2 课题创新点 本文的主要创新点在于： 1 提出并实现了适用于多种不同行为模型的行为架构。不同于以往基于特定 应用的行为建模，本文抽象并提取群体行为建模和实现的各个步骤，为特 定应用模型提供一个有效的行为引擎，避免了重复的工作，提高了群体行 为实现效率。 2 采用多层次模型的动态势场信息分发，将多种信息进行分类分层表示和更 新控制，有效地减小了群体行为规划的计算量，适应了实时计算的需要。 3 提出了一种适合于大规模群体的路径导航方法。该方法将基于局部势能场 的碰撞避免与基于全局势能场的目标导航有效结合。全局势能场建立在局 部势能场之上，节省了运算量。 4 分析了行为模拟中的可并行化过程，采用o p e n m p 对行为引擎实现进行并 9 电子科技大学硕士学位论