评论: 0　查看评论　发表评论

找优秀程序员，就在博客园

最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐：史上最强女游戏程序员

网站导航：博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

摘要：
制作一个3-D游戏引擎并不是一件很简单的任务，因为现在的游戏玩家常常要求在游戏中有着高性能和高质量的输出。在这篇文章中，我们向大家展示了多种实时渲染的算法如何用来在一个实际的3-D游戏引擎中提高性能。我们探究了一个通用的3-D游戏引擎的结构并且讨论了在3-D游戏引擎中的视景图像的任务。我们将从软件工程的角度来研究视景图像，我们将向你展示一种面向对象的和可以方便的通过不同渲染引擎来设计的视景图像。接下来，我们解释了在我们的3-D游戏引擎中用来提高引擎性能的算法。我们在视景图像和物体几何层面上对我们的3-D游戏引擎进行了优化。我们提出的算法在静态和动态的场景中表现的都是相当的好。最后，我们用多处理器在视景图像方面用并行处理的方式来建立个3-D游戏引擎方面作了一下简单的展望。

一、介绍：

在过去的十年里面，计算机游戏行业经历了巨大的增长的黄金时期。在过去的几年里，随着3-D加速硬件设备的飞快的进步，游戏制造行业都将焦点集中在用创新的思想来生产交互式的3-D游戏。3-D游戏引擎是驱动这些游戏的核心技术。简单的来讲，一个3-D擎获得游戏中的3-D物体的几何数据并将这些数据展示在显示设备上，典型的显示设备就是显示器。这个过程就是我们通常所知的渲染。3-D物体的几何数据通常通过一系列的顶点来定义，物体的具体特性（象漫射的颜色，镜面反射以及发射出的颜色等），纹理图，纹理匹配以及一些常用的向量。所有的这些数据在3-D游戏引擎处理途径中经历不同的阶段来决定着这些3-D 物体的最终显示的效果。

图1 一个完整的3-D引擎的处理过程。高层的视景图像给用户一种直觉的方式来模拟一个场景，优化的场景保证了场景对于渲染的高效率。
高层视景图像规定了在游戏中的物体之间的关系，它对于游戏开发者来讲也是在游戏中操纵这些物体的一个应用程序接口（API）。在一个场景被渲染之前，视景图像必须为了渲染而被优化。这种优化处理就是典型的将高层视景图像转变成（编译成）优化的视景图像，这种被优化的视景图像就是用了一种非常适用于渲染的数据结构。这就要求开发者去详细的确定每个物体的“线索”：比如这个物体是静止的还是移动的，物体的结构是否随着时间的变化而变化等等。视景物体剔除就是将观察者不能看到的物体丢弃掉的处理过程，尽管细节层次控制可以将相对于观察着者比较远的一些无关紧要的物体给删除掉。所有这些思想的背后就是减少渲染那些你看不见的东西以及减少远端物体几何数据，为了是将送往最终渲染管线的数据减到最少，这些将会明显的提高渲染性能。这些就是一个3-D游戏引擎为了提高它的性能而所要完成的主要任务。
后续的任务，诸如灯光，视角转换，裁减，投影变换以及光栅化，都是渲染引擎为了完成渲染流程所需要承担的任务。渲染引擎，就是经常提及的立即模式渲染引擎，往往都可以被3-D加速硬件支持。两种主要的适用于PC机的渲染引擎就是微软的Direct3D和Silicon Graphics 公司的 OpenGL。在这种渲染引擎上开发游戏往往是枯燥和耗费时间的，这些引擎所给的程序接口都是些程序性的和面向硬件的。在接下来的部分，我们将在集中在建立3-D游戏引擎的三个主要的模块：（1）为我们的3-D引擎建立高层场景图像；（2）为了建立优化的场景图像的算法；（3）如何丢弃不在观察者视野范围内的物体，并且适当的控制细节层次控制物体。
2.在3-D引擎中的设计问题
视景图像设计由于它直接牵扯到整个3-D引擎的性能所以显得非常重要。它定义了一种让程序员来模拟视景的方式。一个好的视景图像设计应该允许程序员将更多的视景（诸如物体和它们的排列）包含在视景中，并且想到用最好的方式来展现它们，并且可以忽略掉渲染管线的复杂的控制。程序员将通过视景图像的API来设计3-D引擎。
视景图像设计
在视景图像设计中的第一个问题就是要考虑物体的表现。就像我们上面提到的一样，象Direct3D和OpenGl这样的立即模式的渲染引擎均倾向于拥有自己的面向图形硬件的渲染程序功能函数。很显然，这种面向渲染的设计并不适合于完成我们的视景图像的设计的目标。一个面向对象的视景图像设计明显的是一种比较好的程序模式，在这种模式中允许程序员在视景中用对象的概念来设计3-D游戏。我们将所有的游戏对象都当作视景中的3-D对象来对待。Strauss和 Carey已经介绍了完全面向对象的视景图像框架。这个框架的基本的思想就是将3-D视景描述为物体的图像，这种图像成为节点。有很多种类型的节点并且每一个节点都有不同的相关属性。比如说，圆柱形状的节点包含两个参数：半径和高度，但是球状物体仅仅包含一个参数，那就是半径。有一些特定的节点可以包含属于它们的子节点的一些参数。例如，在图2中，描绘了一个汽车的一部分的视景图像。节点组命名为“Body”，它拥有4个子节点来组成汽车的车身。纹理节点包含了定义汽车车身纹理图像的参数。这些参数同样会被命名为“门”的一组节点继承，这些节点用来组成汽车车身的车门。因此，汽车车门将会拥有和车身一样的纹理。通过应用这种方式，我们不仅可以增加资源的可重复利用度，而且也是简单的模拟场景的方式，尤其当我们处理一些视景物体的相对位置时，这种方式显得更有效。变换节点用来描述在父节点下的对象的位置和方向的变换。这些都是相对于父节点的变换。为了得到这些节点的绝对变换（相对于整个场景的变换），当前的这些节点将和它们的父节点的变换相结合（通过矩阵相乘）起来。这样就可以很轻松和简单的一个对象相对与父节点的位置和方向了。这种模型就是通常我们所说的等级场景模型并且是骨骼动画的基础，这种模型通常用来在游戏中的动画的运动部分。

