外文原文及译文

北京联合大学毕业设计（论文）外文原文及译文

题目： 3D游戏开发技术研究与实现--游戏界面、图形渲染、网络功能

专业：计算机科学与技术指导教师：朱淑琴

学院：师范学院学号： 2009020306126

班级： 2009级计算机科学与技术姓名：赵晔

一、外文原文

Collision detection technology and artificial intelligent technology could be applied in the development of game, as well as the areas of education, virtual reality, historic preservation, geo-information system, scientific research, entertainment and business. So, the reinforcing for the research on 3D game technology has great practical significance. And the successful research and development of collision detection technology and artificial intelligent technology that are suitable for 3D game will have huge theoretical significance and practical significance, wide application prospects. With the development of 3D game as platform, this article deeply researches collision detection algorithm and artificial intelligent technology in game, focuses on the problem of large calculation amount, slow calculation speed and imprecise collision detection for collision detection algorithm to improve the collision detection in game by the method of combining class-bounding boxes and segment detection method with space partition method, which could effectively promotes the precision and speed of collision detection algorithm. In addition, this article perfects path search algorithm of game, improves the problems of long-time search, slow searching speed in A* path search algorithm by improving the path search method of A* algorithm, restraining search scope and aggravating the weight of heuristic function.

1.COLLISION DETECTION ALGORITHM

The BVH (bounding volume hierarchy) in collision detection algorithm is one of the most widely used collision detection methods. The crossing test among BBB is simple, but the compactness of BBB collision detection algorithm is bad.This article makes improvement for bounding volume’s compactness and detection method of AABB collision detection algorithm.

Improve the idea: the core of collision detection algorithm is real time and precision. Some game could sacrifice some precision to get real time. The system will adopt collision

detection algorithm based on AABB, and improve the problem of bad compactness and large calculation amount existed in AABB collision detection algorithm to certain extent, with the purpose of making the improved collision detection algorithm simple, speedy and precise. Improvement idea mainly includes the following aspects: 1) apply BSP to discompose space of scene to reduce the calculation amount for collision detection; 2) optimize bounding volume; 3) put forward segment collision detection algorithm to promote the speed of AABB collision detection.

BSP decomposition scene: the precision and speed of collision detection is the important property of game. If we suppose there are 100 objects in world, for RPG game, system has to make collision detection for 100 objects and 1002 calculations of collision detection. If the are other objects existing in system, too large calculation amount and too bad system performance are difficult to be accepted by players. So, it is necessary to promote the speed of collision detection.This article mainly provides the following two methods to promote the speed of collision detection. Firstly, as above mentioned, if the game scene is not decomposed, collision detection has to detect each object for collision, but in these detections, most of collision detection is useless, so, precious time and resource are wasted for idol work in this way. Then how to reduce this situation? Considering from the aspect of data structure, binominal method shall be adopted to decompose scene. Binominal method could not only be used to manage scene, but also be applied into collision detection.Binominal method could divide object into different area. Each unit contains little object, and collision detection could be done in line with area.BSP tree has the advantage to traverse three dimensional spaces along BSP tree.For each iteration, 50% objects that are impossible to conflict in tree dimensional space could be eliminated until the coincident object is found, by comparing central sibling nodes of objects. This method is simple and speedy, which just need log2N, or even N step for bad situation, to finish collision detection. Therefore, the adoption of BSP tree for decomposition scene promotes the speed of collision detection to a great extent so as to reduce the calculation amount for collision detection. Secondly, the speed of collision detection could be promoted from the point of space. Game scene includes static and dynamic object. If the bounding volumes for them are updated continuously, this will cost many time to calculate the bounding volume for all the objects, which undoubtedly increases unnecessary calculation. Because the bounding volume of static does not change, so it is not necessary to update their bounding volume. Accordingly, object in static scene

has already confirmed its bounding volume in calling stage, and does not update their bounding volumes. In order to guarantee the precision of collision detection, the bounding volume of dynamic player must be updated real time.The adoption of this method could reduce the calculation amount of collision detection algorithm to a very great extent, and promote the running speed of game.

