游戏的空间数据结构

Question

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

到目前为止,我正在开发一个Quad Tree来减少搜索空间,但因为它是用于游戏,所有移动的对象都需要更新它在树中的位置.回到原点.

是否有任何数据结构或方法可以提供帮助？它需要处理大约10,000个物体,因此蛮力不够好.

Answer 1

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

从逻辑上讲，这个测试将空间划分为规则的网格。每个网格单元都标有与该单元相交的对象列表。通过扫描所有对象来初始化网格。我不懂 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