精华游戏算法之七

　　Another hidden problem is the collide_with_other_objects() routine, which checks whether an object intersects any other object in the scene. If we have a lot of objects in the scene, this routine can get very costly. If we have to check each object against all other objects in the scene, we’ll have to make roughly 图三 (N choose 2 )的比较。因此，我们将要完成的工作就是比较数字的关系N2 (or O(N2))。但是我们能避免施行 O ( N2 )在若干方法之一的对明智的比较。例如,我们能把我们的世界划分成是静止的物体( collidees )并且移动的物体( colliders )的初速度 v=0 。例如，在一个房间里的一面僵硬的墙是一碰撞面和向墙被扔的一个网球球是一碰撞对象。我们能建立一个二叉树(为每个组的一个)给这些对象，并且然后检查哪个对象确实有碰撞的机会。我们能甚至进一步限制我们的环境以便一些碰撞对象不会与我们没有在 2 颗子弹之间计算碰撞的对方发生抵触，例程。当我们继续前进，这个过程将变得更清楚，为现在，让我们就说它是可能的。（为了减少场景方面数量的另外的方法就是建立一个八叉树，这已经超出这篇文章的范围，但是你可以在文末参看我给你列出的参考文献）现在让看看基于portal-based引擎的碰撞检测。 (N choose 2) comparisons. Thus, the number of comparisons that we’ll need to perform is of order N2 (or O(N2)). But we can avoid performing O(N2) pair-wise comparisons in one of several ways. For instance, we can divide our world into objects that are stationary (collidees) and objects that move (colliders) even with a v=0. For example, a rigid wall in a room is a collidee and a tennis ball thrown at the wall is a collider. We can build two spatial trees (one for each group) out of these objects, and then check which objects really have a chance of colliding. We can even restrict our environment further so that some colliders won’t collide with each other — we don’t have to compute collisions between two bullets, for example. This procedure will become more clear as we move on, for now, let’s just say that it’s possible. (Another method for reducing the number of pair-wise comparisons in a scene is to build an octree. This is beyond the scope of this article, but you can read more about octrees in Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods, mentioned in the “For Further Info” section at the end of this article.) Now lets take a look at portal-based engines and see why they can be a pain in the neck when it comes to collision detection. IMG upload/forum/200562134942.gif[/IMG] ---------------------------------------------------------------------------- 关于SLG中人物可到达范围计算的想法 下面的没有经过实践，因此很可能是错误的，觉得有用的初学朋友读一读吧：）希望高人指点一二简介：在标准的SLG游戏中，当在一个人物处按下鼠标时，会以人物为中心，向四周生成一个菱形的可移动区范围，如下： 0 000 00s00 000 0 这个图形在刚开始学习PASCAL时就应该写过一个画图的程序（是否有人怀念？）。那个图形和SLG的扩展路径一样。一、如何生成路径：从人物所在的位置开始，向四周的四个方向扩展，之后的点再进行扩展。即从人物所在的位置从近到远进行扩展（类似广宽优先）。二、扩展时会遇到的问题： 1、当扩展到一个点时，人物的移动力没有了。 2、当扩展的时候遇到了一个障碍点。 3、当扩展的时候这个结点出了地图。 4、扩展的时候遇到了一个人物正好站在这个点（与2同？）。 5、扩展的点已经被扩展过了。当扩展节点的时候，每个节点都是向四周扩展，因此会产生重复的节点。当遇到这些问题的时候，我们就不对这些节点处理了。在程序中使用ALLPATH[]数组记录下每一个等扩展的节点，不处理这些问题节点的意思就是不把它们加入到ALLPATH[]数组中。我们如何去扩展一个结点周围的四个结点，使用这个结点的坐标加上一个偏移量就可以了，方向如下： 3 0 2 1 偏移量定义如下： int offx[4] = { -1, 0, 1, 0 }; int offy[4] = { 0, 1, 0, -1 }; 扩展一个节点的相邻的四个节点的坐标为： for(int i=0; i<4; i ) { temp.x = temp1.x offx[ i ]; temp.y = temp1.y offy[ i ]; } 三、关于地图的结构： 1、地图的二维坐标，用于确定每个图块在地图中的位置。 2、SLG中还要引入一个变量decrease表示人物经过这个图块后他的移动力的减少值。例如，一个人物现在的移动力为CurMP=5，与之相领的图块的decrease=2；这时，如果人物移动到这里，那它的移动力变成CurMP-decrease。 3、Flag域：宽度优先中好像都有这个变量，有了它，每一个点保证只被扩展一次。防止一个点被扩展多次。（一个点只被扩展一次真的能得到正确的结果吗？） 4、一个地图上的图块是否可以通过，我们使用了一个Block代表。1---不可以通过；0---可以通过。这样，我们可以定义一个简单的地图结构数组了： #define MAP_MAX_WIDTH 50 #define MAP_MAX_HEIGHT 50 typedef struct tagTILE{ int x,y,decrease,flag,block; }TILE,*LPTILE; TILE pMap[MAP_MAX_WIDTH][MAP_MAX_HEIGHT]; 以上是顺序数组，是否使用动态的分配更好些？毕竟不能事先知道一个地图的宽、高。四、关于路径： SLG游戏中的扩展路径是一片区域（以人物为中心向四周扩展，当然，当人物移动时路径只有一个）。这些扩展的路径必须要存储起来，所有要有一个好的结构。我定义了一个结构，不是很好： typedef struct tagNODE{ int x,y; //扩展路径中的一个点在地图中的坐标。 int curmp; //人物到了这个点以后的当前的移动力。 }NODE,*LPNODE; 上面的结构是定义扩展路径中的一个点的结构。扩展路径是点的集合，因此用如下的数组进行定义： NODE AllPath[PATH_MAX_LENGTH]; 其中的PATH_MAX_LENGTH代表扩展路径的点的个数，我们不知道这个扩展的路径中包含多少个点，因此定义一个大一点的数字使这个数组不会产生溢出： #define PATH_MAX_LENGTH 200 上面的这个数组很有用处，以后的扩展就靠它来实现，它应该带有两个变量nodecount 代表当前的数组中有多少个点。当然，数组中的点分成两大部分，一部分是已经扩展的结点，存放在数组的前面；另一部分是等扩展的节点，放在数组的后面为什么会出现已扩展节点和待扩展节点？如下例子：当前的人物坐标为x,y；移动力为mp。将它存放到AllPath数组中，这时的起始节点为等扩展的节点。这时我们扩展它的四个方向，对于合法的节点（如没有出地图，也没有障碍......），我们将它们存放入AllPath数组中，这时的新加入的节点（起始节点的子节点）就是等扩展结点，而起始节点就成了已扩展节点了。下一次再扩展节点的时候，我们不能再扩展起始节点，因为它是已经扩展的节点了。我们只扩展那几个新加入的节点（待扩展节点），之后的情况以此类推。那么我们如何知道哪些是已经扩展的结点，哪些是等扩展的节点？我们使用另一个变量cutflag，在这个变量所代表的下标以前的结点是已扩展节点，在它及它之后是待扩展结点。五、下面是基本框架（只扩展一个人物的可达范围）： int nodecount=0; //AllPath数组中的点的个数（包含待扩展节点和已经扩展的节点 int cutflag=0; //用于划分已经扩展的节点和待扩展节点 NODE temp; //路径中的一个点（临时） temp.x=pRole[cur]->x; //假设有一个关于人物的类，代表当前的人物 temp.y=pRole[cur]->y; temp.curmp=pRole[cur]->MP; //人物的最大MP AllPath[nodecount ]=temp; //起始点入AllPath，此时的起始点为等扩展的节点 while(curflag=MAP_MAX_WIDTH|| temp.y<0||temp.y>=MAP_MAX_HEIGHT) continue; //出了地图的范围 if(pMap[temp.x][temp.y].flag) continue; //已经扩展了的结点 //经过了上面几层的检测，没有问题的节点过滤出来，可以加入AllPath AllPath[nodecount]=temp; } pMap[AllPath[ i ].x][AllPath[ i ].y].flag=1; //将已经扩展的节点标记为已扩展节点 } cutflag=n; //将已扩展节点和待扩展节点的分界线下标值移动到新的分界线 } for(int i=0;i)），从城内走到城外还有情可缘，因为有道城墙嘛，但是两个地方明明没有界限，却偏偏在这一边看不到另外一边，就有点不现实了。当然这并不是毛病，一直以来的RPG都是遵循这个原则，我们（至少是我）已经习惯了这种走路的方式。我在这里说的仅仅是另外一种看起来更自然一点的走路方式，仅此而已。当然要把整个城市的地图一下子装进内存，现在的确是不现实的，每一次只能放一部分，那么应该怎么放才是我们要讨论的问题。我们在以前提到Tile方法构造地图时就谈到过Tile的好处之一就是节省内存，这里仍然可以借鉴Tile的思想。我们把整个大地图分成几块，把每一块称作一个区域，在同一时间里，内存中只保存相邻的四块区域。这里每个区域的划分都有一定的要求：每个区域大小应该相等这是一定的了，不然判断当前屏幕在哪个区域中就成了一个非常令人挠头的事；另外每个区域的大小都要大于屏幕的大小，也只有这样才能保证屏幕（就是图中那块半透明的蓝色矩形）在地图上荡来荡去的时候，最多同时只能覆盖四个区域（象左图中所表示的），内存里也只要保存四个区域就足够了；还有一点要注意的，就是地图上的建筑物（也包括树啦，大石头啦什么的）必须在一个区域内，这样也是为了画起来方便，当然墙壁——就是那种连续的围墙可以除外，因为墙壁本来就是一段一段拼起来的。 我们在程序中可以设定4个指针来分别指向这4个区域，当每次主角移动时，就判断当前滚动的屏幕是否移出了这四个区域，如果移出了这四个区域，那么就废弃两个（或三个）已经在目前的四个相邻区域中被滚出去的区域（说得很别扭，各位见谅），读入两个（或三个）新滚进来的区域，并重新组织指针。这里并不涉及内存区域的拷贝。这样的区域划分方法刚好适合我们以前提到的Tile排列方法，只要每个区域横向Tile的个数是个偶数就行了，这样相邻的两个区域拼接起来刚好严丝合缝，而且每个区域块的结构完全一致，没有那些需要重复保存的Tile（这个我想我不需要再画图说明了，大家自己随便画个草图就看得出来了）。在文件中的保存方法就是按一个个区域分别保存，这样在读取区域数据时就可以直接作为一整块读入，也简化了程序。另外还有个细节就是，我们的整个地图可能不是一个规则的矩形，可能有些地方是无法达到的，如右图所示，背景是黑色的部分代表人物不能达到的地方。那么在整个地图中，这一部分区域（在图中蓝色的3号区域）就可以省略，表现在文件存储上就是实际上不存储这一部分区域，这样可以节省下不少存储空间。对于这种地图可以用一个稀疏矩阵来存储，大家也可以发挥自己的才智用其他对于编程来说更方便的形式来存储地图。 这就是对无限大地图实现的一种方法，欢迎大家提出更好的方法。也希望整个版面能够活跃一点。