Optimize bounding volume: in order to promote the precision of collision detection. But game scene includes dynamic role and static object, if the bounding volume of every object is updated real time, it will increase unnecessary time for calculation. Thus, AABB bounding volume for the object in scene shall be bound in line with class when developing this game. For the static object in scene such as wall, house, tree and other objects with regular shape, only one bounding volume shall be bound, and will not be updated real time, the collision detection in game will be seriously affected.The system just updates the bounding volume of dynamic role real time.The width of bounding volume shall be designed as the maximum stride for the acting movement of role. If the bounding volume is too small, the collision detection will be imprecise, and the collision will shows the phenomenon of distortion; if the bounding volume is too big, the real time of collision will be bad, so, a proper design of bounding volume will produce the effect of getting twofold results with half the effort for the collision detection between objects. The step length of dynamic role also affects the precision of collision detection. If the step length of role is too big, the following situations probably happen: when the previous frame hasn’t collide with object, the next frame probably has gone through this object, which means that the penetration situation is very easy to happen for the object smaller than the step length of role. In order to prevent the penetrating, the step length of role shall be increased properly in the process of producing character animation.

Segment collision detection algorithm: game system has low requirement for the precision of collision detection, but has higher requirement for the running speed of game. The static object in game scene do not need to take collision detection, and the collision would happen only between dynamic role and static object. The scene models of game are mostly regular object, so the adoption of AABB bounding volume is enough to express the object in scene approximately.The collision detection for two AABB objects needs to calculate at least for 6 times, while, if m collision detections are made before collision, 6m calculations between AABB polygons is needed. This not only has large calculation amount, but also waste of time, becase the answer could be obtained only with m

calculations if there is no collision. The method for solution is to make crossing test with ray and static AABB before the collision of two objects. In this process, the AABB side that is possible to collide is confirmed, and is not changed into the side of dynamic AABB role and static AABB that is possible to collide until two objects is going to collide so as to make collision detection. However, the opportunity to decide to displace ray with AABB bounding volume is obtained through the distance of ray and AABB bounding volume of static object. With the improved collision detection algorithm, the calculation amount decreases nearly a half. The algorithm is described as follows: 1) select the central point S of bounding volume of player role and the vector V of moving direction and make a ray with(S, V) as parameter; 2) utilize BSP tree decomposition method to quickly find the area that is probably take collision detection; 3) take the collision detection for the ray and static AABB object: estimate the distance between ray and static AABB object, estimate AABB side that probably collide, eliminate the side that is impossible to collide, if reach the set threshold, then continue; take collision detection for dynamic AABB and static AABB plane, otherwise, turn back to.

2.OPTIMIZATION OF ALGORITHM

Large storage space and slow calculation speed is the biggest disadvantage of A* path search algorithm. This article adopts three methods to optimize and improve path search. With the method of grading for path search, A* algorithm embodies the intelligence of NPC in path search, but has two defects: A* algorithm needs to maintain heuristic information, present node and expanding node, while, it needs inner storage with exponential quantity for worst situation, and objective point searched by A* algorithm are both static, but the player role in this system is dynamic, this obviously increases the complexity for path search. A* path search is rather difficult to achieve. So, it is necessary to improve A* path search algorithm.

By observation，we find that all the optimal routes are the straight line between starting point and objective point in the condition of no obstacle. If there is obstacle, each turning point must locate in the peak of convex polygon of obstacle. On the basis of the above idea for searching path, this system adopts grading path search method, which means that non-player role approach object at the path without obstacle, A* algorithm shall be used for path search when the distance between non-player role and obstacle reaches set threshold d, then the optimal node shall be selected real time to change path. For the movement in the straight line of two points, the extending node is very little, and

calculation amount is very small. Figure 1 is the sketch map for the grading path search method adopted in this article, among which starting point indicates NPC, objective point indicates player role. U is the moving direction of NPC, V is moving direction of player role. The part from starting point NPC to node adopts path movement of straight line. When the distance between NPC and obstacle reaches threshold d, the improved A* algorithm shall be used to make regular path search. Segment path search method will greatly reduce the searching times, and would not increase the searching time for the increase of distance.

Figure 1: the sketch map of segment path search

The steps of improved algorithm: 1) let coordinate point S of non-player role as starting node and coordinate point G of player role as objective node; 2) calculate d=|G-S|;

3) if d

3.EXPERIMENTAL RESULT AND ANALYSIS

Collision detection algorithm: in this procedure, the action responding to collision is that virtual character slides along the edge of the object colliding so as to avoid obstacle. In this process, you have to pay attention to the situation that d is 0. This experiment adopts AABB collision detection algorithm and improved algorithm. Then, compare the experimental data of storage’s calling time and game’s rendering frequency of two algorithms, where 100 groups of experimental data are collected for provision and the average for random selection of 10 groups is made for comparison. The comparison of experimental results is shown in figure 2 and figure 3.

