用于2D碰撞检测的四叉树 [英] QuadTree for 2D collision detection

问题描述

我目前正在从事2D游戏的游戏，我正在使用四叉树进行碰撞检测。我写了一个正确的四叉树，正确地将我的演员进入树中他们所属的节点/树叶。但是，我有一些问题。

首先，我如何实际使用我的四叉树选择对象应该测试碰撞的哪些其他对象？我不确定这是怎么做到的。

其中提出了第二个问题。说我在节点中有一个不是另一个节点的邻居的对象，但是该对象足够大，以至于它跨越了一些节点，我如何检查实际的冲突，因为我猜测树可能认为它不是足够接近与远节点的物体相撞？如果不完全适合节点的对象将保存在父节点中？

在我的游戏中，大多数对象具有不同的大小并移动。 / p>

我已经阅读了很多关于quadtree的博客/文章，但最多只是解释如何构建一个不是我正在寻找的树。

欢迎任何帮助/信息。

解决方案

您可以建立一个约定

然后，当您检查节点A的冲突时，您可以像这样进行：

1. 当前节点=根节点


2. 检查A与当前节点中每个元素的冲突


3. 如果A可以完全包含在当前节点的任何子节点中，则将当前节点设置为该子节点并再次转到2

最后，检查A与childre中所有元素的碰撞递归地显示当前节点的n个节点。

请注意，对象越小，它们将位于四叉树中越深，因此，他们将被更少的比较。

I'm currently working on a 2D shoot them up type of game, and I'm using a quad tree for my collision detections. I wrote a working quad tree that correctly pushes my actors into the nodes/leaves they belong to in the tree. However, I've got a few problems.

Firstly, how do I actually use my quadtree to select against which other objects an object should test collisions ? I'm unsure about how this is done.

Which brings up a second question. Say I have an object in node that is not a neighbour of another node, but that the object is large enough that it spans a few node, how can I check for an actual collision, since I'm guessing the tree might consider it's not close enough to collide with objects in a "far away" node? Should objects that don't completely fit in a node be kept in the parent node?

In my game, most of the objects are of different sizes and moving around.

I've read a good number of blogs/articles about quadtrees but most just explain how to build a tree which is not really what I'm looking for.

Any help/info is welcome.

解决方案

You can establish a convention that every element is contained in the smallest quadtree node which contains it fully.

Then when you check the collisions for node A, you proceed like this:

1. current node = root node
2. check collisions of A with each element directly in current node
3. if A can be contained entirely in any of sub-nodes of the current node, set the current node to that sub-node and go to 2 again
4. finally, check collisions of A with all the elements in children nodes of the current node, recursively.

Note that the smaller the objects, the deeper they will be located in the quad tree, hence they will be compared less often.

这篇关于用于2D碰撞检测的四叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！