2.2 可移植的视景图形
为了保证我们的游戏能满足尽可能多的玩家的要求，我们必须保证我们的3-D游戏引擎可以在不同的平台和不同的操作系统上运行。因此可移植性是我们设计视景图形的另外一个问题。一个视景图形必须能够在各种目标平台上运行渲染引擎，而且游戏的代码还不能做任何的改动。一个可移植的视景图形必须设计成为不依赖于特殊的渲染引擎才能运行。D鰈lner and Hinrichs 已经讨论了一些实用的方法来归纳不同渲染引擎的特性，并且提议一种可以支持这些系统的通用的视景图形结构。他们确信通过应用一种通用的视景图形，大多数的实时渲染设备都能被整合为单一的不会被凌驾于或是受到一些特殊的渲染引擎的视景图形表示方法。可移植性通过分离的渲染对象和渲染引擎来共同完成。图3就是一个用来证明这种观点简化了的原始的视景图形结构。和前面我们讨论的 Strauss and Carey的工作相类似，一个渲染对象就是在视景图形中的一个节点。多个渲染对象在视景中组织起来就形成了一个完整的视景。D鰈 lner and Hinrichs 将渲染对象扩展到包括不被任何渲染函数支持的2-D和3-D几何对象，除了它们的几何描述；属性包括外观属性（颜色，材质，纹理），变换属性（方向和位置），以及光照属性（不同的光源），这些都是要渲染的细节。在渲染的过程中，渲染引擎将会研究和解释视景图形的内容，计算每个被渲染对象的属性并且将它们转换为与目标渲染引擎相匹配的算法。因此，渲染引擎是唯一的能包含细化一个可移植渲染系统的代码的地方，这些渲染引擎的特殊的算法在整个执行过程中被称为句柄，即每个属性的特例。在渲染的时候渲染引擎将会调用这些句柄的方法。特殊的渲染引擎可以提供优化的引擎执行方法用来扩展底层渲染引擎的特殊的功能函数。在一张大的图片、一些视景图形被描述为可以满足特定规范的参数化的视景。一个视景结构紧紧能为给定的渲染引擎而计算。它的内容可以被不同的渲染引擎解释为不同的目的。
3.在3-D引擎中的优化技术
在这一章中的优化专门的是指用来加速我们3-D引擎的渲染速度的加速技术。优化技术获得视景图形中的对象，并且构建一种特别有利于渲染的数据结构来存储物体的几何数据。这个过程就是通常所说的视景图形编辑。一个完整的优化视景图形应该能够提供对于感光输出结果。Sudarsky and Gotsman 定义了一个在每一祯的运行时间为O(n+f (N))的条件下的感光输出算法，在这里N是在场景里所有对象，n是所有的可见物体，而且f(N)远远小于N。举个简单的例子， 也就是说一个光敏感输出算法的运行时间和可见物体的数量成线性正比关系，而不是和场景中的所有物体成正比。目前共有两种技术能达到这个目的。在物体的几何层次，细节层次控制试图在越远的物体上渲染的越少的数据（也就是物体包含越少的数据）。然而，越靠近观察者的物体越会清晰的呈现它们的完整特性，反之越远的物体看起来越粗糙因为很多精细的细节数据被移除掉了。在场景结构层次，可见性删除技术可以避免渲染观察着看不见的部分。这些物体在渲染之前就被丢弃掉了以便于不把这些数据送到渲染硬件中去。可见性删除技术可以更深层次的分成背面剔除法，视锥体剔除法和遮挡剔除法。简单的讲，背面剔除法就是将背对于观察者的物体的表面被丢弃；视锥体剔除法就是将观察者视角外的物体忽略掉；遮挡剔除法就是试图将从观察者视线内的被其他物体完全遮挡的物体丢弃掉（如图4）。
图4（a）视锥体剔除法将观察者视线外的物体丢弃掉。
    (b)遮挡剔除法将被其他物体挡住的物体丢弃掉。

3.1场景结构优化

为了实现在可见性剔除算法的光敏感输出，它们不能简单的重复计算整个场景中的物体并且决定哪一个是可见的。我们应用一种特定的数据结构来将场景中的物体分组，这样的话，用一个简单的查询，算法就可以一下子决定是接受还是丢弃一组物体。我们还可以建议使用分等级的数据结构来根据物体的位置来将场景中的物体归成几个区域。通过这种方式，如果一个特定的区域被发现是相对于观察者来讲是不可见的或是隐藏的那么大部分的物体将不会被渲染。为了得到这些分级的数据结构场景必须要被预处理。假设这个预处理是非常耗费时间的，那么它必须在初始化阶段被完成。
我们应用混合式八叉树作为空间数据结构来存储3-D引擎中的物体。我们选择八叉树的主要原因是基于我们回顾其他的优化技术，我们优化的场景结构的可适应性可以扩展到不同的算法。八叉树模型用一个立方体顺着三个纬度来一次性的划分空间物体。在每一个阶段，用八个相等的立方体沿着三个轴面上均匀的划分整个场景（xz,xy和yz面）。图5证明在2维视角上验证了这个过程。

图5 一个二维版本的八叉树的四方块的构建。每个面上再递归的划分为四个相等的小的相等的四方块，直到里面的物体为空或是一整个物体。
这样就可以创建一个每个节点都包含有八个字节点的树。通过划分每个物体都会和它所嵌套子节点的的相应的立方体相关联。如果一个物体恰好被一个面所划分（图5 的c）,那么这个物体就可以用几种方法来处理。一种方法就是根据与划分面的关系来划分物体，根据物体在他的子节点的所关联的立方体的空间尺度来关联部分物体。分裂算法有点复杂并且这种方法同时也会增加场景中物体的数量。另外一种方法就是将原始的物体既可以与它的父节点相关联也可以与它的装入的子节点相关联。当立方体为空时，或是一整个物体都包含在立方体时就停止向下划分（图5的d）。当算法结束时，实际的物体都会包含在八叉树的叶节点内，每个叶节点会包含少于或是等于指定的物体的数量。

3.2物体的可见性剔除

视锥体剔除法是通过执行观察者视角与装入最大立方体的一系列物体的交集测试来运行的，如果测试失败则将这些物体在最初的阶段裁减掉，否则进行与最小的立方体进行一次最终的测试。八叉树不仅可以很好的应用在静态的场景，同时它也可以方便的应用于动态的场景中。遮挡剔除法算法可以紧接着应用于丢弃掉其他的一大部分不在观察者视线内的物体，尤其对于场景内物体密度比较大的情况更加有效。张提出了一种比较新颖的应用分级的空间图形遮挡地图的遮挡剔除算法。这个算法有两部分测试组成：一个在Z轴方向上的一维度深度测试和两维度的空间图形的交迭测试来共同决定一个物体是否被遮挡住。
对于两维度的交迭测试，一个遮挡表示就是被渲染一系列潜在的很好的遮光板而构建的，这个遮挡在场景结构完成时就被确定了。张还建议一些大的或比较靠近观察者的物体当作比较好的遮光板。这些遮光板被渲染成没有纹理，灯光和开启Z-buffering的一块在黑背景下的一块白颜色的脱离屏幕的图形缓冲。这些操作允许将一些列小的遮光板拼成一块大的遮光板。这个被渲染过的图像就是最高分辨率的遮挡地图，这个方案是基于分级的遮挡地图的。这个层级是通过从最高分辨率向下到最小分辨率一层层递归取样形成的，象图6所示。图形硬件可以用缩小倍率的过滤的双线性插补的纹理映射来加速这个过程。

