在矩形數組中找到重疊的最快方法是什麼？

Question

我在業餘時間研究「遊戲」，幾乎純粹是作爲一種學習經驗，並且正處於玩家實體與敵方實體之間需要發生碰撞檢測的地步。

玩家和所有敵人共享一個基類，Entity，這使他們能夠訪問x，y，高度和寬度屬性。使用這些，我可以爲每個實體構建一個矩形，並嘗試查找重疊。如果有重疊，則發生碰撞。

所以，與上述邏輯，我們可以假裝下列數據是在矩形數組：

X Y HEIGHT WIDTH 
------------------------ 
0 0 25  50 
0 50 25  25 
0 100 25  30 
50 200 25  50 
150 250 25  25 
150 50 25  30 

是什麼，以確定是否任何這些實體（矩形）的與相交的最快方式任何其他？簡單地遍歷數組並將每個元素與其他元素進行比較的性能不夠好（O（n^2））。有沒有更好的辦法？

Answer 1

您想要使用某種空間索引或結構，以便您快速找到彼此靠近的元素。

一個常用的數據結構是quadtree。