炮弹与墙壁和目标的碰撞检测
我正在寻找一种好的算法来检测移动的球是否接触静态墙壁或静态目标。经典的射击游戏逻辑。除了循环它们之外，有人见过更好的算法吗？
编辑：我不知道哪个是最好的解决方案，BSP树或基于网格的计算，但我的实现将在JavaScript上并控制画布中的移动对象，并且如果炮弹击中某些东西，炮弹就会被摧毁，所以我认为每个发射炮弹需要一棵 BSP 树。
I am seeking a good algorithm detecting if a moving ball is touching either a static wall or a static target. A classic Firing game logic. Anyone seen a good algorithm other than just loop them all?
EDIT: I have no idea which is the best solution, BSP tree or grid based calculation, but my implementation will be on JavaScript and controlling moving objects in canvas, and the cannon ball will be destroyed if it hits something, so I think each fired cannon ball needs one BSP tree.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
由于您已经知道静态对象的位置，因此可以将其位置编码为 BSP 或kd-tree。然后，当球的位置移动时，您可以跟踪 BSP 或 kd 树中对象的位置，并且仅与树的相同节点内的对象进行比较。
总体思路是在开始进行测试之前构建一个二叉树。这种数据结构使得定位“附近”物体变得更加容易——因为您减少了测试碰撞的物体数量，所以整体上加快了检测速度。
Since you already know the location of the static object, you can encode its location into a BSP or kd-tree. Then, as the location of the ball moves, you track the object's location in the BSP or kd-tree and only compare against objects within the same nodes of the tree.
The overall idea is to build up a binary tree before you start doing your tests. This data structure makes it much easier to locate 'nearby' objects -- since you are cutting down the number of objects you test for collision, you speed up the detection overall.
我同意 wickedchicken 的想法是最好的。我只是建议另一种方法。
当我（几年前）编写类似的游戏时，我所做的是将游戏区域划分为 N*N 网格。现在，为了检查是否发生碰撞，我只检查了与球位于同一网格正方形中或与该正方形相邻的 8 个正方形中的任何一个中的对象。仔细选择 N 的值可以使这个过程变得相当快。
当然，只有当所有对象或多或少均匀地分布在游戏区域上时，这才会产生良好的结果。但当时对我来说，这种方法看起来比编写更复杂的数据结构更容易（我还在读高中，刚刚学习编程）。
I agree that wickedchicken's idea is the best. I'm just suggesting another approach all the same.
What I did when I was coding a similar game (years ago) was to partition the playing area into a N*N grid. Now, to check whether a collision occurs, I just checked with only those objects that were in the same grid square as the ball or in any of the 8 squares adjacent to that square. Carefully choosing the value of N can make this pretty fast.
Of course, this only gives good results if all the objects are distributed more or less evenly across the playing area. But at the time this approach looked easier to me than coding a more complex data structure (I was still in high school and just learning programming).
由于墙/目标没有移动，因此您不会比较球之间的碰撞情况（对吗？），而且您必须每帧循环遍历每个球才能移动它，您最好只检查每个球的碰撞情况每一帧（如果碰撞很复杂，可以按近似距离进行过滤）。
这比保留 BSP 树运行得更快并且更容易编写。
Since the wall/target are not moving, you are not comparing the balls for collisions with each other (right?), and you must loop through every ball every frame anyways to move it, you would be best to just check every ball for collision every frame (if the collision is complex, you can filter by approximate distance).
This will run faster and be easier to write than keeping a BSP tree.