图6  a 接近建立一个遮挡图的遮光板
（b）在不同级别的分层次的遮挡图
交集测试是通过测试物体是否投影在屏幕空间的范围内，这一点和分层次的遮挡图形的同尺寸的像素对应于相同尺度的边框内的尺寸是不一样的。如果边框内所有的元素与映射的交集为不透明（全白），那么这个算法就认为这个物体是被遮挡的。然而，这个算法会递归的检查比它低一层次的不透明的像素。这个算法独特的一点是比较接近可见性剔除，也就是忽略掉对那些仅通过小洞或是透过遮光物体才能见到的物体的渲染。对于这点，在遮挡映射里像素并不完全等同于全部透明，而是相对于一个透明的阈值（灰度）。这个值越小那么这个算法就越接近于剔除，场景内物体会由于被忽略渲染而导致部分可见。张已经得出了一个计算在层次中的不同等级的阈值的公式。这个特征就好像是增加剔除率，当场景不需要物体被看见事可以通过一些遮挡物的一些小的和一些不是特别清醒的图来代替这个物体。
一维度的Z-depth 是用来检查一个物体是否在遮挡物体的后面。张提议用深度估计缓冲来将屏幕分成一系列的小的矩形区域。对于每个区域，所有的遮挡物体的视线内的最远的顶点的z-value被加入缓冲。深度估计缓冲在每一帧祯都需要建立。在渲染是，如果一个物体的所占的体积的最近的顶点的Z-value要比这个物体所能覆盖的区域的所存储的Z-value都大的话，这个物体才会通过深度测试。为了使一个物体被遮挡，这个物体必须同时能通过用分级的遮挡映射的交集测试和用深度估计缓冲的深度测试才行。

3.3动态物体的优化
为了处理八叉树内的动态物体，最直接的方法就是每次当物体运动是，就在八叉树内把它删除掉，接下来通过插入它的新位置。这并不是最佳的处理方法，因为这样会使我们陷入到频繁修改八叉树的结构。举个例子来说，删除八叉树的节点有时会合并刚刚分开的节点，就像图7所示。另外，它还经常需要一个很长的路径来寻找物体的相对于根节点的插入的新节点。为了避免因为删除和建立节点而频繁更新八叉树，Sudarsky建议仅更新那些具有最少共同祖先的子树的物体的新老位置。（图8）对于一个八叉树很深的大场景，这种方法会很明显的减少更新八叉树的时间，因为LCA要比根节点更加接近叶节点。
为了避免对每个动态物体的每一帧都要更新八叉树的结构，Sudarsky用了一个懒惰计算技术，即我们在一个物体是绝对需要的之前不计算任何事情。这就需要一个与每个动态物体相关联的临时的边界体（TBV）。这个TBV是一个保证在某些特定时间内能包含一个动态物体的边界体。这段时间就是指TBV的有效时间，失效其就是这个时间的最后时刻。现在比较流行的TBV的构建方法往往基于一些物体运动和行为的前期知识。举个例子，sweep曲面可以用作TBV的物体上的边界；如果最大的速度和加速度已知的话，球形也是可以用的。应用这种技术，动态物体的TBV可以用在上述视锥体剔除法的交集测试中。在下列情况下一个运动的物体可以被认为是个隐藏的或是不可见的：(1)它的TBV是可见的，也就意味着物体本身可能是可见的；(2)它的TBV过期了,意味着这个TBV不再保证包含一个物体了。一个优先队列用来存储所有的TBV的过期的数据。为了得到更适宜的性能，我们所关心的有效期必须被关闭。一个适当的算法在大多数环境下都能很好的应对这种情况。如果一个物体在确实被看见之前它的TBV就过期了，也就意味着它的有效期太短并且在下一个TBV中将赋予它更长的有效期。相比之下，如果一个 TBV在它过期之前就被看见了，那么在下一个TBV中将赋予它更短的有效期。

图8）当动态物体被更新是八叉树的节点经常被删掉和建立。
   （a）最初有两个物体的八叉树
(b)一个动态物体从八叉树内被删除
(c)动态物体又被重新插入到新的位置

3.4物体的几何优化
场景物体的几何数据可以通过试图产生代表从不同观察者的距离的物体的不同层次细节（LOD）进一步的优化。这种情况的背后的原因是我们不需要展现所有的完整的物体的数据因为物体距离我们比较远并且在图形上看起来很小。我们只需要展现那些距离观察者比较近的物体的完整数据，这些物体的精细的数据都可以被展现出来。这样就可以明显的减少物体的数据，因为我们只需要发送那些最需要物体到渲染引擎里去。图9证明了一个Stanford兔子在LOD控制下在两个相对于观察者不同的距离下的显示情况。

图9（a）最高细节的原始的兔子模型（35947个顶点，69451个三角形）
（b）相对于观察者比较远的距离情况下同样的减少了LOD的兔子模型
(c)一个扩大（b）的版本，展示给我们一个粗糟的兔子模型（359个顶点，508个三角形）
通过简化物体的LOD控制是一种为了提高我们3-D引擎性能的必须的技术。LOD两个比较出名的简化技术是分数倍采样和聚类方法。分数被采样是在分类的基础上减少顶点、边或是三角形。那些对于整个显示贡献比较少的顶点将被标注为候选顶点。当一个最不重要的顶点被刈除后，剩下的漏洞将被补上。这个过程一直到达到预期的目的后才会结束。在聚类方法中，一组高权重的顶点将被预决定了。靠近这些顶点的周围的一些顶点将被聚类。只有那些权重高的顶点被送到渲染引擎中去，这些顶点都关联着网格的形成。这种方法非常快但是这种简化的方法的质量比较差。
简化算法的保真度可以通过在简化过程中瞄准那些小的共面的网格来得以提高。为了得到这些网格，可以用长度，面积，体积，角度等，来测量每个顶点的其他临近的顶点。当这些共面的顶点被刈除或是被大的三角形代替，多边形的数量减少了，但是物体的形状仍和原来物体相差不多。这样原来的物体将被尽可能多的保留下来。

4.将来3-D游戏引擎

上面我们讨论的所有的算法都是串行的，都是设计运行在一个处理器的计算机上。尽管今天主流的游戏者都在用这种配置，多处理器的计算机是未来工业的一种趋势。现在在多处理器上的3-D引擎算法方面作了很多的研究工作。Rohlf and Helman解释了3-D引擎的不同构件之间如何用不同的并行散发进行优化。他们研究的3-D引擎用多处理技术来划分多个处理器之间的工作，并且用管道来管理数据。他们同时也证明了处理器如何同步在不同环境下它们之间的操作。
Igehy介绍了一个感兴趣的方向将OpenGL程序接口扩展到并行处理上。他的扩展允许多个绘图设备同时来画一张图。最初所包括的同步化是允许并行横行一个明确的有序的场景。在一个24处理器的系统上应用这个程序接口的运行证明了它的有效性。

