问题标签 [quadtree]

在我的 2D 游戏中，我有静态和动态对象。可以有多个摄像头。我的问题：确定与当前相机的视图矩形相交的对象。

目前，我只是遍历所有现有对象（不关心动态或静态）并使用相机视图对它们进行 AABB 检查。这对于非常动态的对象似乎是可以接受的，但对于静态对象则不然，因为静态对象可能有成千上万个（静态关卡几何体散布在整个场景中）。

我研究了多种可以解决我的问题的数据结构：

• 四叉树

这是我考虑的第一件事，但问题是它会迫使我的场景具有固定大小。（静态对象可以接受，动态对象不行）

• 动态 AABB 树

看起来不错，但是对于许多动态对象来说，重新平衡它的开销似乎太大了。

• 空间哈希

对我来说，这里的主要问题是，如果你用相机缩小很多，必须查询大量几乎不存在的空间哈希桶，导致性能低下。

一般来说，我对这个问题的良好解决方案的标准是：

• 动态大小：该解决方案不得导致场景大小受到限制，或需要大量重新计算以调整大小

• 良好的查询性能（针对相机）

• 对动态对象的良好支持：处理位置不断变化的对象所需的计算应该很好：

在我的游戏中，动态对象的最大合理数量可能是 5000。考虑到它们每帧都会改变它们的位置。考虑到频繁的插入和删除，是否有比每帧将对象的 AABB 与相机进行比较更快的数据结构？

我正在尝试使用和理解D3 可视化库(http://mbostock.github.com/d3/)，我正在查看他们的力导向代码，似乎他们正在使用四叉树来计算粒子上的力. 代码是

其中 quad.count 似乎是四叉树节点中的粒子数。但是在https://github.com/mbostock/d3/blob/master/d3.geom.js#L696中查看他们的四叉树代码，我找不到对 的任何引用，以及它是如何计算的。我问是因为我想修改一些东西来改变每个节点的“重量”或“费用”。count

我正在为四叉树编写删除方法。

现在，当您删除节点中的项目时，您将需要检查其兄弟节点以查看是否需要折叠节点并将它们合并为一个。

为了检查兄弟姐妹，我应该存储一个指向父节点的指针，还是有办法以递归方式更好地做到这一点？

谢谢

我有一组[(x1,y1),(x2,y2), ..., (xn,yn)]按莫顿排序的点。我希望从这些点构建一个基于指针的压缩四叉树。阅读 Eppstein et al 和 Aluru 我的印象是这应该是一个相对简单的任务。

不幸的是，这两篇文章中的解释都缺乏伪代码，而且有些难以理解。因此，我想知道是否有人可以提供高级伪代码来描述构建树所需的具体操作。

我正在尝试在我正在制作的游戏中使用四叉树进行碰撞检测，但我不确定如何处理可能在不同四边形之间移动的对象？

我能想到的唯一方法是每帧清除整个树，然后将所有内容添加回那里，但这似乎会使 CPU 密集且效率不高。您是否每帧检查每个对象以查看它是否已移出当前四边形的边界，如果是，则将其删除并读取？这似乎又是非常低效的，因为您每帧都要对每个移动对象执行碰撞检查。

此外，关于四叉树，但与在其中移动的对象无关，您如何处理同一个四边形中的多个对象？我读过的大多数关于它们的网站都说你应该只在一个四边形中拥有一个，也许两个对象，如果你得到更多，然后将它们推到树中。如果你有这样的情况怎么办？你有三个圆圈，它们都在它们下一层的边缘，所以它们不能再往下走，但是有三个都在同一层，人们说你不应该有。

有哪些好的数据结构可以在二维空间模拟中跟踪代理？

我看过一些对四叉树（我理解）和 kd-trees（我不太理解）的引用。

我正在寻找一个代理可以有效地说“我知道我的位置，并且我想知道哪些代理在我附近（在我自己的某个半径内）”的东西。

示例（伪代码很好）将不胜感激。

我在 Java 中工作。

我正在制作四叉树，需要帮助将对象插入其中。我理解这样做的概念，但我不擅长递归和 Java 传递变量的方式。

我有一个 Quadtree 类，其中包含一个名为 root 的节点。Node 类内部有四个 Node，它们是组成它的四个四边形。创建四叉树时会创建根节点，并且在调用 createChildrenQuads() 之前不会创建每个节点内的四个节点。但是，对于根节点，在创建四叉树时会调用该方法。

所以我关于如何将项目插入节点的思考过程是这样的：

1. 从根节点开始
2. 对于每个节点：
   1. 检查并查看当前项目适合当前节点的哪个子节点
   2. 如果它适合其中一个，则将其插入该节点（调用递归方法并重新开始）
   3. 如果它不适合任何东西，请将其添加到当前节点的对象列表中并完成

基于此，我创建了这个：

我认为在四叉树方面，我的逻辑很好。当我调试代码时，看起来一切正常。但是，我相信我的问题是 Java 通过值而不是引用传递参数，所以当我将它添加到正确的位置时，它并没有得到“保存”，因为它只是一个局部变量。我相信这是问题所在，但我可能是错的。

所以我尝试对其进行一些更改以使其插入方法返回当前节点，以便所有内容都应该正确“保存”。这就是我想出的：

但是，我仍然有同样的问题。现在我不确定我的问题是什么。

我正在将它用于游戏，并且我拥有它以便它在所有四边形所在的位置绘制轮廓，并且我可以单击以将实体添加到四叉树中。我的代码的两个版本似乎都是一样的。发生的情况是，当我将实体添加到四叉树时，它会被添加并保留在那里，所以我猜我关于它没有得到“保存”的理论是因为 Java 传递引用的方式是错误的。

但是，我的代码应该（至少在我的脑海中应该）将每个实体放入四叉树中尽可能低的级别，在每个节点沿着树向下时在每个节点中创建新的子四边形。但实际发生的情况是，有时它似乎只是将新实体添加到当前四边形中，根本不下树，或者它下降一两个级别，就是这样，当它很容易下降几个更多级别。

任何人都可以看到代码或我的逻辑有什么问题吗？

因此，从理论的角度来看，我需要一些头脑风暴的帮助。现在我有一些只绘制一些对象的代码。对象位于四叉树的叶子中。现在，随着对象的移动，我想将它们放置在四叉树的正确叶子中。

现在我只是在改变它们的位置后重建对象的四叉树。我试图找出一种方法来纠正树而不完全重建它。我能想到的就是有一堆指向相邻叶节点的指针。

有没有人知道如何找出对象移动到的节点，而不仅仅是到处都有大量的指针或指向文章的链接？我所能找到的只是构建四叉树的不同方法，而不是更新它。

我正在创建一个类似于 Minecraft 的地形引擎，我想知道八叉树到底是什么。使用我的引擎，我将它的每个部分分成块或区域 - 从我所读到的内容中，这与它有关。另外，我想知道指数是否确实会提高游戏中的性能，如果可以，会提高多少？任何其他提高性能的想法/方法将不胜感激。请注意，我已经包含了背面剔除，如果盒子或一侧被隐藏，则不要显示该侧。

我正在寻找用于根据人口密度构建 QuadTree 的 java 代码。另外，我在我的代码中使用谷歌地图，所以如果有人知道如何实现它，那将非常有帮助！谢谢