遊戲的空間數據結構

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來代替。