5.总结
我们已经介绍了一些主要的方面来执行一个实际的3-D游戏引擎。这个引擎的设计是轻便的和有效的，因为它允许游戏程序有效的构建和控制场景对象。我们也强调了很多3-D引擎应用的优化技术。光敏感输出是我们在3-D引擎中所用算法的必要部分。在场景和物体层面为了将对静态和动态物体的渲染性能提高到最大优化是必须要做的。最后，简单讨论了一些额外的用来提高并行处理的3-D引擎性能的源码。

评论: 0　查看评论　发表评论

找优秀程序员，就在博客园

最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐：史上最强女游戏程序员

网站导航：博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

by Kylinx

一个游戏引擎做好了，最重要的是缺什么？脚本。打个比方，游戏引擎是一部电脑，则脚本就是电脑的软件。既然脚本这么重要，那该怎样实现呢？下面我就来说说我的做法。

首先理解一下消息循环
一个好的游戏离不开好的消息循环。它是游戏实现很重要的一部分。下面我就来说说我的游戏《宿命传说》的做法。

首先，我定义了一个全局变量extern int GameState;
在游戏中定义了许多当前的游戏状态例如

#define GAME_STATE_CUSTOM 0 //这代表在战斗中玩家可以控制游戏
#define GAME_STATE_TALKING 1

等等。
好了，下面在WinMain里面的while(1)循环中有个UpdateScreen()函数

原型为
void UpdateScreen()
{
    延时
    switch(GameState)
    {
        case GAME_STATE_CUSTOM:
            画出地图
            画出所有精灵
            画出天气（如果有的话）
            如果玩家选中了敌人的话（打个比方DrawFlag=DrawEnemyState）就显示敌人的移动范围和敌人状态
        break;
        case GAME_STATE_TALKING:
            GameDialogProc();
        break;
        case GAME_STATE_SCRIPTCONTROLLING:
            ScriptControlProc();
        break;
        ….//其他的消息在这里处理
    }
    将缓冲表面的图象显示到屏幕;
}

每个游戏状态都需要一个独立的函数来写。这样在每次切换游戏状态时都不会出现无法处理的情况。
在处理键盘消息的时候我也用一个个独立的函数来写
如处理回车键我用了 KeyReturnProc()来控制
在这个函数里同样也少不了switch(GameState)这一句，为什么？
答案很简单，比如说在精灵行走时回车键就没有用，这是我没有处理精灵行走这个状态的键盘消息。而在战斗场景里按下回车键，如果有精灵在选择框里的话，就会处理相应的东西。
例如选择了敌人则使DrawFlag=DrawEnemyState;这样在更新屏幕时就会画出敌人的移动范围和状态。
明白了吗？好了，如果你明白了消息循环的原理，下面的东西就很容易理解了。

下面谈谈脚本控制
要实现这个，就必须在UpdataScreen()这个函数中拦截一个“脚本控制”的消息，并调用相应的处理函数:ScriptControlProc();
那么怎样得到“脚本控制”这个消息呢？
我是这样约定的：新游戏->调用脚本
"战斗结束"->调用脚本
“前往下一个地点”->调用脚本
好了，就只有这几种情况下才调用，调用脚本的函数为BeginScriptControl();
这个函数做了三个工作：
1．首先读取舞台（场景）角色的数据（没一关都是一个不同的舞台）
2．打开脚本文件（注意要用全局的文件指针）（虽然我在源程序中没直接打开，但是原理是一样的）
3．将游戏状态设定为“脚本控制”以便在下一次UpdateScreen()中调用的是ScriptControlProc();（怎么样？知道消息循环的作用了吧？）
ScriptControlProc()这个函数其实也很简单：
读取脚本文件中的参数直到文件结束

读取脚本文件需要一个解释脚本的函数LoadParam(FILE*fp);
这个函数负责解释脚本中的东西：是函数调用还是函数参数
然后找到相应的函数执行即可
比如说脚本里有一段代码MovePlayerTo(1,1,1);
意思就是把第1个玩家移动到1，1处
怎样做呢？
我是按照以下几步做的
1．保存当前的游戏状态
2．把当前游戏状态设定为“移动精灵”
当引擎得到“移动精灵”这个函数后，在UpdataScreen()中调用的是
MoveRoleProc()这个函数
当移动结束后，MoveRoleProc()调用EndMoveRole()，这个函数的作用就是
读取先前的游戏状态

怎么样？又回到读脚本了吧？记住在移动角色的时候脚本文件的指针没有改变，
所以回到读脚本的这个函数后不是重新读取而是继续读取！
同理其他的脚本指令如LoadDialog也是一样的道理！
当文件要结束的时候，别忘了告诉引擎该停止了，这时候我们必须更新游戏状态
脚本里的SetGameState就是负责这项工作的。

评论: 0　查看评论　发表评论

找优秀程序员，就在博客园

最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐：史上最强女游戏程序员

网站导航：博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

Introduction To DirectPlay
翻译：杨冰（源代码之光）
E-Mail:iceryeah2000@163.com
创建时间：2002-9-11
最后修改时间：2002-10-1
备注：此章节是在翻译完Using DirectPlay章节后翻译的，对很多术语的翻译都经过了很长时间的考虑，可能还有不妥之处，会在以后更正。

目录：
　　Creating and Managing Sessions
　　DirectPlay Network Communication
　　DirectPlay Transport Protocol
　　Communicating with DirectPlay Objects
　　DirectPlay Lobby Support
　　
正文：

Microsoft? DirectPlay? API为开发者提供了开发诸如多人游戏或聊天程序的工具。一个多人游戏有两个基本特性：
1 两个或更多的独立用户，每个用户都拥有客户端游戏程序
2 网络连接了用户的电脑（通过中央电脑服务器连接）
DirectPlay提供了一个额外的层，使你的游戏和网络底层相隔。并且，你的游戏可以非常简单的使用DirectPlay API，并使用DirectPlay管理网络通讯。DirectPlay提供的特性，使多人游戏在开发中得到了很多简化。其中包括：
1 创建和管理点对点，客户/服务会话（Session）
2 在一个会话中管理用户（User）和组(Group)
3 管理在不同网络平台上进行会话的成员之间发送的消息
4 使游戏在大厅（Lobby）中互动
5 使用户可以进行语音互动

　　这部分的文档（Introduction To DirectPlay）高度概括了DirectPlay的功能。随后的章节将告诉你DirectPlay的细节和如何在你的游戏中使用DirectPlay。

