四叉樹vs只是一個網格的碰撞檢測

Question

我正在考慮使用四叉樹進行2D矩形的碰撞檢測，但它似乎有點過於複雜，試圖找到每個矩形觸摸的每個象限，當有所有不同的大小或甚至工作每個象限應該有多少個象限。

我決定改爲在整個區域上只有一個小網格，並通過對每個四角執行row = x/cell width，column = y/cell height來查找每個對象所在的單元格，然後檢查與這些單元中的每個其他對象碰撞。我也優化了一下，以防止它重新檢查相同的對象

我用一個32x32網格和5000個移動物體對暴力方法進行了測試，它的碰撞檢查速度提高了20倍，速度提高了20倍。所以我想知道使用四叉樹會有什麼優勢，比我做的更好？它真的會更快嗎？

Answer 1

當物體的尺寸變化很大時（由於單個物體移動時需要更新許多網格單元），或者它們非常小且非常稀疏（這需要大量的網格內存大多是空單元）。這些是基於樹的分區結構（例如四叉樹）發光的情況。