二、译文

碰撞检测技术和人工智能技术可以被应用在游戏发展以及教育、虚拟现实、历史保护、地理信息系统、科研、娱乐和商业领域中。因此，加强对3D游戏技术的研究具有重要的现实意义。并且适用于3D游戏的碰撞检测技术和人工智能技术的成功研发将具有十分重要的理论意义和实现意义，具有广泛的应用前景。随着使用平台开发3D游戏，本文深入研究了碰撞检测算法和人工智能技术在游戏中的应用，以庞大的计算量，使用结合类保卫盒和空间分割段检测法来提高碰撞检测算法的速度慢、碰撞检测计算不精确，可以有效地提高碰撞算法的精确度和速度。此外，本文完善了游戏路径搜索算法，提高了长时间的搜索问题，搜索速度慢在A*路径搜索算法的改进A*算法的路径搜索方法，限制搜索范围和加重的启发函数数量。

1.碰撞检测算法

BVH（层次包围盒的碰撞算法）是一种最为广泛使用的碰撞检测法。BBB的交叉实验是很简单，但是紧密的BBB碰撞测试却很复杂。本文对包围体的密实度和AABB包围盒的碰撞检测算法的检测方法进行了改进。

改进思想：提高碰撞检测算法的核心是实时性和精确度。有些游戏会牺牲一些精确度来的得到实时。该系统采用基于AABB包围盒的碰撞算法，并且使用提高目的碰撞检测算法简单、快速和精确的方法，一定程度的提高了在AABB包围盒碰撞检测算法中密实度差、计算量大的问题。改进思想主要包括以下几个方面：1）应用BSP 分解空间场景来减少碰撞检测的计算量；2）优化包围盒；3）提出了段的碰撞检测算法，来提高AABB碰撞检测的速度。

BSP分解场景：精确度和碰撞检测速度是游戏的重要属性。假设在RPG游戏视图中有100个物体，则系统要做出100个碰撞测试和1002个碰撞测试计算。如果还有其他的对象存在系统中，大量的计算和糟糕的系统是很难被玩家接受的。因此，提高碰撞检测的速度是很有必要的。本文主要提出了一下两种方法来提高碰撞检测的速度。首先，如上所述，如果游戏场景中不分解，碰撞测试就要对每一个对象进行碰撞，但是在这些检测中，大部分的碰撞测试时无用的，一次，宝贵的时间和资源就在这些工作上浪费掉了。那么要如何减缓这种现象呢？从数据结构方面考虑，二叉树的理念可以应用到场景的分解中。二叉树法不仅可以应用在管理场景中，还可以应用到碰撞检测里。二叉树法可以分为不同的区域对象。每个区域由小的对象组成，碰撞测试可以以区域为单位进行。遍历BSP树具有三维空间的优势。对于每次的循环，50%的对象不可能在对象的中心节点找到符合对象时才被树维空间冲突排除掉。该方法快速简单，它只需要log2N一个公式哪怕N是一个很复杂的数字，就能完成碰撞测试。因此，在分解场景采用BSP树有利于碰撞检测，并且在很大程度上减少了碰撞检测的计算

量。其次，可以从空间的角度来提高碰撞检测的速度。游戏场景包括静态和动态对象。如果包围盒不断更新，这将会花费大量的时间去计算包围盒的所有对象，这无疑增加了不必要的计算。由于静态的包围体并没有改变，所以不需要更新他们的包围盒。因此，在静态场景对象中已经确认了它在调用级的包围盒，并没有更新他们的包围盒。为了确保碰撞检测的精确度，动态的对象包围体必须实时更新。采用这样的方法可以很大程度上减少碰撞检测算法的计算量提高游戏运行速度。

优化包围盒：来提高碰撞检测的精确度。但是，游戏场景中包括动态和静态对象，如果每个物体的包围盒都实时更新，这将增加不必要的时间来计算。因此，开发此游戏时使用AABB包围盒对场景中的对象进行测试比较适宜。对于场景中的静态对象如墙、房子、树和其他规则形状的对象只属于一个包围盒，并不会实时更新，这样游戏中的碰撞检测将会受到很大的影响。该系统只实时更新动态对象的包围盒。包围体的宽度应设为对象动作的最大跨度。如果边界体积太小，碰撞检测是不够精确的，碰撞显示也会有失真的现象；如果边界体积过大，碰撞实时将会过长，所以设计一个合理的包围体会使碰撞检测得到事半功倍的效果。动态对象的活动范围也影响着碰撞检测的精确度。如果对象的活动范围过大，可能会发生以下情况：当前的帧没有碰撞到对象，而下一帧又错过了该对象，这意味着很容易出现对象小于活动范围的现象。为了防止漏过，在创建对象动画的过程中应为对象的活动范围制定一个适当的值。