Creating and Managing Sessions
　　游戏会话是一个特殊的多人游戏。会话中会有两个或者更多的用户同时在线，用户彼此拥有相同的游戏客户端。角色（Player）在游戏中是一个实体，它被游戏所定制。每个用户可以拥有多个角色。不过，游戏必须自己管理这些角色，使用DirectPlay接口对象来管理这些角色。

创建会话的第一步就是收集一组用户的信息。有两种方式：
1 大多数游戏会话都被一个运行在远程计算机上大厅程序（lobby application）所管理。大多数基于Internet的游戏都用这种方式。
2 各个用户自己相互进行联系。这种方式一般用在小型的局域网中。并且游戏不是很大。

会话被管理后，游戏就可以被连接。在会话过程中，角色可能从会话中退出，或者新的角色被加入。

　　在多人游戏中，同一会话中的用户UI应该进行同步。管理多人游戏会话应该反复发送消息流给每个用户。比如，每当角色移动，一个消息就应该被发送，以便在所有其他游戏客户端更新角色的位置。DirectPlay的核心就是为所有在一个会话中的计算机发送高效安全的消息。

有两种基本方式来组织会话消息，一种是点对点，一种是客户/服务模式。讲这两种模式的资料很多，这里就不再复述。

DirectPlay Network Communication
　　 DirectPlay的主要功能是使游戏和网络底层分开。如果你需要发送状态更新的消息，你可以很简单的调用DirectPlay API，不必在意复杂的网络连接情况。DirectPlay网络服务提供了多种网络连接支持：TCP/IP, IPX, modem, 和 serial links。

DirectPlay Transport Protocol
　　 DirectPlay网络核心是DirectPlay协议。这个传输层协议在DirectPlay8中完全重写，现在已经被用在所有的消息中。DirectPlay协议重点放在让你可以很简单的发送消息。协议为多人游戏提供了很多量身定制的特性，包括：
1 可靠和不可靠的消息传递。可靠传递的消息是不断的发送，直到目标程序确信接收了他们。你可以根据你的情况分配消息的具体发送方法。
2 连续和非连续消息传递。连续消息被一个个传送到目标程序中。
3 消息分割和打包。当消息的大小超过网络的许可，DirectPlay将自动进行分割和重组打包。
4 阻塞控制。DirectPlay会自动控制（throttles）你传出消息的速度，使目标程序能够执行和接收消息。
5 发送顺序。要确保重要的消息被首先发送，DirectPlay可以设置消息的发送级别，其中包括low, medium, 和 high priority。High priority（最高优先发送）消息被最先送上消息队列的前端，然后是medium和low。
6 消息超时处理。防止消息队列被阻塞，DirectPlay允许你分派每个消息一个超时值，当这个消息超时后，便从消息队列中移除。 DirectPlay Addresses

为了传送消息，每个加入多人游戏的人都要有一个唯一的地址。运行游戏客户端的电脑提供设备地址，而游戏主机将提供主机地址。

DirectPlay的地址是一个URL字符串。这些字符串由如下格式构成：
x-directplay:/[data string]
在不同的网络连接上，它包含发送消息方和接收方这样的元素。
DirectPlay地址对象会生成URL字符串。依你的熟练程度，你可以直接使用URL地址或者通过DirectPlay地址对象来管理URL。（using the methods exposed by the address object to handle each element of the data string separately）

Communicating with DirectPlay Objects
　　 DirectPlay其实是基于COM的。各个组件管理各个不同的方面。比如，DirectPlay点（peer）对象(CLSID_DirectPlay8Peer)，就是负责管理点对点游戏的。

你通过组件的接口来和它通讯。比如，在点对点游戏中，你发送给另外用户数据时，使用IDirectPlay8Peer::SendTo。DirectPlay会发送消息到目标。

DirectPlay通过很多callback functions（回调函数）进行联系。在原理上，这些函数和windows程序使用得回调函数一样。游戏执行这些callback function，在DirectPlay初始化期间传送函数指针。当DirectPlay需要通讯时，它调用callback function，并且传递两个重要信息：
1 鉴定消息类别ID。
2 一个数据块指针，一般是一个结构体。

比如，当一个消息发送上面的信息到目标，目标程序的callback function将接收到DPNMSGID_RECEIVE消息ID，指出那个消息已经到达。并伴随着包含数据的结构。

因为大多数的DirectPlay消息是多线程的，其中关键就是callback function如何被恰当的执行。

DirectPlay Lobby Support
　　大厅（Lobby）主要的任务是安排角色会面和安排游戏。大厅服务器（Lobby servers）一般还有其他功能，比如主持聊天室，发送新闻和信息，主持商业买卖。大厅服务器可以便利的使用和安排多人游戏工作，但它不是必需的。多人游戏也可以直接在大厅客户端之间进行通讯（lobby clients）。

一个具有大厅的多人游戏，由三个部分组成：
1 大厅服务器
2 大厅客户端
3 支持大厅的游戏（A lobbyable game）

DirectPlay没有具体的告诉大厅服务器如何工作，你可以自己安排。DirectPlay提供了对大厅客户端的支持。一个大厅客户端通过大厅服务器连接程序(vendor)进行工作，连接程序被安装到用户的系统上。它就像一个链，来连接用户和大厅。当你要直接进行通讯，你必须知道每个大厅的工作细节。

大厅客户端游戏接收大厅服务器的通讯细节，使用恰当的通讯协议。大厅客户端进行用户和游戏程序之间的通讯。游戏也能使用接口传送消息给大厅客户端。

大厅实际可以连接任何程序。不过，游戏必须有某些具体的大厅支持组件（lobby-aware components）。一般的，一个支持大厅的游戏可以通过会话和大厅客户端进行联系。如果游戏被注册成支持大厅，大厅客户端能自动的接收更新信息，并在游戏里进行相应的更新。诸如host migration。

评论: 0　查看评论　发表评论

找优秀程序员，就在博客园

最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐：史上最强女游戏程序员

网站导航：博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

评论: 0　查看评论　发表评论

找优秀程序员，就在博客园

最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐：史上最强女游戏程序员

网站导航：博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

不想让ime显示默认的窗口，只想用它的转换和选字功能，看过拿铁游戏论坛上的一个兄弟的一些代码，修正了一些我认为的bug，加入了一组控制函数，使得程序中可以显示一些button，玩家可以不必用热键就能切换输入法、全角/半角，中/英文标点。

//不知道这个能不能解决缩进的问题


下载演示例子

评论: 0　查看评论　发表评论

找优秀程序员，就在博客园

最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐：史上最强女游戏程序员

网站导航：博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

在这一节中就要向大家介绍另外一个重要的部分，并且也是最头疼的部分：线程同步和数据保护。

　　关于线程的概念我在前面的章节中已经介绍过了，也就在这里不累赘—“重复再重复”了。有一定线程基础的人都知道，线程只要创建后就如同脱缰的野马，对于这样的一匹野马我们怎么来进行控制和处理呢？简单的说，我们没有办法进行控制。因为我们更本就没有办法知道CPU什么时候来执行他们，执行他们的次序又是什么？

