关于障碍物碰撞判断所需要的数据结构问题！

gg0001

我做一个2D的开枪射击类游戏，把所有的子弹放在一个无序数组里，人物放在另一个数组里，碰撞检测时一个个的检测，可发现运行效率十分不好，那我应该建立怎样的数据结构，然后怎样去应用？请带上程序，先在此谢谢了！！！

夜荷

相信你的电脑对这样简单的碰撞不会浪费多少时间的。

happysnoopy

每一颗子弹遍历每一个NPC，看他们接触了吗，可以划分区域，减少检测时间

genl

你用数组的话 那射到屏幕外的子弹岂不是也得计算？？？能不慢么
如果说射到屏幕外的子弹用移动数组的办法去掉数组元素。。。那样的话慢的更彻底

不喜欢面向对象就用链表 最好是用面向对象 反正数组是不行

genl

其实 我目前这方面弄得也不好。。。
在800X600X256的情况下 Sprite（人物+子弹）个数超过630多个的时候
帧数就落到30帧以下。。。。P4 2.4G  8500啊。。。
现在想想 《彩京》确实做得很好。。。满天子弹不卡。。。。

bluespark

     利用BSP或四叉树来优化

gg0001

1：
happysnoopy所说的“每一颗子弹遍历每一个NPC，看他们接触了吗，可以划分区域，减少检测时间”，不知道怎样划分区域？
能把详细步骤介绍一下么？谢谢！
2：
还有上楼的说利用BSP或四叉树来优化，我也是不懂的，能介绍一下建立此类数据结构的依据和办法么？以及怎样遍历？谢谢！

bluespark

      BSP是把地图按照一半一半这样划分，让每个区域内只有一定数量的对象，如果超过规定的数量，就继续细分，直到满足条件为止，四叉树也是同样的道理，只是每次划分为4块而已，概念上是一样的， 同样适合于八叉树。
      如何检测，如果一个对象不和父对象碰撞，则也不会跟子对象碰撞，这就是检测的依据，可以加快碰撞检测的效率

jiangwei

我就是研究物理引擎的，欢迎访问我的BLOG

260013004

可以分为两部分检测碰撞，在该帧检测一部分的子弹和人物的碰撞，
在下一帧再检测剩下的子弹碰撞。
还有当子弹不在屏幕内就不用检测了。
如果场景是移动的，可以让子弹在一定的距离内或时间内消失。
还有也可以把人物分为一组一组的，就是在一个以某个中心，某个
半径为团体的，可以在设定的帧内改变这个团体的中心和半径，
半径也可以是固定，当一个人物超出这范围时可以把它划到另一组
或自己新键一组。