尝试在游戏中使用四叉树进行碰撞检测
Trying to use quadtrees for collision detection in a game
我目前正在使用四叉树实现碰撞检测系统。我能够实现四叉树，但我对特定情况有疑问。
可以说我最初的四叉树的边界是 200x200。所以我的第一级子四叉树的边界是：
西北: (0, 0) ~ (100,100)
SW: (0, 100) ~ (100, 200)
NE: (100, 0) ~ (200, 100)
SE: (100, 100) ~ (200, 200)
假设在(98, 98)处有一个正方形的对象，它的宽和高都是5，我在插入子树的时候取了中心的位置，所以这个对象会放在NW四叉树。然而，由于它的宽度和高度是 5，它们在技术上也在所有其他 3 个四叉树上。我是否必须检查对象的边界是否跨越四叉树的另一侧，如果是，则将多个实例添加到四叉树中？
是 - 或者，在插入时，在这种情况下将您的正方形分成 4 个独立的正方形。更简单的方法是允许重复项存储在叶子上，并使其便宜（pointer/index 到正方形，例如）
您还可以创建一棵 loose-fitting 树，您只需选择一个 children 来插入这个正方形，但扩展其边界框以适合。在那些情况下，你有重叠的分区并且必须递归地下降到树下进行搜索，所以它有其优点和缺点。
您可以做的另一件事是允许元素存储在树枝中，而不仅仅是树叶。在那种情况下，如果一个元素想要进入多个 children，只需将它存储在分支而不是进一步下降。为此，您必须在遍历期间检查每个分支的元素，而不仅仅是叶子。
我建议从重复开始。其他方法可能是一个真正的麻烦，并且不需要为这样的麻烦而烦恼（直到你衡量需要它）。
这些在任何分支的死点中心都有一个区域的元素可能想让你的树变得非常深和不平衡，所以你通常需要一个健康的停止间隙来防止它永远重复出现。这通常不是什么大问题，除非你有大量这样的元素。
此外，对于 2D 情况，您有时可以使用固定网格。实际上，有时只使用 NxM 网格比使用 quad-tree 效果更好，因为它构建起来非常简单（这使得它更容易快速更新非常动态的内容，例如，精灵每次都在屏幕上移动框架），并且没有棘手的 worst-case 场景，因为它没有 "depth" 这个概念，只有包含元素的单元格。
我目前正在使用四叉树实现碰撞检测系统。我能够实现四叉树，但我对特定情况有疑问。 可以说我最初的四叉树的边界是 200x200。所以我的第一级子四叉树的边界是：
西北: (0, 0) ~ (100,100)
SW: (0, 100) ~ (100, 200)
NE: (100, 0) ~ (200, 100)
SE: (100, 100) ~ (200, 200)
假设在(98, 98)处有一个正方形的对象，它的宽和高都是5，我在插入子树的时候取了中心的位置，所以这个对象会放在NW四叉树。然而，由于它的宽度和高度是 5，它们在技术上也在所有其他 3 个四叉树上。我是否必须检查对象的边界是否跨越四叉树的另一侧，如果是，则将多个实例添加到四叉树中？
是 - 或者，在插入时，在这种情况下将您的正方形分成 4 个独立的正方形。更简单的方法是允许重复项存储在叶子上，并使其便宜（pointer/index 到正方形，例如）
您还可以创建一棵 loose-fitting 树，您只需选择一个 children 来插入这个正方形，但扩展其边界框以适合。在那些情况下，你有重叠的分区并且必须递归地下降到树下进行搜索，所以它有其优点和缺点。
您可以做的另一件事是允许元素存储在树枝中，而不仅仅是树叶。在那种情况下，如果一个元素想要进入多个 children，只需将它存储在分支而不是进一步下降。为此，您必须在遍历期间检查每个分支的元素，而不仅仅是叶子。
我建议从重复开始。其他方法可能是一个真正的麻烦，并且不需要为这样的麻烦而烦恼（直到你衡量需要它）。
这些在任何分支的死点中心都有一个区域的元素可能想让你的树变得非常深和不平衡，所以你通常需要一个健康的停止间隙来防止它永远重复出现。这通常不是什么大问题，除非你有大量这样的元素。
此外，对于 2D 情况，您有时可以使用固定网格。实际上，有时只使用 NxM 网格比使用 quad-tree 效果更好，因为它构建起来非常简单（这使得它更容易快速更新非常动态的内容，例如，精灵每次都在屏幕上移动框架），并且没有棘手的 worst-case 场景，因为它没有 "depth" 这个概念，只有包含元素的单元格。