　　有人要问没有办法控制那我们如何是好呢？这个问题也正是我这里要向大家进行解释和说明的，虽然我们不能够控制他们的运行，但我们可以做一些手脚来达到我们自己的意志。

　　这里我们的做手脚也就是对线程进行同步，关于同步的概念大家在《操作系统》中应该都看过吧！不了解的话，我简单说说：读和写的关系（我读书的时候，请你不要在书上乱写，否则我就没有办法继续阅读了。）

处理有两种：用户方式和内核方式。
用户方式的线程同步由于有好几种：原子访问，关键代码段等。

　　在这里主要向大家介绍关键代码段的处理（我个人用的比较多，简单实用）。先介绍一下它的一些函数，随后提供关键代码段的处理类供大家参考（比较小，我就直接贴上来了）

VOID InitializeCriticalSection( //初始化互斥体
    LPCRITICAL_SECTION lpCriticalSection // critical section
);

VOID DeleteCriticalSection( //清除互斥体
    LPCRITICAL_SECTION lpCriticalSection // critical section
);

VOID EnterCriticalSection( //进入等待
    LPCRITICAL_SECTION lpCriticalSection // critical section
);

VOID LeaveCriticalSection( //释放离开
    LPCRITICAL_SECTION lpCriticalSection // critical section
);

以上就是关于关键代码段的基本API了。介绍就不必了（MSDN）。而我的处理类只是将这几个函数进行了组织，也就是让大家能够更加理解关键代码端

.h
class CCriticalSection //共享变量区类
{
public:
    CCriticalSection();
    virtual ~CCriticalSection();
    void Enter(); //进入互斥体
    void Leave(); //离开互斥体释放资源
private:
    CRITICAL_SECTION g_CritSect;
};

.cpp
CCriticalSection::CCriticalSection()
{
    InitializeCriticalSection(&g_CritSect);
}

CCriticalSection::~CCriticalSection()
{
    DeleteCriticalSection(&g_CritSect);
}

void CCriticalSection::Enter()
{
    EnterCriticalSection(&g_CritSect);
}

void CCriticalSection::Leave()
{
    LeaveCriticalSection(&g_CritSect);
}

由于篇幅有限关键代码段就说到这里，接下来向大家简单介绍一下内核方式下的同步处理。

　　哎呀！这下可就惨了，这可是要说好多的哦！书上的罗罗嗦嗦我就不说了，我就说一些我平时的运用吧。首先内核对象和一般的我们使用的对象是不一样的，这样的一些对象我们可以简单理解为特殊对象。而我们内核方式的同步就是利用这样的一些特殊对象进行处理我们的同步，其中包括：事件对象，互斥对象，信号量等。对于这些内核对象我只向大家说明两点：
1．内核对象的创建和销毁
2．内核对象的等待处理和等待副作用

第一：内核对象的创建方式基本上而言都没有什么太大的差别，例如：创建事件就用HANDLE CreateEvent(…..),创建互斥对象 HANDLE CreateMutex(…….)。而大家注意的也是这三个内核对象在创建的过程中是有一定的差异的。对于事件对象我们必须明确指明对象是人工对象还是自动对象，而这种对象的等待处理方式是完全不同的。什么不同下面说（呵呵）。互斥对象比较简单没什么说的，信号量我们创建必须注意我们要定义的最大使用数量和初始化量。最大数量>初始化量。再有如果我们为我们的内核对象起名字，我们就可以在整个进程中共用，也可以被其他进程使用，只需要OPEN就可以了。也就不多说了。

第二：内核对象的等待一般情况下我们使用两个API：
DWORD WaitForSingleObject( //单个内核对象的等待
            HANDLE hHandle, // handle to object
            DWORD dwMilliseconds // time-out interval
);

DWORD WaitForMultipleObjects( //多个内核对象的等待
            DWORD nCount, // number of handles in array
            CONST HANDLE *lpHandles, // object-handle array
            BOOL fWaitAll, // wait option
            DWORD dwMilliseconds // time-out interval
);

具体怎么用查MSDN了。

　　具体我们来说等待副作用，主要说事件对象。首先事件对象是分两种的：人工的，自动的。人工的等待是没有什么副作用的（也就是说等待成功后，要和其他的对象一样要进行手动释放）。而自动的就不一样，但激发事件后，返回后自动设置为未激发状态。这样造成的等待结果也不一样，如果有多个线程在进行等待事件的话，如果是人工事件，被激活后所有等待线程成执行状态，而自动事件只能有其中一个线程可以返回继续执行。所以说在使用这些内核对象的时候，要充分分析我们的使用目的，再来设定我们创建时候的初始化。简单的同步我就说到这里了。下面我就将将我们一般情况下处理游戏服务器处理过程中的数据保护问题分析：

首先向大家说说服务器方面的数据保护的重要性，图例如下：

用户列表

　　　　用户删除

　　　　用户数据修改

　　　　使用数据

加入队列

　　对于上面的图例大家应该也能够看出在我们的游戏服务器之中，我们要对于我们用户的操作是多么的频繁。如此频繁的操作我们如果不进行处理的话，后果将是悲惨和可怕的，举例：如果我们在一个线程删除用户的一瞬间，有线程在使用，那么我们的错误将是不可难以预料的。我们将用到了错误的数据，可能会导致服务器崩溃。再者我们多个线程在修改用户数据我们用户数据将是没有办法保持正确性的。等等情况都可能发生。怎么样杜绝这样的一些情况的发生呢？我们就必须要进行服务器数据的保护。而我们如何正确的保护好数据，才能够保持服务器的稳定运行呢？下面说一下一些实际处理中的一些经验之谈。

1．我们必须充分的判断和估计我们服务器中有那些数据要进行数据保护，这些就需要设计者和规划者要根据自己的经验进行合理的分析。例如：在线用户信息列表，在线用户数据信息，消息列表等。。。。。

2．正确和十分小心的保护数据和正确的分析要保护的数据。大家知道我们要在很多地方实现我们的保护措施，也就是说我们必须非常小心谨慎的来书写我们的保护，不正确的保护会造成系统死锁，服务器将无法进行下去（我在处理的过程中就曾经遇到过，头都大了）。正确的分析要保护的数据，也就是说，我们必须要估计到我们要保护的部分的处理能够比较快的结束。否则我们必须要想办法解决这个问题：例如：

DATA_STRUCT g_data;
CRITICAL_SECTION g_cs;

EnterCriticalSection(&g_cs);
SendMessage(hWnd,WM_ONEMSG,&g_data,0);
LeaveCriticalSection(&g_cs);

以上处理就有问题了，因为我们不知道SendMessage（）什么时候完成，可能是1/1000豪秒，也可能是1000年，那我们其他的线程也就不用活了。所以我们必须改正这种情况。

