新手问题：碰撞检测中如何遍历？

player7

就是最简单的2D矩形碰撞，精灵上限是1000多个。

原来我用的是遍历精灵链表，用1号去和所有检测，用2号去和所有检测，3号、4号、、、、等等，就是速度有点慢。

后来我想到精灵的类型其实只有几种，比如敌方、我方、第三方、等等，所以我弄了20个链表来放精灵的类型，在初始一个精灵的时候，指定它的类型（比如精灵1），同时将这个类型加入到类型链表（比如：　链表[1].append(精灵p) ) ,同时每个精灵内部保存一个要检测对方类型的数组Ｓ［］.

     这样，一个精灵Ｐ，只要取出自己保存的Ｓ数组，分别与指定的类型做检测即可．

我的问题是：　这种分类的方法，怎么避免重复检测？比如：　
精灵p1，自己类型为1，指定和[2 ，3 ] 类型作检测，
精灵p2，自己类型为2，指定和[1， 3 ] 类型作检测，

这时候，p1检测了p2, 到了p2,又要检测p1。

我想不到什么办法，所以现在暂时只能规定， 1设定了检测类型2,3，则 2,3类型就不能设定为检测1

sjinny

去找些空间分割的资料吧，比如四叉树之类的

player7

和空间分割有关系吗?

hwbnet

类型是怎么分的：敌方、我方、第三方 分为三种类型么？

smile636

先不关敌方我方，我给出一个通用的避免重复检测的算法吧，假设objectGroup[]中是一组待做碰撞检测的物体：
for(int i=0;i<GroupSize;i++)
                        {
                                if(0<objectGroup.life)
                                {
                                        for(int j=i+1;j<GroupSize;j++)
                                        {
                                                        if(true==objectGroup[j].checkCollision(objectGroup))//为真的话两物体碰撞了！
                                                        {
                                                                objectGroup.onCollision(objectGroup[j]);//碰撞的物体j处理函数
                                                                objectGroup[j].onCollision(objectGroup);//碰撞的物体i处理函数
                                                        }                                                       
                                        }
                                }       
                        }

player7

谢谢楼上的,我原来就是用的这种方法遍历,1000个精灵要遍历490000次,而这1000个精灵里有的是不需要检测的,但是也要用个 if() 来判断一下,
极端情况下,1000个精灵,只有2个要检测,这种情况也判断49万次有点浪费啊?

bracelet

使用对象的空间信息对对象进行排序存储，可以大大减少搜索范围

比如按对象的BBox的x,y,z的范围分别排3个序列，搜索的时候只要按被检对象的BBox的范围检索就行了，有序队列的搜索快多了

不过动态维持这个序列需要花点时间，场景之类不动的就不需要花时间了

BSP也基本就是这个原理

smile636

我刚才回答的是针对你帖子问的问题，所以没考虑那么多
碰撞可以采用区块划分法，而且你上面的每个物体都要一串检测标识，这样不方便，可以采取组号标识