作者ttshaw (InLivingEveryday)
看板GameDesign
标题Re: [程式] 关於射击游戏子弹与怪物碰撞的运算量
时间Fri Mar 19 15:30:41 2010
※ 引述《yan04870449 (杨伯)》之铭言：
: 假如我现在有一个list里面有目前所有有效子弹的物件，另一个
: list里面装有目前场景上有效的怪物，那我在检查子弹跟怪物碰
: 撞的时候就要算 bullet list size * enemy list size 如果场
: 景上有60只怪100个子弹，那就要跑6000次，感觉很没有效率，不
: 知道板上有没有前辈可以提供这类演算法的手法供小弟学习。
你可以参考这本书:
Realtime Collision Detection by Christer Ericson
里面有一个章节在介绍空间分割, 目的就是减少碰撞的计算量
物理引擎通常会使用AABB来作第一次碰撞, 叫做broad phase
常用的方法有:
1. dynamic AABB tree
2. sort and sweep methods (sweep and prune),
通常称作SAP, 原理是bubble sort
再来才作narrow phase, 就是细部的碰撞计算, 计算碰撞点/碰撞方向等
实作可以参考bullet physics engine, open source.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.128.139.157
1F：推 Eric0605:那本书的确是做碰撞侦测的圣经本 03/20 22:36