DATA_STRUCT g_data;
CRITICAL_SECTION g_cs;

EnterCriticalSection(&g_cs);
PostMessage(hWnd,WM_ONEMSG,&g_data,0);
LeaveCriticalSection(&g_cs);

或者 DATA_STRUCT temp_data;

EnterCriticalSection(&g_cs);
temp_data = g_cs;
LeaveCriticalSection(&g_cs);
SendMessage(hWnd,WM_ONEMSG,& temp_data,0);

3．最好不要复合保护用户数据，这样可能会出现一些潜在的死锁。

　　简而言之，服务器的用户数据是一定需要进行保护，但我们在保护的过程中就一定需要万分的小心和谨慎。这篇我就说到这里了，具体的还是需要从实践中来进行学习，下节想和大家讲讲服务器的场景处理部分。

评论: 0　查看评论　发表评论

找优秀程序员，就在博客园

最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐：史上最强女游戏程序员

网站导航：博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

　　在游戏的编写中，不可避免的出现很多应用数据结构的地方，有些简单的游戏，只是由几个数据结构的组合，所以说，数据结构在游戏编程中扮演着很重要的角色。
　　本文主要讲述数据结构在游戏中的应用，其中包括对链表、顺序表、栈、队列、二叉树及图的介绍。读者在阅读本文以前，应对数据结构有所了解，并且熟悉C/C++语言的各种功用。好了，现在我们由链表开始吧！

1、链表
　　在这一节中，我们将通过一个类似雷电的飞机射击游戏来讲解链表在游戏中的应用。在飞机游戏中，链表主要应用在发弹模块上。首先，飞机的子弹是要频繁的出现，消除，其个数也是难以预料的。链表主要的优点就是可以方便的进行插入，删除操作。我们便将链表这一数据结构引入其中。首先，分析下面的源代码，在其中我们定义了坐标结构和子弹链表。

　　struct CPOINT
　　{
　　　　int x;　　// X轴坐标
　　　　int y;　　// Y轴坐标
　　};

　　struct BULLET
　　{
　　　　struct BULLE* next;　　// 指向下一个子弹
　　　　CPOINT bulletpos;　　　// 子弹的坐标
　　　　int m_ispeed;　　　　　// 子弹的速度
　　};

　　接下来的代码清单是飞机类中关于子弹的定义：

　　class CMYPLANE
　　{
　　public:
　　　　void AddBullet(struct BULLET*);　　// 加入子弹的函数，每隔一定时间加弹
　　　　void RefreshBullet();　　　　　　　// 刷新子弹
　　privated:
　　　　struct BULLET *st_llMyBullet;　　　// 声明飞机的子弹链表
　　};

　　在void AddBullet(struct BULLET*)中，我们要做的操作只是将一个结点插入链表中，并且每隔一段时间加入，就会产生连续发弹的效果。
　　这是加弹函数主要的源代码：

　　void AddBullet(struct BULLET*)
　　{
　　　　struct BULLET *st_llNew,*st_llTemp;　　// 定义临时链表
　　　　st_llNew=_StrucHead;　　　　　　　　　 // 链表头（已初始化）
　　　　st_llNew->(BULLET st_llMyBullet *)malloc(sizeof(st_llMyBullet));　　// 分配内存
　　　　st_llTemp= =_NewBullet;　　　　　　　　// 临时存值
　　　　st_llNew->next=st_llTemp->next; st_llTemp->next=st_llNew;
　　}

　　函数Void RefreshBullet()中，我们只要将链表历遍一次就行，将子弹的各种数据更新，其中主要的源代码如下：

　　while(st_llMyBullet->next!=NULL)
　　{
　　　　// 查找
　　　　st_llMyBullet->bulletpos.x-=m_ispeed;　　// 更新子弹数据
　　　　………
　　　　st_llMyBullet=st_llMyBullet->next;　　　 // 查找运算
　　}

　　经过上面的分析，在游戏中，链表主要应用在有大规模删除，添加的应用上。不过，它也有相应的缺点，就是查询是顺序查找，比较耗费时间，并且存储密度较小，对空间的需求较大。
　　如果通过对游戏数据的一些控制，限定大规模的添加，也就是确定了内存需求的上限，可以应用顺序表来代替链表，在某些情况下，顺序表可以弥补链表时间性能上的损失。当然，应用链表，顺序表还是主要依靠当时的具体情况。那么，现在，进入我们的下一节，游戏中应用最广的数据结构 — 顺序表。

2、顺序表
　　本节中，我们主要投入到RPG地图的建设中，听起来很吓人，但是在RPG地图系统中（特指砖块地图系统），却主要使用数据结构中最简单的成员 — 顺序表。
　　我们规定一个最简单的砖块地图系统，视角为俯视90度，并由许多个顺序连接的图块拼成，早期RPG的地图系统大概就是这样。我们这样定义每个图块：

　　struct TILE　　// 定义图块结构
　　{
　　　　int m_iAcesse;　　// 纪录此图块是否可以通过
　　　　……　　　　　　　// 其中有每个图块的图片指针等纪录
　　};

　　当m_iAcesse=0,表示此图块不可通过，为1表示能通过。
　　我们生成如下地图：

　　TILE TheMapTile[10][5];

　　并且我们在其中添入此图块是否可以通过，可用循环将数值加入其中,进行地图初始化。
　　如图表示：

　　从上图看到这个地图用顺序表表示非常直接，当我们控制人物在其中走动时，把人物将要走到的下一个图块进行判断，看其是否能通过。比如，当人物要走到（1，0）这个图块，我们用如下代码判断这个图块是否能通过：

　　int IsAcesse(x,y)
　　{
　　　　return TheMapTile[x,y].m_iAcesse;　　// 返回图块是否通过的值
　　}

　　上述只是简单的地图例子，通过顺序表，我们可以表示更复杂的砖块地图，并且，现在流行的整幅地图中也要用到大量的顺序表，在整幅中进行分块。
　　好了，现在我们进入下一节：

3、栈和队列
　　栈和队列是两种特殊的线性结构，在游戏当中，一般应用在脚本引擎，操作界面，数据判定当中。在这一节中，主要通过一个简单的脚本引擎函数来介绍栈，队列和栈的用法很相似，便不再举例。
　　我们在设置脚本文件的时候，通常会规定一些基本语法，这就需要一个解读语法的编译程序。这里列出的是一个语法检查函数，主要功能是检查“（）”是否配对。实现思想：我们规定在脚本语句中可以使用“（）”嵌套，那么，便有如下的规律，左括号和右括号配对一定是先有左括号，后有右括号，并且，在嵌套使用中，左括号允许单个或连续出现，并与将要出现的有括号配对销解，左括号在等待右括号出现的过程中可以暂时保存起来。当右括号出现后，找不到左括号，则发生不配对现象。从程序实现角度讲，左括号连续出现，则后出现的左括号应与最先到来的右括号配对销解。左括号的这种保存和与右括号的配对销解的过程和栈中后进先出原则是一致的。我们可以将读到的左括号压入设定的栈中，当读到右括号时就和栈中的左括号销解，如果在栈顶弹不出左括号，则表示配对出错，或者，当括号串读完，栈中仍有左括号存在，也表示配对出错。
　　大致思想便是这样，请看代码片断：

