游戏的空间数据结构

Question

我需要实现一个空间数据结构来存储矩形，然后能够找到与给定矩形相交的所有矩形。这将在 JavaScript 中实现。

到目前为止，我正在开发一个四叉树来减少搜索空间，但因为它是用于游戏的，所以所有移动的对象都需要更新其在树中的位置。回到第一点。

有什么数据结构或方法可以提供帮助吗？它需要处理大约 10,000 个对象，因此暴力是不够的。

Answer 1

哈希表作为近似交集测试效果相当好。哈希表用作更复杂算法的一部分，用于检测 中的冲突常微分方程。

从逻辑上讲，这个测试将空间划分为规则的网格。每个网格单元都标有与该单元相交的对象列表。通过扫描所有对象来初始化网格。我不懂 javascript，所以我将使用 python-ish 伪代码。

for each ob in objects:
  for each x in [floor(ob.x_min / grid_size) .. floor(ob.x_max / grid_size)]:
    for each y in [floor(ob.y_min / grid_size) .. floor(ob.y_max / grid_size)]:
      hashtable[hash(x, y)].append(ob)

要查找与给定对象的碰撞，请在哈希表中查找接近碰撞，然后对每个对象应用精确的碰撞测试。

near_collisions = []
for each x in [floor(ob.x_min / grid_size) .. floor(ob.x_max / grid_size)]:
  for each y in [floor(ob.y_min / grid_size) .. floor(ob.y_max / grid_size)]:
    near_collisions = near_collisions ++ hashtable[hash(x, y)]

remove duplicates from near_collisions

for each ob2 in near_collisions:
  if exact_collision_test(ob, ob2):
    do_something

Answer 2

即使有移动的对象，您仍然可以使用四叉树 - 只需在每次移动或每次穿过区域边界时删除并重新插入对象即可。

但是四叉树不太擅长存储矩形，我建议使用 R-tree反而。