应该使用什么技术来修剪 2d 碰撞检查? [英] What technique should be used to prune 2d collision checks?

问题描述

从一开始，碰撞检测感觉就像是一个 O(n^2) 的问题.

From the outset, collision detection feels like it is an O(n^2) problem.

您有一堆对象，您需要检查每个对象是否与任何其他对象发生碰撞.但是，我知道根据所有其他对象检查每个对象是非常低效的.如果两个球甚至彼此不靠近，为什么要在它们之间进行相对昂贵的碰撞检查?

You have a bunch of objects and you need to check if each object is colliding with any of the other objects. However, I know that it is wildly ineffecient to check each object against all the other objects. Why do a relatively expensive collision check between two balls if they aren't even close to eachother?

这是我正在开发的简单程序的示例:

Here is example of my simple program I'm working on:

如果你有 1000 个球，那么如果你使用天真的碰撞检测，你将有 1000^2 个集合检查(一百万)！这种碰撞检查很快成为我应用程序中的瓶颈.我需要实施一些广泛的阶段修剪.

If you have 1000 balls then if you went with the naive collision detection you would have 1000^2 collection checks (a million)! This collision checking has quickly become the bottleneck in my application. I need to implement some broad phase pruning.

处理二维圆形对象时，应该使用哪些技术来修剪碰撞检查?我已经阅读了有关 QuadTrees、BSP、空间散列等的内容，但很难找出最适合此用例的方法.

What techniques should be used to prune collision checks when working with 2d - circular objects? I've read about QuadTrees, BSP, spatial hashing, etc but it is difficult to sort out what method is most appropriate to this use case.

有人知道什么最有效吗?

Does anyone have any knowledge about what might work best?

推荐答案

空间散列.参见 Hugo Elias 的页面关于它.

这篇关于应该使用什么技术来修剪 2d 碰撞检查?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！