algorithm - 炮弹与墙壁和目标的碰撞检测

Question

我正在寻找一种好的算法来检测移动的球是接触静态墙还是静态目标。经典的射击游戏逻辑。除了将它们全部循环之外，有人见过好的算法吗？

编辑:我不知道哪个是最好的解决方案，BSP 树或基于网格的计算，但我的实现将基于 JavaScript 并控制 Canvas 中的移动对象，如果炮弹撞到什么东西就会被摧毁，所以我认为每个发射的炮弹都需要一棵 BSP 树。

Answer 1

由于您已经知道静态对象的位置，因此可以将其位置编码为 BSP或 kd-tree .然后，随着球的位置移动，您可以跟踪对象在 BSP 或 kd 树中的位置，并且只与树的相同节点内的对象进行比较。

总体思路是在开始进行测试之前构建一个二叉树。这种数据结构使得定位“附近”物体变得更加容易——因为您减少了测试碰撞的物体数量，所以整体上加快了检测速度。