分段的碰撞检测算法：游戏系统对碰撞检测的要求不高，但对游戏的运行速度有着较高的要求。在游戏场景中，静态对象不需要碰撞检测，碰撞只是发生在动态对象和静态对象间。游戏的场景模型大多是普通的对象，因此，采用AABB包围盒足以表达场景中对象的近似。两个AABB包围盒之间的碰撞检测需要计算6次，如果在做碰撞之前有M个碰撞检测，则在AABB包围盒需要6M次的计算。这样不仅计算量大，而且浪费时间，因为如果没有碰撞只需要计算M即可。解决方案是在射线和静态AABB两个物体碰撞之前做交叉测试。在这过程中，AABB测发生冲突是无疑的，不改变动态和静态AABB是可能发生碰撞的，知道两个物体将要碰撞时才会有碰撞检测。然而，机会决定AABB包围盒的移动射线从射线和静态对象AABB包围盒中获得的距离。用改进的碰撞检测算法计算量能减少近一半。该算法描述如下：1）选择玩家角色包围盒的中心点S和移动距离的矢量V并且以（S,V）作为参照做一个射线；2）利用BSP树分解法很快就会发现可能是带碰撞检测的区域；带碰撞检测的射线和静态AABB对象：估计出射线和静态AABB对象之间的距离和AABB包围盒可能发生碰撞，消除不可能发生，如果达到设定的临界值之后继续；带碰撞检测的动态AABB和静态AABB平面，否则，返回。

2.优化算法

大面积的空间和缓慢的计算速度是A*寻路算法的最大不足。本文采用了三种方法来优化和提高路径搜索。随着路径搜索分级法，A*算法体现了NPC在路径搜索的智能，但有两个缺陷：A*算法需要保持启发式信息，现节点和扩充节点，它需要扩大，为最坏情况下的指数数量的内存，目的节点的A*算法的搜索都是静态的，但在这个系统中的玩家角色是动态的，这显然增加了路径搜索的复杂性。A*路径的搜索难以实现。因此，有必要改进A*寻路算法。通过观察，我们发现，所有的路线在没有障碍物的情况下，起始点和终点是直线的。如果有障碍物，每个转折点必须在障碍物的凸多边形的峰值。在上述寻路思想的基础上，本系统采用分级路径搜索方法，即非玩家在没有障碍物的路径上接近对象时，A*算法应用于寻路时在非玩家角色和障碍物范围之间设置一个临界值 d ，然后使最有节点应该选择实时改变路径。对于另一个点间的直线运动而言，延长节点是非常小计算量也会很小。图1是分级寻路法即本文采用的示意图，其中起点显示NPC，终点表示玩家的角色。U是NPC的移动方向，V是玩家的移动方向。从NPC出发点到节点采用直线路径运动。当NPC和障碍物之间的距离是临界值d时，改进好的A*算法应用于正规寻路。分段搜索法将会大大缩短搜索时间，并不会因为距离的增加而增加搜索时间。

图1：段路径搜索示意图

改进算法的步骤：1）让非玩家角色的调节点S作为起始节点，调节玩家角色的

G点作为目标节点；2）计算d= | G-S |；3）如果d＜D（人为设定的临界值），NPC 被激活，否则，返回到1）；4）按直线进行路径搜索，玩家角色行动沿着射线方向；5）如果在路径遇到障碍物Q，计算| Q-S |；○1如果| Q-S |＜k（人为设定的临界值）即为改进的A*算法；○2否则，返回5）；6）返回到4）。重复操作。

3.实验结果和分析

碰撞检测算法：在这一过程中的作用，行动对碰撞作出反应是虚拟角色沿着该物体的边缘避免碰撞障碍物。在这个过程中要注意的是D是0. 本实验采用AABB包围盒的碰撞检测算法及改进算法。比较存储的调用时间和2种算法的游戏编译频率的实验数据，其中100组实验数据进行规定和10组随机选择平均值进行了比较。实验结果的比较如图2和图3所示。

图2 算法访问量的实验结果

图3 FPS的算法实验结果