群体多目标规划及行为模拟.doc

中文摘要 本文研究了大规模人群模拟中当个体具有多目标情况下，其路径规划的问题。本文工作基于中科院虚拟现实实验室所开发的大规模人群模拟软件Guard系统。我们使用Continuum Crowd 算法作为底层运动驱动模型，对上海世博会C片区做了相关模拟实验工作。我们的工作主要在以下几个方面：1) 提出了一种基于二次随机化的算法来生成个体(Agent)的目标集合，使其与目标场馆的偏好度相契合。2) 提出了一种场馆定义方法(入口和出口组合成场馆)，利用XML配置文件解决了场馆出口入口对应问题。3) 使用近似A * 算法来计算场馆的静态路径距离，使用最短路思想完成场馆路径规划。4) 使用优先队列数据结构维护场馆人员队列，极大的提高程序性能。关键字： 群体模拟 路径规划 势能场算法 多目标AbstractThis paper studies the path planning problem of the simulation of large crowds when the agent has multi-goals.This work is based on a large scale crowd simulation software Guard system developed by China Academy of Sciences Virtual Reality Lab.Using Continuum Crowd motion-driven model as the underlying algorithm, we have done the simulation of C Area of Shanghai World Expo Our work is mainly in the following areas: 1) Based on a secondary randomization algorithm ,we generate the agents target set, so as to fit venues preference. 2) We proposed a approach to define the venue (the combination of entries and exits), using XML configuration files 3) Use approximate A *algorithm to calculate the static route from the venue, and use the shortest path algorithm to complete complex path planning. 4) We use priority queue data structure to maintain waiting queue, greatly improve application performance.Key words:Crowd simulation Path planning Potential field algorithm Multiple goals目 录中文摘要1Abstract2一 引言51.1 研究背景51.2 研究目的与意义51.3本文的研究问题与主要贡献61.3.1 主要研究问题71.3.2 主要贡献71.4 论文组织结构71.5 论文工作总结8二 研究背景92.1面向大型公共设施安全问题研究的虚拟现实系统Guard系统简介92.1.1 Guard系统模块介绍92.1.2 Guard系统流程图与Guard系统使用102.1.3 Guard设计思想方法112.2群体运动仿真简介132.2.1 群体运动综述5132.2.2 群体运动模型的层次132.2.3 势能场模型142.3 本章小结16三 问题描述173.1 个体单目标模拟与多目标模拟流程图比较173.2 从单目标模拟到多目标模拟存在的问题18四 解决方案204.1 场馆定义与A*路径规划204.1.1 XML介绍204.1.2场馆XML文件应用244.1.3 静态距离计算相关问题284.1.4 个体多目标规划模块A*算法路径规划334.2 个体（Agent）目标生成与决策344.2.1 个体(Agent)目标集合生成344.2.2 个体(Agent)游览路径的决策354.2.3 场馆内个体离馆顺序规划354.3系统工作流程384.3.1分组(Gruop)驱动机制384.3.2 历史记录读写更新与姿态更新部分394.3.3 总体工作顺序流程394.4 实验结果40五 未来工作展望435.1 并行扩展435.2 排队现象的加入43六 参考文献45七 致谢46八 附录：478.1 随机洗牌算法random_shuffle478.2 Singleton 模式简介47一 引言1.1 研究背景早在19世纪末，群体行为的研究就初见端倪，但运用计算机模型对群体行为进行仿真研究的技术近年来才刚刚起步。20世纪90年代以来，群体行为仿真技术逐渐引起计算机图形学、人工智能、影视制作等众多领域研究者的关注。进入21世纪，群体运动对模拟逼真性和可视化效果的需求极为迫切，群体运动模拟日渐成为计算机虚拟现实领域的焦点。从传统的迪斯尼经典卡通中的群体场面到现代流行的CG动画制作的人群，人群运动仿真经历了从手工绘制到计算机生成的质的飞跃。Craig Reynolds的鸟群模拟1通过生物群聚行为模拟为进一步的人群运动仿真奠定了基础。华盛顿大学计算机图形学研究者提出的离散化势能算法2又将群体运动重新定位在全局性控制的角度上。随着应用需求和技术水平的不断提高，人群运动仿真对模拟对象之规模和复杂性要求越来越突出，大规模高密度模拟问题随即产生。大规模高密度人群运动仿真，就是研究大规模人群在极度拥挤环境的运动特征与规律，建立人群与环境的交互模型，并在计算机生成空间中以三维的方式逼真地展示运动过程。目前官方使用于大型场馆建筑设计、大型场面影像生成等项目中。1.2 研究目的与意义作为一种仿真分析方法，大规模高密度人群运动仿真技术可以应用于公共安全领域，体育场馆、地铁站等大型公共设施的设计等等。图1-1为势能场算法2模拟接到场景。以体育场馆为例，应用高密度人群运动仿真技术，可以根据体育场馆的设计规模，模拟球迷退场等常规情景下的高密度人群运动，辅助分析场馆的走廊宽度、出口数目和出口位置等设计分布是否合理；还可以模拟球迷发生冲突、火灾、恐怖袭击等非常规情景下的人群运动，辅助建立紧急情况下人员的疏散方案、合理布置消防器材、分配警力，还可以作为场馆管理人员进行消防、反恐等安全培训的辅助工具。与传统方法相比，以高密度人群运动仿真技术作为人群运动的分析工具，具有直观、灵活、高效、经济和无人员安全风险等诸多优点。图1-1 势能场方法模拟街道场景2作为一种演示工具，高密度人群运动仿真技术能够生成逼真的人群运动动画，因此，可以应用于娱乐游戏、电影电视媒体、国防研究等等。其具有以下几个优点：1）成本低、风险小、经济有效。利用计算机进行场馆建设前的评估模拟、疏散模拟的一个突出优势便是成本低、风险小、经济有效。真实的群体疏散模拟往往需要投入大量的人力物力，同时还必须承担一定经济损失和人员伤亡的风险。而用计算机进行模拟不仅可以大大节省开支，还可以确保相关人员的人身安全。同时，对于一些在现实中难于重现的情境，比如地震、爆炸等，亦可通过计算机得到重现并用于模拟研究。2）直观简单，可重复性强。利用计算机可视化模拟技术可将大量枯燥的数据转化成简单直观的图形显示，同时通过一定参数的设定和修改，可以方便地对不同场景和人员配置下的情况进行反复模拟。3）科技含量高，通用性强，可发展空间大。一个有效的高密度人群运动仿真模型的建立，需要综合考虑社会学、心理学、行为学、环境学以及计算机技术等多方面的因素，拥有高科技含量，也有着很强的通用性。因此，用计算机辅助模型设计和评估将成为一种必然的趋势，高密度群体模拟技术将会有越来越广阔的应用前景。 中国科学院计算技术研究所虚拟现实实验室在研究虚拟环境建模，自然灾害现象模拟、人群运动模拟方面做了很多工作，积累了很多经验，本文的研究就是基于由虚拟现实实验室开发的大规模人群模拟软件Guard系统的。1.3本文的研究问题与主要贡献1.3.1 主要研究问题目前由中国科学院计算技术研究所虚拟现实实验室所开发的大规模人群模拟软件Guard系统(以下我们简称其为Guard系统，有关Guard系统的详细介绍，请参见本文中Guard 系统介绍）只能支持个体(Agent)的单目标游览。当个体(Agent)从生成区域中产生出来的时候，就会随机产生一个目标，并在势能场算法模型(有关势能场算法的详细介绍，请参见本文群体运动综述)驱动下，朝向其既定目标前进。但在现实世界中，很多个体(Agent)的游览存在多目标的情况，这是目前Guard系统所不能完成的。本文主要解决的问题是在个体(Agent)同时具有多个目标的情况下，大规模人群模拟情况的实现的探讨。目前Guard系统应用于上海世博会项目人流游览疏散的模拟。现实情况中，当个体(Agent)进入世博会园区，他可能想去很多个场馆进行游览，其目标具有多个（具有一个目标的个体只是少数情况），所以具有多目标的个体更符合实际需要。本文研究并实现了个体多目标的模拟过程。1.3.2 主要贡献 本文研究了大规模人群模拟中个体多目标规划问题的实现。我们工作基于中科院虚拟现实实验室所开发的大规模人群模拟软件Guard系统，我们对Guard系统进行了多目标的扩展。我们使用Continuum Crowd 算法作为底层运动驱动模型，对上海世博会C片区做了相关模拟实验工作。我们创新性工作主要在以下方面：1) 提出了一种二次随机化的思想来生成个体(Agent)的目标集合，使其与目标场馆的偏好度很好相契合。2) 提出了一种场馆定义方法(入口和出口组合成场馆)使用XML配置文件的方法，解决了场馆出口入口对应问题。3) 使用近似A * 算法思想来完成场馆的静态路径距离计算，使用最短路思想完成场馆路径规划。4) 使用优先队列数据结构维护场馆人员队列，极大的提高程序性能。1.4 论文组织结构 第一章 引言。主要介绍了本文的研究背景和研究意义以及主要的研究内容。 第二章 研究背景 首先介绍了面向大型公共设施安全问题研究的虚拟现实系统Guard系统简介，介绍了本文工作的软件基础Guard系统，包括Guard系统中的各个模块的介绍和其设计思想。然后介绍了群体运动仿真简介。主要包括群体运动仿真的现状以及群体运动模拟中的分层机制和群体运动模拟中的经典模型势能场模型。 第三章 介绍了从个体(Agent)单目标到个体(Agent)多目标模拟的转换过程中出现的各种问题。第四章 针对第三章中出现的各种问题，我们提出了相应的解决方案。4.1中试场馆定义与A*路径规划 主要介绍了我们在本文中场馆定义的方法，以及相关背景知识XML文档的介绍。然后介绍了A*算法的背景知识，以及在此项目中路径规划模块的详细信息。4.2个体目标生成与决策 主要介绍了二次随机化思想来生成个体目标集合然后基于最短路径方法的个体游览路径规划和使用优先队列的场馆个体离馆顺序规划。 4.3系统工作流程 主要介绍了Guard系统模拟中的分组机制和历史记录管理个体姿态更新部分，最后用顺序图的方式生成了整个系统工作流程。 4.4 实验结果 本文中我们做了3个实验，都做成了Demo进行展示 第五章 未来工作展望 下一阶段我们需要把个体多目标规划部分集成到并行系统当中去，然后进行排队现象的模拟。 第六章 参考文献 第七章 致谢 第八章 附录1.5 论文工作总结 本文讨论并实现了上海世博会项目中个体多目标的模拟过程，并解决了其中面临的几个问题。我们的工作主要在以下几个方面：1) 提出了一种基于二次随机化的算法来生成个体(Agent)的目标集合，使其与目标场馆的偏好度相契合。2) 提出了一种场馆定义方法(入口和出口组合成场馆)，利用XML配置文件解决了场馆出口入口对应问题。3) 使用近似A * 算法来计算场馆的静态路径距离，使用最短路思想完成场馆路径规划。4) 使用优先队列数据结构维护场馆人员队列，极大的提高程序性能。二 研究背景2.1面向大型公共设施安全问题研究的虚拟现实系统Guard系统简介2.1.1 Guard系统模块介绍Guarder是中国科学院计算技术研究所虚拟现实实验室“面向大型公共设施安全问题研究的虚拟现实系统”，是大规模群体渲染工作的工作平台，主要任务是解决复杂环境下大规模群体的路径规划问题，判断建筑布局、人员组织等方案是否会容易导致拥挤等影响公共安全的现象。Guard系统场景中主要模块有渲染模块、交互模块、计算模块、文件模块，各模块又可分为相应子模块。3 1）渲染模块 渲染模块包括场景渲染，群体渲染，要素渲染，交互渲染和其他渲染组成。其中场景渲染负责场景模型的现实。群体渲染，负责虚拟人体的现实。要素渲染负责模拟要素、统计要素的渲染，由其自身负责，目前各种要素均以区域实现。交互渲染负责交互时各种临时对象的现实，由各UI对象自行处理。其他渲染主要指文本、天空盒、场景坐标轴等，这些由系统基于OpenGL直接实现。2）交互模块 交互模块包括非数据交互和数据交互。非数据交互指相机交互、剪切平面交互。数据交互包括数据的添加、修改、删除、选取等。3）计算模块系统中的计算模块主要包括模拟计算、统计分析两部分，前者根据模拟任务的设置、完成人员运动轨迹的计算，后者以前者为基础，完成相关信息的统计。4）文件模块系统中文件模块主要包括场景文件、模拟记录、统计结果、项目文件。场景文件负责提供场景的导入。模拟记录模块提供模拟记录的管理，包括系统运行时数据调度、文件导入导出。统计结果模块负责统计结果。项目文件负责模拟任务的设置、统计元素设置、场景视角等。2.1.2 Guard系统流程图与Guard系统使用系统运行始于./Guarder2/src/guarder.cpp中的_tWinMain函数。在这里，系统创建了CMainWindow框架窗口实例，然后开始查询并派发消息，当用户选择退出后，主窗口被销毁，程序退出。图2-13是Guard系统的流程图。图 2-1 Guard系统流程图 Guard系统的使用，请读者参考Demo2 。Demo2中给出了一个使用Guard的实例演示。图2-2 给出了一个Demo2 的截图(操作过程参见Demo2)。详细的使用过程请参见Guard使用手册4 图2-2 Guard系统演示实例Demo2截图 2.1.3 Guard设计思想方法Guard系统不允许多个实例同时运行的方法是使用了Win32系统中的Mutex。Mutex是Win32系统实现多线程互斥访问资源的一种方式。Guard系统 采用wxWidgets库提供用户交互。wxWidgets库是开源跨平台的界面库同微软的MFC基本上是同时发展起来的，其最大的特点和优点是本生界面的提供：在Windows上用它生成的界面长着Windows上窗口的样，在Linux上则长着Linux的样，所谓“橘生淮南即为桔，生于淮北则为枳”。图2-3是Guard系统的启动界面。图2-3 Guard系统的启动界面 Guard系统的设计模式，采用的是设计模式中的经典的单键模式(Singleton Pattern)。关于单键模式的详细介绍请读者参照附录2 单键模式。2.2群体运动仿真简介2.2.1 群体运动综述5 群体运动控制的传统方法可以被大体上分为两类，宏观方法和微观方法。微观方法描述了在人群中每一个个体(Agent)的运动，而宏观方法则是控制群体运动的全局行为。所谓宏观主导模型（macroscale-oriented model），即从整体环境考虑，将个体角色抽象为环境中分配的粒子，按照全局原则规定特定环境中的个体的运动方式；所谓微观主导模型（microscale-oriented model），即着眼于行为个体，根据获取的部分环境信息，按照一定的行为规则约束个体运动，组成群体运动。宏观模型基于场景环境，不考虑人员的个体特征，只是将模型中所有人作为具有共同特征的群体加以分析和模拟。宏观模型中的群体运动决策方法一般为无行为的，完全依赖人群的物理运动和建筑空间的物理表达来决定个体的运动决策情况并做出相应的预测和判断。宏观模型在描述运动过程时针对大量的人群，不论在模型的理论组织还是计算速度方面都具有较大的优势。主要代表有元胞自动机模型（Cellular model）、多agent模型（Multi-agent Based Model）、势能场模型（Potential Field Model）等。微观模型基于个体，可设定或由随机方法确定模型中人员的个体特征，以模拟人员的决定和运动过程。微观模型中同样包含群体行为，一般分为基于物理运动行为约束方程模型、基于运动行为经验准则的规则模型和基于人工智能的状态决策模型。微观模型的代表主要有智能个体模型（AI-based Model）、微粒群模型（Particle Based Model）、物理力模型（Physical Force Based Model）等。2.2.2 群体运动模型的层次 群体运动模型具有分层结构，可以分为两个层次：底层路径导航层和上层运动决策层。下面我们分别介绍这两个层次1）底层路径导航层群体运动模拟的全局场景可以被离散化为许多网格，我们底层路径导航层以网格为基础，通过获取网格信息，来获得导航信息。Guard系统中，我们采用网格划分的离散化矢量场模型提供导航信息。在经典势能场理论基础上，屏蔽个体产生的代价影响，提出一次预处理生成全局路径网格信息的引导方法。2）上层运动决策层个体通过感知系统实现与局部环境的交互，通过所在的势能场得到路径方向信息，综合对感知到的移动障碍采取的碰撞避免策略，从而得到运动决策，并将更新后的状态反馈到环境系统。底层路径导航层与上层运动决策层相辅相成。在科技部国家科技支撑计划“世博科技专项”课题“2010年上海世博会人流疏导应急预案模拟关键技术研究与服务应用”项目中，我们的工作是为Guard系统扩展多目标规划的功能。添加多目标规划的模块隶属于上层的运动决策层，它与底层的路径导航层无关。2.2.3 势能场模型 在Guard系统的底层路径导航层，我们使用的是参考文献2中的势能场(Potential Field)算法，下面我们对势能场算法进行一个简介。1）密度映射过程图2-4 密度映射过程图在势能场算法中，我们把场景划分为对齐的四边形网格。个体(Agent)对其周围网格有一个密度影响，相当于把此个体映射到周围的网格当中去。每个人都有一个自己单独的密度场，这个函数本身的形式并不重要，重要的是具有这样一个性质，在一定范围内大于某个阈值，出了范围都少于一个阈值。文章中处提出了下面的密度映射函数。然后对每一个网格的密度值，平均速度值进行计算.人群密度场就是每个人的个体密度场叠加产生的结果。其中(Xi)表示第i个个体的速度，i表示第i个个体在此网格上的密度映射值。2）速度场的计算首先，我们人为设定一个网格密度的最大值和网格密度的最小值。当某个网格密度少于网格密度最小值时，此时的速度F相当于只受地形的影响，我们定义地形的斜率的最大值与最小为值分别为Smax 和Smin，表示在方向上的斜率。我们使用下面的公式获得速度。当在高密度区，此时密度大于网格密度最大值，则此时人的速度就等于人流的速度。当密度介于网格密度最大值与网格密度最小值之间的时候，此刻的速度相当于网格最大密度时的速度与网格最小密度时的速度的线性插值。 3）路径代价计算 将路径代价设定为行路时间、路程长度、路径不适度三者的积分和：其中P为路径，、为参数，g为不适值，设 f 为速度，有ds = f * dt，所求最佳路径使下式最小：将积分元设为C，上式变为 即代价元： 4）势能场势能值的计算 规定目标节点为势能零点，按有限差分规则计算网格势能：5）路径方向场计算由梯度计算公式：推出速度矢量式：思想为根据势能梯度求速度场，然后利用速度乘以模拟的单位时间，得到个体(Agent)的下一个位置，更新个体(Agent)的位置信息。然后进行下一步的计算模拟。2.3 本章小结我们介绍了面向大型公共设施安全问题研究的虚拟现实系统Guard系统，简要介绍了Guard系统模块组织，其中包括渲染模块、交互模块、计算模块、文件模块等。然后介绍了Guard系统的系统流程图和Guard系统的设计思想等。此部分的介绍为我们下面工作的展开做了铺垫。我们简要介绍了群体运动的现状和群体模拟的两个层次底层路径导航层和上层运动决策层，我们的工作是建立在上层运动决策层之上的。在3.3节中，我们详细介绍了势能场算法，包括其密度映射的原理和速度场的生成，路径代价和势能场的计算等，通过上述计算，可以获得每一帧个体的速度，位置等需要的信息，从而能够很好的完成底层路径导航层的工作。三 问题描述3.1 个体单目标模拟与多目标模拟流程图比较 个体单目标模拟，即个体(Agent)只有一个目标。在其生命周期内只有两个过程：初始阶段的个体目标生成与模拟过程中的个体历史记录的管理。其流程图见图3-1个体目标生成个体历史记录管理图3-1 个体单目标模拟流程图场馆定义问题场馆距离计算个体目标决策个体历史记录管理个体目标生成场馆等待队列维护图3-2 个体多目标模拟流程图 个体多目标模拟，即个体(Agent)具有多个目标，在其生命周期内，有几个过程：初始阶段完成场馆定义过程个体目标生成过程以及场馆距离计算等，然后根据初始阶段获得的信息完成个体目标决策过程。在模拟进行的过程当中，我们需要完成场馆等待队列的维护和个体历史记录的管理等功能。3.2 从单目标模拟到多目标模拟存在的问题目前，我们的Guard系统模拟的时候只能够模拟个体(Agent)的单目标运动，个体(Agent)一出现的时候，即产生一个目标，然后在个体的生命期内，朝向目标运动，到达目标之后，个体即消失。但现实情况却与此不同，现实情况中，个体(Agent)存在多目标的情况，一个个体当到达场馆之后，停留一段时间之后，仍然会朝向他的下一个目标运动。如果加入个体多目标的过程，则我们模拟的情况更为真实。从个体单目标运动扩展到个体多目标运动面临很多的问题：1） 场馆的定义问题 当个体具有单目标的时候，不必关心场馆出口与入口的组合关系，只要个体到达目标场馆即可，但当个体具有多目标的情况下，个体需要从一个场馆入口进入场馆之后，需要从此场馆的出口出现，此时我们需要一个约束关系来确认哪些场馆入口与出口时相对应的。(见图3-1)图3-1 场馆定义问题2） 场馆之间的距离计算问题 当个体(Agent)具有单个目标的时候，不必关心场馆与场馆之间的距离，但当个体(Agent)具有多目标的情况下，我们需要计算场馆与场馆之间的距离，用来为个体(Agent)做路径规划3） 个体目标生成问题 当个体具有单目标的情况下，我们只需要为个体生成一个随机目标即可，但当个体具有多目标时，我们为个体生成目标集合的时候，需要考虑到我们生成的目标集合的总体分布应当满足实际情况4） 个体目标决策问题 当我们生成目标序列与各个场馆之间的距离之后，我们需要给个体做合适的路径规划。用来指导个体做下一步的运动。5） 场馆等待队列维护问题 当个体只具有单目标的情况下，场馆内并无等待的个体。当当个体具有多个目标的情况下，场馆内应当有正在游览等待充场馆离开的个体，如何管理此部分等待个体，也是一个问题6） 个体历史记录管理 当个体(Agent)具有单个目标的情况下，其历史记录就为模拟的过程中每一帧的实际运动情况即可，但当个体具有多目标的时候，个体在场馆的阶段并不参与模拟，我们需要修改历史记录的管理方式来使其具有连续的历史记录，如何修改历史记录的管理方式，也是一个问题。 从个体具有但目标的系统扩展到个体具有多目标的系统，上述问题是我们必须要面对的！四 解决方案 针对我们在第三章中所面临的各个问题，我们在第四章中一一做出了解答。4.1节中解决了我们在场馆定义问题和场馆之间的距离计算问题。4.2节中解决了个体目标生成问题和个体目标决策问题与场馆等待队列维护问题。4.3节中我们结局了个体历史记录管理问题，4.4节中我们给出了个体多目标规划的最终实验结果。4.1 场馆定义与A*路径规划基于现实情况的考虑，每一个场馆有很多的出口和很多的入口，在程序实现的过程中，我们也要基于这样一个现实，将该场馆的入口和该场馆的出口当做一个整体来考虑，只有这时一个个体(Agent) 才能够实现从一个场馆的入口进入场馆，游览一段时间，然后从该场馆的出口出来，然后游览下一个场馆。在整个程序的实现中，我们通过设置XML配置文件的方法，来通过Markup实现了从XML文件读入场馆的信息。首先我们介绍关于XML文件的书写与markup的使用的方法，然后我们介绍此思想在Guard项目中的应用。为了实现人群多目标规划过程，在已知个体(Agent)的游览目标集合的情况下，我们应该参照场馆环境生成一条合理的游览路径。游览路径的选取要基于个体与场馆的距离信息，在距离信息的获取中，我们使用了效率较高的A*算法，下面我们对距离信息获取进行了一个总体描述，然后对A*算法进行了详尽的介绍，最后我们讨论了A*算法在项目中的应用。 4.1.1 XML介绍一 XML文档简介1 XML是英文Extensible Markup Language 的缩写，中文翻译为可扩展标记语言。62 XML文档的优点7 i) 易携带和传输 XML文档不依赖于特殊的软件，文本编辑器就可以编写XML文档 ii) 易于共享和跨平台 iii)易于查询 因为XML是树状结构的结构化文档3 XML文档的语法和数据组织结构下面是关于XML文档的一些简单的介绍，关于XML详细说明请读者参考文档3 1）每个开始标记必须有结束标记 2）一个XML文档只能有一个根元素(root element) 3）所有XML元素必须正确嵌套 4）属性值必须加引号 5）一个元素不能有相同的属性 6）XML文档是大小写敏感的(Case Sensitive) 7）XML文档是树状结构，它只有一个根元素(root element)，其他元素都是根元素的后代。图4-1表示的是XML文档的树状结构图。图4-1 XML文档树状结构图 4 我们使用的工具是CMarkup 11.2 它的官方网站是/CMarkup 11.2 为我们提供了很多处理XML文档的方法，在四个方面处理中尤为出色。 1）生成和修改XML文档 Generate or modify XML 2）从XML文档中提取所需信息 Extract the information you need from XML 3）在XML中处理二进制文件 Handle images and binaries in XML 4）处理非常大的文档 Even on very large documents二 XML CMarkup的使用方法1 创建一个XML文档为了创建一个XML文档，我们需要实例化一个CMarkup对象，然后调用AddElem函数方法来创建一个根元素。此时如果我们调用AddElem(“ORDER”)，文件就会给我们创建一个空的元素。然后调用AddChiladElem来在根元素之下创建子元素。例如Code 4-11. CMarkupxml;2. xml.AddElem(ORDER);3. xml.AddChildElem(ITEM);4. xml.IntoElem();5. xml.AddChildElem(SN,132487A-J);6. xml.AddChildElem(NAME,crankcasing);7. xml.AddChildElem(QTY,1);8. CStringcsXML=xml.GetDoc();Code 4-1如上代码生成了下面的XML文档Code 4-21. 2. 3. 132487A-J4. crankcasing5. 16. 7. Code 4-22 遍历一个XML文档在Code 4-1中创建的CString同样可以通过使用SetDoc方法被转变成为一个CMarkup对象。例如Code 4-31. CMarkupxml;2. xml.SetDoc(csXML);3. while(xml.FindChildElem(ITEM)4. 5. xml.IntoElem();6. xml.FindChildElem(SN);7. CStringcsSN=xml.GetChildData();8. xml.FindChildElem(QTY);9. intnQty=atoi(xml.GetChildData();10. xml.OutOfElem();11. Code 4-33 添加元素和属性在Code 4-1 和Code 4-3 中只是创建了一个Item元素，在我们通过调用IntoElem和AddElem方法来添加元素和属性。例如Code 4-41. CMarkupxml;2. xml.AddElem(ORDER);3. xml.IntoElem();/insideORDER4. for(intnItem=0;nItemaItems.GetSize();+nItem)5. 6. xml.AddElem(ITEM);7. xml.IntoElem();/insideITEM8. xml.AddElem(SN,aItemsnItem.csSN);9. xml.AddElem(NAME,aItemsnItem.csName);10. xml.AddElem(QTY,aItemsnItem.nQty);11. xml.OutOfElem();/backouttoITEMlevel12. 13. xml.AddElem(SHIPMENT);14. xml.IntoElem();/insideSHIPMENT15. xml.AddElem(POC);16. xml.SetAttrib(type,csPOCType);17. xml.IntoElem();/insidePOC18. xml.AddElem(NAME,csPOCName);19. xml.AddElem(TEL,csPOCTel);Code 4-4通过如上的XML文件我们便得到了如下的XML文档，见Code 4-51. 2. 3. 132487A-J4. crankcasing5. 16. 7. 8. 4238764-A9. bearing10. 1511. 12. 13. 14. JohnSmith15. 555-123416. 17. 18. Code 4-54 查找元素 通过使用FindElem方法，我们可以在XML文档中查找相应的信息。1. CMarkupxml;2. xml.SetDoc(csXML);3. xml.FindElem();/ORDERelementisroot4. xml.IntoElem();/insideORDER5. while(xml.FindElem(ITEM)6. 7. xml.FindChildElem(SN);8. if(xml.GetChildData()=csFindSN)9. break;/found10. Code 4-6此外在CMarkup中，还有很对方法，用来对XML文档进行详尽的处理，有兴趣的读者可以参加CMarkup源代码，获得更详尽的理解。图 4-2展示的是CMarkup中的部分方法。 图4-2 CMarkup中部分方法4.1.2场馆XML文件应用我们通过读取场景配置文件来搭建场景的模型，搭建完成之后我们将得到如下的模型。见图4-3 （一个典型场馆的布局图,此场馆具有两个出口两个入口，如图所示）图4-3 典型场馆布局图 图4-4 生成区域模型 图4-5目标模型此时我们只有场景语义信息，包括场馆的高度，以及场景中是否是可行走区域等。但是对于场馆的真实名称以及场馆的出口(图4-4 生成区域)入口(图4-5 目标)的归属关系，人游览此场馆的停留时间等信息则无从得知。我们需要使用XML配置文件来获得此信息。在我们的场馆配置文件描述中，我们使用如下的定义：(程序定义)string VenueName; /场馆名称vector Genregion; /生成区域名称vector Entrance; /目标入口名称vector p; /目标入口的指针vector q; /生成区域的指针int index; /场馆索引号int time; /agent在该场馆的平均逗留时间 在XML配置文件中，我们采用如下的格式进行场馆定义：1. 2. 法国馆3. 生成区域14. 生成区域25. 目标16. 目标27. 08. 79. Code 4-7 在CMakrup文件中，我们采用如下方法来从上述XML文件中获取场馆的信息，从而实现了场馆的定义1. CMarkupxml;2. if(xml.Load(F:GuardSHsosi.xml)3. 4. xml.IntoElem();/insideVenueInformation5. while(xml.FindChildElem(Venue)6. 7. Venuetemp;8. xml.IntoElem();9. xml.FindChildElem(Name);10. 11. temp.VenueName=xml.GetChildData();12. 13. while(xml.FindChildElem(Genregion)14. 15. temp.Genregion.push_back(xml.GetChildData();16. 17. while(xml.FindChildElem(Entrance)18. 19. temp.Entrance.push_back(xml.GetChildData();20. 21. while(xml.FindChildElem(Index)22. 23. temp.index=parase(xml.GetChildData();24. 25. while(xml.FindChildElem(WaitTime)26. 27. temp.time=parase(xml.GetChildData();28. 29. GlobalVenue.push_back(temp);30. xml.OutOfElem();31. 32. xml.OutOfElem();33. Code 4-8经过上述定义，通过模拟的时候的预处理,我们便获得了我们的场景图(图4-6 世博会园区中模拟场馆图)与现实中的真实场馆(图4-7 世博会园区真实场馆图)之间的一一对应关系，接下来人群的模拟都基于如上信息进行的。图4-6世博会园区模拟场馆图图4-7世博会园区真实场馆图4.1.3 静态距离计算相关问题一 Pathfinding与Movement问题综述寻路(Pathfinding)解决这样一类问题：找到起点到终点的最短代价（时间, 距离，设备等）距离，且在此过程中需要避免障碍物，避免敌人等。移动(Movement)是这样一类问题：选择一条从起点到终点的路径并沿着它走下去。 现实中的路径规划(Path Planning)问题都可以规约到Pathfinding和Movement的问题。 解决一个现实中的路径规划问题，我们可以从寻路(PathFinding)和移动(Movement)任何一方面下手。一方面,一个复杂的寻路(Pathfinding)算法和一个很简单的移动(Movement)算法结合，我们将会观察到如下现象：当个体(Agent)开始移动时，它就会沿着已经规划好的全局路径走下去。另一个方面，一个只考虑移动(Movenment)的路径规划算法，将不会去寻找一个复杂的全局路径(初始的路径就是从起点到终点的一条直线),而只是在每一个时刻通过对周围环境的考察，移动一步，然后重复上述过程。在寻路(PathFinding)和移动(Movement)之间有一个权衡的过程。寻路通常能够生成好的结果，但是它的计算量大，效率差，速度慢。而移动(Movement)计算量小，效率高，速度快，但常常受环境的限制，不能生成比较好的路径。但如果环境比较复杂，寻路(Pathfinding)效率将变得非常差！下图中(图4-8)阐释了寻路与移动之间的权衡。红色代表只考虑移动(Movement)的算法,蓝色代表只考虑寻路(PathFinding)的算法。红色由于只考虑周围环境，所以在检查到障碍物的时候，已经走了很多冤枉路，而蓝色由于提前进行了寻路(Pathfinding)过程，所以表现较好，但这是以大计算量为前提的。图4-8寻路(Pathfinding)与移动(Movement)算法比较8二 路径规划(PathPlanning)中的Dijks