　　struct　　// 定义栈结构
　　{
　　　　int m_iData[100];　　// 数据段
　　　　int m_iTop;　　　　　// 通常规定栈底位置在向量低端
　　}SeqStack;

　　int Check(SeqStack *stack)　　// 语法检查函数
　　{
　　　　char sz_ch;
　　　　int boolean; Push(stack,'# ');　　// 压栈，#为判断数据
　　　　sz_ch=getchar();　　　　　　　　　// 取值
　　　　boolean=1;
　　　　while(sz_ch!='\n'&&boolean)
　　　　{
　　　　　　if(sz_ch= ='(')
　　　　　　　　Push(stack,ch);
　　　　　　if(sz_ch= =')')
　　　　　　　　if(gettop(stack)= ='#')　 // 读栈顶
　　　　　　　　　　boolean=0;
　　　　　　　　else
　　　　　　　　　　Pop(stack);　　　　　 // 出栈
　　　　　　sz_ch=getchar();
　　　　}
　　　　if(gettop(stack)!='#') boolean=0;
　　　　if(boolean) cout<<"right";　　　 // 输出判断信息
　　　　else
　　　　　　cout<<"error";

　　这里只是介绍脚本的读取，以后，我们在图的介绍中，会对脚本结构进行深入的研究。
　　总之，凡在游戏中出现先进后出（栈），先进先出（队列）的情况，就可以运用这两种数据结构，例如，《帝国时代》中地表中间的过渡带。

4、二叉树
　　树应用及其广泛，二叉树是树中的一个重要类型。在这里，我们主要研究二叉树的一种应用方式：判定树。其主要应用在描述分类过程和处理判定优化等方面上。
　　在人工智能中，通常有很多分类判断。现在有这样一个例子：设主角的生命值d，在省略其他条件后，有这样的条件判定：当怪物碰到主角后，怪物的反应遵从下规则：
 

表1

　　根据条件，我们可以用如下普通算法来判定怪物的反应：

　　if(d<100) state=嘲笑，单挑;
　　else if(d<200) state=单挑;
　　　　else if(d<300) state=嗜血魔法;
　　　　　　else if(d<400) state=呼唤同伴;
　　　　　　　　else state=逃跑;

　　上面的算法适用大多数情况，但其时间性能不高，我们可以通过判定树来提高其时间性能。首先，分析主角生命值通常的特点，即预测出每种条件占总条件的百分比，将这些比值作为权值来构造最优二叉树（哈夫曼树），作为判定树来设定算法。假设这些百分比为：

表2

　　构造好的哈夫曼树为：

图2

　　对应算法如下：

　　if(d>=200)&&(d<300) state=嗜血魔法;
　　else if(d>=300)&&(d<500) state=呼唤同伴;
　　　　else if(d>=100)&&(d<200) state=单挑;
　　　　　　else if(d<100) state=嘲笑，单挑;
　　　　　　　　else state=逃跑;

　　通过计算，两种算法的效率大约是2:3，很明显，改进的算法在时间性能上提高不少。
　　一般，在即时战略游戏中，对此类判定算法会有较高的时间性能要求，大家可以对二叉树进行更深入的研究。现在，我们进入本文的最后一节：图的介绍，终于快要完事了。

5、图
　　在游戏中，大多数应用图的地方是路径搜索，即关于A*算法的讨论。由于介绍A*算法及路径搜索的文章很多，这里介绍图的另一种应用：在情节脚本中，描述各个情节之间的关系。
　　在一个游戏中，可能包含很多分支情节，在这些分支情节之间，会存在着一定的先决条件约束，即有些分支情节必须在其他分支情节完成后方可开始发展，而有些分支情节没有这样的约束。
　　通过分析，我们可以用有向图中AOV网（Activity On Vertex Network）来描述这些分支情节之间的先后关系。好了，现在假如我们手头有这样的情节：

　　注意：在AOV网中，不应该出现有向环路，否则，顶点的先后关系就会进入死循环。即情节将不能正确发展。我们可以采取拓扑派序来检测图中是否存在环路，拓扑排序在一般介绍数据结构的书中，都有介绍，这里便不再叙述。
　　那么以上情节用图的形式表现为（此图为有向图，先后关系在上面表格显示）：
 

图3

　　现在我们用邻接矩阵表示此有向图，请看下面代码片断：

　　struct MGRAPH
　　{
　　　　int Vexs[MaxVex];　　　　　　// 顶点信息
　　　　int Arcs[MaxLen][MaxLen];　　// 邻接矩阵
　　　　……
　　};

　　顶点信息都存储在情节文件中。
　　将给出的情节表示成邻接矩阵：

　　我们规定，各个情节之间有先后关系，但没有被玩家发展的，用1表示。当情节被发展的话，就用2表示，比如，我们已经发展了遭遇强盗的情节，那么，C1与C2顶点之间的关系就可以用2表示，注意，并不表示C2已经发展，只是表示C2可以被发展了。
　　请看下面的代码：

　　class CRelation
　　{
　　public:
　　　　CRelation(char *filename);　　　　　　　 // 构造函数，将情节信息文件读入到缓存中
　　　　void SetRelation(int ActionRelation);　　// 设定此情节已经发展
　　　　BOOL SearchRelation(int ActionRelation); // 寻找此情节是否已发展
　　　　BOOL SaveBuf(char *filename);　　　　　　// 保存缓存到文件中
　　　　……
　　privated:
　　　　char* buf;　　　　　　　　　　　　　　 　// 邻接矩阵的内存缓冲
　　　　……
　　};

　　在这里，我们将表示情节先后关系的邻接矩阵放到缓冲内，通过接口函数进行情节关系的修改，在BOOL SearchRelation(int ActionRelation)函数中，我们可以利用广度优先搜索方法进行搜索，介绍这方面的书籍很多，代码也很长，在这里我就不再举例了。
　　我们也可以用邻接链表来表示这个图，不过，用链表表示会占用更多的内存，邻接链表主要的优点是表示动态的图，在这里并不适合。
　　另外，图的另一个应用是在寻路上，著名的A*算法就是以此数据结构为基础，人工智能，也需要它的基础。好了，本节结束。

评论: 0　查看评论　发表评论

找优秀程序员，就在博客园

最新新闻：
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报：QQ的平台化价值是如何创造的？(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐：史上最强女游戏程序员

网站导航：博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库