群体行为规划技术的研究与实现
|
摘要
群体动画在计算机游戏、影视动漫、城市建筑规划等很多方面都有着广泛的应用。然而,对大规模群体行为进行模拟尤其是实时模拟是一件复杂而艰巨的工作。因为对群体行为的仿真不仅涉及到高层的决策过程,还同时要考虑底层事物的表示以及事物之间的交互计算。更为麻烦的是,个体与个体之间以及个体与环境之间的复杂约束关系决定了在群体规模增大的时候,仿真运算复杂度将呈非线性增长。为此,本文提出构建一个高效的群体行为引擎来解决这一问题。本文首先讨论了行为系统的设计,然后着重研究了在路径规划算法方面进行改进及系统实现中使用加速技术来提高系统性能,最后介绍了群体的建模方法以及行为引擎如何被用来进行快速实现。
构建行为引擎的目的在于简化群体仿真应用的开发过程。它的难点在于如何对行为仿真中的各种元素进行抽象、组织和融合。本文将行为引擎设计为信息管理模块、路径规划模块,以及系统控制模块三分部分。每个功能模块的作用和设计都做了比较详细的讲解。它预置了一些关键算法来提高行为仿真质量,同时也给用户提供了很好的扩展接口。
路径规划是大规模群体仿真性能消耗的最主要部分。本文提出了一种基于势能场的实时高效的群体导航方法。该方法将局部势能场与全局势能场相结合,有效的解决了局部势能场中的极小值问题,同时又避免了全局势能场无法满足局部灵活性的问题。
并行计算技术是目前最为流行的计算加速方法之一。本文分析了如何对碰撞避免和行为个体的更新进行适当修改,以适应并行执行。同时介绍了OpenMP并行方案如何被用在行为引擎中实现并行运算。另外,本文探讨了另一种简化运算的方法——LOD技术,并介绍了它如何用在行为仿真中以简化运算。
最后,本文介绍了群体行为的建模方法,并以交通仿真和室外逃生系统为例,将重点放在如何利用行为引擎系统进行快速的群体建模实现,同时也作为行为引擎系统有效性的验证。随后,本文对目前的研究成果进行了总结,并对将来进一步的工作进行了展望。
In computer-games, films and urban-designing, crowd simulation with computers have a wide range of applications. However, large-scale crowd simulation of behavior, especially real-time simulation, is a complex and arduous task. The crowd simulation of behavior involves not only high-level decision-making process, but also taking into account that the bottom of things, as well as the calculation of the interaction between objects. The more troublesome is that the complex relationships of objects make the simulation show a non-linear increase in computational complexity with crowd size get larger. This paper proposes to build an efficient behavior engine to solve this problem. First, this paper discusses the designing of behavior system. And then this paper focused on studying aspects of the path planning algorithm and system implementation with acceleration techniques to improve system performance. Finally, this paper introduced the methods of crowd modeling and how the behavior engine to be used for fast implementing it.
The behavior engine aims to simplify the development process of application about crowd simulation. Its difficulty lies in how to abstract and organize the various elements of simulation. This paper will divide the engine into three parts: the module of information management, the module of path planning and the module of controlling. Each functional module has a detailed explanation. The engine preloads a number of key algorithms to improve the quality of simulation, and also provides good extensions for users.
Path planning is the most consumed part of the simulation performance. This paper proposes a real-time and efficient navigation method with potential. The method combines the local potential with the global potential. It is an effective solution of the minimum value problem with local potential, while avoiding global potential can not meet the local flexibility.
Parallel computing technologies are currently the most popular one of the methods of calculation speedup. This paper analyzes how to use parallel computing technologies for the collision avoidance and behavior of individual updates. The paper also introduced how to use OpenMP technology to develop the engine for realization of parallel computing. In addition, the paper explores another method of simplified operation - LOD techniques, and describes how it is used in the behavior simulation to simplify the operation.
Finally, the paper describes the method of modeling crowd behavior to implement traffic simulation and outdoor escape system. It focuses on how to implement rapidly crowd model with the engine system. It is also as a validation of the effectiveness of engine systems. Subsequently, this paper summarizes the research results and looks to further work.
构建行为引擎的目的在于简化群体仿真应用的开发过程。它的难点在于如何对行为仿真中的各种元素进行抽象、组织和融合。本文将行为引擎设计为信息管理模块、路径规划模块,以及系统控制模块三分部分。每个功能模块的作用和设计都做了比较详细的讲解。它预置了一些关键算法来提高行为仿真质量,同时也给用户提供了很好的扩展接口。
路径规划是大规模群体仿真性能消耗的最主要部分。本文提出了一种基于势能场的实时高效的群体导航方法。该方法将局部势能场与全局势能场相结合,有效的解决了局部势能场中的极小值问题,同时又避免了全局势能场无法满足局部灵活性的问题。
并行计算技术是目前最为流行的计算加速方法之一。本文分析了如何对碰撞避免和行为个体的更新进行适当修改,以适应并行执行。同时介绍了OpenMP并行方案如何被用在行为引擎中实现并行运算。另外,本文探讨了另一种简化运算的方法——LOD技术,并介绍了它如何用在行为仿真中以简化运算。
最后,本文介绍了群体行为的建模方法,并以交通仿真和室外逃生系统为例,将重点放在如何利用行为引擎系统进行快速的群体建模实现,同时也作为行为引擎系统有效性的验证。随后,本文对目前的研究成果进行了总结,并对将来进一步的工作进行了展望。
In computer-games, films and urban-designing, crowd simulation with computers have a wide range of applications. However, large-scale crowd simulation of behavior, especially real-time simulation, is a complex and arduous task. The crowd simulation of behavior involves not only high-level decision-making process, but also taking into account that the bottom of things, as well as the calculation of the interaction between objects. The more troublesome is that the complex relationships of objects make the simulation show a non-linear increase in computational complexity with crowd size get larger. This paper proposes to build an efficient behavior engine to solve this problem. First, this paper discusses the designing of behavior system. And then this paper focused on studying aspects of the path planning algorithm and system implementation with acceleration techniques to improve system performance. Finally, this paper introduced the methods of crowd modeling and how the behavior engine to be used for fast implementing it.
The behavior engine aims to simplify the development process of application about crowd simulation. Its difficulty lies in how to abstract and organize the various elements of simulation. This paper will divide the engine into three parts: the module of information management, the module of path planning and the module of controlling. Each functional module has a detailed explanation. The engine preloads a number of key algorithms to improve the quality of simulation, and also provides good extensions for users.
Path planning is the most consumed part of the simulation performance. This paper proposes a real-time and efficient navigation method with potential. The method combines the local potential with the global potential. It is an effective solution of the minimum value problem with local potential, while avoiding global potential can not meet the local flexibility.
Parallel computing technologies are currently the most popular one of the methods of calculation speedup. This paper analyzes how to use parallel computing technologies for the collision avoidance and behavior of individual updates. The paper also introduced how to use OpenMP technology to develop the engine for realization of parallel computing. In addition, the paper explores another method of simplified operation - LOD techniques, and describes how it is used in the behavior simulation to simplify the operation.
Finally, the paper describes the method of modeling crowd behavior to implement traffic simulation and outdoor escape system. It focuses on how to implement rapidly crowd model with the engine system. It is also as a validation of the effectiveness of engine systems. Subsequently, this paper summarizes the research results and looks to further work.
引文
[1] Massive software, www.massivesoftware.com, 2006
[2] Bouvier E., Cohen E., and Najman L.. From crowd simulation to airbag deployment: particle systems, a new paradigm of simulation. Journal of Electronic Imaging,1997, 6(1):4-107.
[3] Reynolds C.. Flocks, Herds and Schools: A Distributed Behavioral Model. SIGGRAPH, Computer Graphics, Vol.21, 1987.
[4] Mataric M. J.. Learning to Behave Socially, in D. Cliff, P.Husbands, J.-A. Meyer & S.Wilson,eds. From Animals to Animats: International Conference on Simulation of Adaptive Behavior, 1994, 453-462.
[5] HELBING D., MOLNáR P., AND SCHWEITZER F.. Computer simulations of pedestrian dynamics and trail formation. Evolution of Natural Structures, 1994, 229-234.
[6] Musse S.R. and Thalmann D.. A Behavioral Model for Real Time Simulation of Virtual Human Crowds. IEEE Transactions on Visualization and Computer Graphics,2001, 7(2):152-164.
[7] Xiaoyuan Tu and Demetri Terzopoulos. Artificial fishes: physics, locomotion, perception, behavior. SIGGRAPH’94: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, 1994,43-50.
[8] Blumberg B.M. and Galyean T. A.. Multi-level direction of autonomous creatures for real-time environments. Proceedings of SIGGRAPH 95, 1995.8,47-54.
[9] Perlin K. and Goldberg A.. IMPROV: A system for scripting interactive actors in virtual worlds. Proceedings of SIGGRAPH 96, 1996.8, 205-216.
[10] TREUILLE A., COOPER S. AND POPOVI? Z.. Continuum Crowds. ACM Trans. Graph, 2006,1160-1168.
[11] Shopf J., Barczak J., Oat C. and Tatarchuk. March of the Froblins: Simulation and Rendering Massive Crowds of Intelligent and Detailed Creatures on GPU. ACM SIGGRAPH, 2008.
[12] LI T.Y., LENG Y.J., AND CHANG S.I.. Simulating virtual crowds with a leader-follower model. In Proceedings of Computer Animation Conference, 2001.
[13] Farenc N., Boulic R., Thalmann D.. An informed environment dedicated to the simulation of virtual humans in urban context. In Eurographics’99, Scopigno R. (Eds.),Vol.18, 1999,309-318.
[14] Tecchia F. AND Chrysanthou Y.. Real-time rendering of densely populated urban environments. In Eurographics Workshop on Rendering Techniques 2000, Springer-Verlag,2000, 83-88.
[15] Sung M., Gleicher M. AND Chenney S.. Scalable behaviors for crowd simulation. Computer Graphics Forum 23, 3 ,2004.
[16] KALLMANN M., BIERI H., THALMANN D.. Fully dynamic contrained Delaunay triangulations. In Geometric Modelling for Scientific Visualization, Brunnett G., Hamann B., Mueller H., Linsen L.(Eds.), Springer-Verlag, 2003, 241-257.
[17] BAYAZIT O.B., LIEN J.-M., AMATO N.M.. Better group behaviors in complex environments using global roadmaps. Artificial Life,2002.
[18] TANG W., WAN T. R. AND PATEL S.. Real-time crowd movement on large scale terrains. Theory and Practise of Computer Graphics, IEEE,2003.
[19] LAMARCHE F. AND DONIKIAN S.. Crowds of virtual humans: A new approach for real time navigation in complex and structured environments. Eurographics 04: Computer Graphics Forum 23, 3, 2004.9, 509-518.
[20] PETTRE J., LAUMOUND J.-P. AND THALMANN D.: A navigation graph for real-time crowd animation on multilayered and uneven terrain. In First International Workshop on Crowd Simulation, 2005, 81-89.
[21] Niitsuma M., Hashimoto H., Y. Kimura, AND Ishijima S.. Movement model of crowd robots based on human collicion avoidance. In Proceedings of the 28th Annual Conference of the IEEE Industrial Electronics Society, Sevilla, Spain, 2002.11,567-1572.
[22] Adela Béres, Károly Béres,Mihoko Niitsuma, AND Hideki Hashimoto. Advanced Movement Model of Crowd Robots.in First Workshop on Intelligent Solutions in Embedded Systems , 2003.
[23] Reeves W.. Particle systems:a technique for modeling a class of fuzzy objets.ACM Tronsactions on Graphics,1983,2(2):91-108.
[24] Hughes R.L.. The flow of human crowds.Annu. Rev.Fluid Mech,2003,35:169-182.
[25] Medieval. Total War .game homepage,http://www.totalwar.com, 2002.
[26] Brockington M.. Level-of-detail AI for a large role-playing game.In AI Game Programming Wisdom, 2002.
[27] Republic. the Revolution game homepage, http://www.elixirstudios.co.uk, 2003.
[28] Barros L. M., da Silva A. T., Musse S. R.. Petrosim: An architecture to manage virtual crowds in panic situations. In Proceedings of Computer Animation and Social Agents ,2004, 111-120.
[29] Braun A., Musse S., Bodmann L. O. B.. Modeling individual behaviors in crowd simulation. In Computer Animation and Social Agents, 2003, 143-148.
[30] Craig Reynolds. OpenSteer : Steering Behaviors for Autonomous Characters. http://opensteer.sourceforge.net/,2002.
[31] Lin M, Gottschalk S. Collision detection between geometric models: a survey. In: Proc. of the IMA Conf. on Mathematics of Surfaces,1998,37-56.
[32] Jiménez P, Thomas F, Torras C. 3d collision detection: A survey. Computers and Graphics, 2001,25(2):269-285.
[33] PaulM I, Michael FC. Controlling dynamic simulation with kinematics constraints behavior functions and inverse dynamics. ACM SIGGRAPH,1987,21 (4) : 215- 224.
[34] Duff T. Interval arithmetic and recursive subdivision for implicit functions and constructive geometry. ACM SIGGRAPH, 1992, 26 (2) : 131-138
[35] H.K.Kim, J.K.Oh, M.G.Choi, et al. An Event-Driven approach for crowd simulation with example motions. KAIST Department of Computer Science,2002.
[36] Ed Seidel. cactus code, http://cactuscode.org/,2003.
[37] Jeremy Reimer. Real-time strategy games, http://arstechnica.com/,2005.
[38] General-purpose computation using graphics hardware. http://www.gpgpu.org/,2005.
[39] Intel multi-core platforms. http://www.intel.com/technology/computing/multicore,2006.
[40] Advanced Micro Devices Inc (AMD). Multi-core processors - the next evolution in computing, 2005.
[41] GPU. http://baike.baidu.com/view/1196.htm?fr=ala0_1_1,2008.
[42] OpenCL. http://www.khronos.org/opencl/,2007.
[43] CUDA. http://www.nvidia.com/object/cuda_home_new.html,2007.
[44] Stream. http://developer.amd.com/gpu/ATIStreamSDK/,2008.
[45] OpenMP. http://openmp.org/wp/,2008.
[46] D. Helbing, I. Farkas, and T. Vicsek. Simulating dynamical features of escape panic.Nature, 2000,487-490.
[47] G. K. Still. Crowd Dynamics. PhD thesis,University of Warwick, UK, 2000.
[48] Jonathan Ferraris.Quadtrees.http://www.donews.net/kesney/,2005.
[49] Henri Hakl. Quadtree and Octree Culling Alternative.http://www.gamedev.net/reference/articles/article1485.asp,2001.
[50] Lawlor Orion Sky,Kal'e Laxmikant V. A voxel-based parallel collision detection algorithm,2002,285-293.
[2] Bouvier E., Cohen E., and Najman L.. From crowd simulation to airbag deployment: particle systems, a new paradigm of simulation. Journal of Electronic Imaging,1997, 6(1):4-107.
[3] Reynolds C.. Flocks, Herds and Schools: A Distributed Behavioral Model. SIGGRAPH, Computer Graphics, Vol.21, 1987.
[4] Mataric M. J.. Learning to Behave Socially, in D. Cliff, P.Husbands, J.-A. Meyer & S.Wilson,eds. From Animals to Animats: International Conference on Simulation of Adaptive Behavior, 1994, 453-462.
[5] HELBING D., MOLNáR P., AND SCHWEITZER F.. Computer simulations of pedestrian dynamics and trail formation. Evolution of Natural Structures, 1994, 229-234.
[6] Musse S.R. and Thalmann D.. A Behavioral Model for Real Time Simulation of Virtual Human Crowds. IEEE Transactions on Visualization and Computer Graphics,2001, 7(2):152-164.
[7] Xiaoyuan Tu and Demetri Terzopoulos. Artificial fishes: physics, locomotion, perception, behavior. SIGGRAPH’94: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, 1994,43-50.
[8] Blumberg B.M. and Galyean T. A.. Multi-level direction of autonomous creatures for real-time environments. Proceedings of SIGGRAPH 95, 1995.8,47-54.
[9] Perlin K. and Goldberg A.. IMPROV: A system for scripting interactive actors in virtual worlds. Proceedings of SIGGRAPH 96, 1996.8, 205-216.
[10] TREUILLE A., COOPER S. AND POPOVI? Z.. Continuum Crowds. ACM Trans. Graph, 2006,1160-1168.
[11] Shopf J., Barczak J., Oat C. and Tatarchuk. March of the Froblins: Simulation and Rendering Massive Crowds of Intelligent and Detailed Creatures on GPU. ACM SIGGRAPH, 2008.
[12] LI T.Y., LENG Y.J., AND CHANG S.I.. Simulating virtual crowds with a leader-follower model. In Proceedings of Computer Animation Conference, 2001.
[13] Farenc N., Boulic R., Thalmann D.. An informed environment dedicated to the simulation of virtual humans in urban context. In Eurographics’99, Scopigno R. (Eds.),Vol.18, 1999,309-318.
[14] Tecchia F. AND Chrysanthou Y.. Real-time rendering of densely populated urban environments. In Eurographics Workshop on Rendering Techniques 2000, Springer-Verlag,2000, 83-88.
[15] Sung M., Gleicher M. AND Chenney S.. Scalable behaviors for crowd simulation. Computer Graphics Forum 23, 3 ,2004.
[16] KALLMANN M., BIERI H., THALMANN D.. Fully dynamic contrained Delaunay triangulations. In Geometric Modelling for Scientific Visualization, Brunnett G., Hamann B., Mueller H., Linsen L.(Eds.), Springer-Verlag, 2003, 241-257.
[17] BAYAZIT O.B., LIEN J.-M., AMATO N.M.. Better group behaviors in complex environments using global roadmaps. Artificial Life,2002.
[18] TANG W., WAN T. R. AND PATEL S.. Real-time crowd movement on large scale terrains. Theory and Practise of Computer Graphics, IEEE,2003.
[19] LAMARCHE F. AND DONIKIAN S.. Crowds of virtual humans: A new approach for real time navigation in complex and structured environments. Eurographics 04: Computer Graphics Forum 23, 3, 2004.9, 509-518.
[20] PETTRE J., LAUMOUND J.-P. AND THALMANN D.: A navigation graph for real-time crowd animation on multilayered and uneven terrain. In First International Workshop on Crowd Simulation, 2005, 81-89.
[21] Niitsuma M., Hashimoto H., Y. Kimura, AND Ishijima S.. Movement model of crowd robots based on human collicion avoidance. In Proceedings of the 28th Annual Conference of the IEEE Industrial Electronics Society, Sevilla, Spain, 2002.11,567-1572.
[22] Adela Béres, Károly Béres,Mihoko Niitsuma, AND Hideki Hashimoto. Advanced Movement Model of Crowd Robots.in First Workshop on Intelligent Solutions in Embedded Systems , 2003.
[23] Reeves W.. Particle systems:a technique for modeling a class of fuzzy objets.ACM Tronsactions on Graphics,1983,2(2):91-108.
[24] Hughes R.L.. The flow of human crowds.Annu. Rev.Fluid Mech,2003,35:169-182.
[25] Medieval. Total War .game homepage,http://www.totalwar.com, 2002.
[26] Brockington M.. Level-of-detail AI for a large role-playing game.In AI Game Programming Wisdom, 2002.
[27] Republic. the Revolution game homepage, http://www.elixirstudios.co.uk, 2003.
[28] Barros L. M., da Silva A. T., Musse S. R.. Petrosim: An architecture to manage virtual crowds in panic situations. In Proceedings of Computer Animation and Social Agents ,2004, 111-120.
[29] Braun A., Musse S., Bodmann L. O. B.. Modeling individual behaviors in crowd simulation. In Computer Animation and Social Agents, 2003, 143-148.
[30] Craig Reynolds. OpenSteer : Steering Behaviors for Autonomous Characters. http://opensteer.sourceforge.net/,2002.
[31] Lin M, Gottschalk S. Collision detection between geometric models: a survey. In: Proc. of the IMA Conf. on Mathematics of Surfaces,1998,37-56.
[32] Jiménez P, Thomas F, Torras C. 3d collision detection: A survey. Computers and Graphics, 2001,25(2):269-285.
[33] PaulM I, Michael FC. Controlling dynamic simulation with kinematics constraints behavior functions and inverse dynamics. ACM SIGGRAPH,1987,21 (4) : 215- 224.
[34] Duff T. Interval arithmetic and recursive subdivision for implicit functions and constructive geometry. ACM SIGGRAPH, 1992, 26 (2) : 131-138
[35] H.K.Kim, J.K.Oh, M.G.Choi, et al. An Event-Driven approach for crowd simulation with example motions. KAIST Department of Computer Science,2002.
[36] Ed Seidel. cactus code, http://cactuscode.org/,2003.
[37] Jeremy Reimer. Real-time strategy games, http://arstechnica.com/,2005.
[38] General-purpose computation using graphics hardware. http://www.gpgpu.org/,2005.
[39] Intel multi-core platforms. http://www.intel.com/technology/computing/multicore,2006.
[40] Advanced Micro Devices Inc (AMD). Multi-core processors - the next evolution in computing, 2005.
[41] GPU. http://baike.baidu.com/view/1196.htm?fr=ala0_1_1,2008.
[42] OpenCL. http://www.khronos.org/opencl/,2007.
[43] CUDA. http://www.nvidia.com/object/cuda_home_new.html,2007.
[44] Stream. http://developer.amd.com/gpu/ATIStreamSDK/,2008.
[45] OpenMP. http://openmp.org/wp/,2008.
[46] D. Helbing, I. Farkas, and T. Vicsek. Simulating dynamical features of escape panic.Nature, 2000,487-490.
[47] G. K. Still. Crowd Dynamics. PhD thesis,University of Warwick, UK, 2000.
[48] Jonathan Ferraris.Quadtrees.http://www.donews.net/kesney/,2005.
[49] Henri Hakl. Quadtree and Octree Culling Alternative.http://www.gamedev.net/reference/articles/article1485.asp,2001.
[50] Lawlor Orion Sky,Kal'e Laxmikant V. A voxel-based parallel collision detection algorithm,2002,285-293.