游戏的空间数据结构

Question

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

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

是否有任何数据结构或方法来帮助？它需要处理大约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 

Answer 2

即使您有移动物体，您仍然可以使用四叉树 - 每次移动物体或每次移动物体时都要移除并重新插入物体。

但四叉树是不是在存储矩形非常好，我会建议使用R-tree来代替。