處理碰撞 - 陣列查找昂貴

我在我的android程序中有一個碰撞檢測方法，用於檢測兩個球碰撞並計算其新速度。每個球存儲在一個陣列Ball[] ballArray。爲了處理碰撞，我遍歷每個球，取其中心座標並計算周圍區域。如果任何其他球的中心位於該區域內，則我檢查兩個球是否有碰撞。處理碰撞 - 陣列查找昂貴

我的方法基本如下

public void handleCollisions(){ 
    int size = ballArray.length; 

    for(int i = 0; i < size; i++){ 
     Ball ball = ballArray[i]; 
     int centerX = ball.centerX; 
     int centerY = ball.centerY; 
     int radius = ball.radius; 

     //calculate box around ball 
     int lowXLimit = (centerX - radius - largestPossibleRadius); 
     int highXLimit = (centerX + radius + largestPossibleRadius); 
     int lowYLimit = (centerY- radius - largestPossibleRadius); 
     int highYLimit = (centerY+ radius + largestPossibleRadius); 

     for(int j = j+1; j < size; j++){ 
      Ball ball2 = ballArray[j]; 
      int centerX2 = ball.centerX; 
      int centerY2 = ball.centerY; 
      int radius2 = ball.radius; 

      //if ball2 is inside the possible collision region around ball1 
      if (centerX2 > lowXLimit && centerX2 < highXLimit && centerY2 > lowYLimit && centerY2 < highYLimit) { 
       //do calculations to determine new velocities 
      } 
}

我是從我的代碼獲得性能相當差，跑一traceview。令我驚訝的是，這種方法中只有大約5％的執行時間用於衝突解決計算（相當多的浮點除法，乘法）。事實上，在這種方法中，大約60-70％的時間只是從球陣列中獲取球（線Ball ball = ballArray[i]和Ball ball2 = ballArray[j]）。

我試過使用ArrayList，但那更糟。有什麼我可以做的，以加快這個代碼？也許另一個數據結構？對我來說，這似乎是一段很長的時間。我應該嘗試減少Ball中的成員變量的數量嗎？

來源

2012-03-12 Alan Carson

我想知道在循環外部聲明ball和ball2是否更有效率，並且只在每次迭代時重新影響 – njzk2 2012-03-12 17:31:45

，我認爲鏈表可能會更有效地循環遍歷元素 – njzk2 2012-03-12 17:37:34

'ball'和'ball2'只是對現有對象的引用 - 不是一個緩慢的操作（'new'）。在循環外部聲明它們並更新循環內部引用的區別應該接近於零。但嘗試一下 - 這是一個有趣的問題。 – zapl 2012-03-12 17:39:28

還有一些要點，可以進行優化：

你可以計算出球的碰撞與剛剛半徑。球之間的距離= sqrt（（x1-x2）^ 2 +（y1-y2）^ 2），現在如果球之間的距離<（半徑1 +半徑2）則它們碰撞。

爲了有效計算，您應該保持距離平方（無sqrt）並與（radius1 + radius2）^ 2比較。這種方式可能比你目前的做法更快。

如果你有n球，你現在必須做的n^2比較，這對許多球很多。所以這將是一個很好的觀點優化：

有真正先進的「空間數據結構」（谷歌），可以讓你比較球與少於所有的球（只是與球足夠接近，所以它可能他們碰撞）。與這些問題有關的是，你必須保持這種結構（每當你的球移動時更新它），這通常是相當多的計算，最終可能會慢於你的方法。

示例：http://www.gamerendering.com/2008/11/17/uniform-grid/ 您採用格網格=球的最大直徑。每當你移動一個球，你就更新它在網格中的位置（這是一個非常簡單的網格劃分）。那麼你只需要比較這個球內或直接相鄰的細胞球。

我試過使用ArrayList，但那更糟糕。有什麼我可以做的，以加快這個代碼？也許另一個數據結構？對我來說，這似乎是一段很長的時間。我應該嘗試減少Ball中成員變量的數量嗎？

幾乎沒有什麼可以通過使用不同的類/成員來做。你的Ball []數組與公共成員是最有效的方法。Ball的成員數量對速度沒有影響。

來源

2012-03-12 17:18:50 zapl

我喜歡統一網格的想法。儘管我仍然需要訪問數組中的每個球來確定它在哪個單元格中？這似乎是昂貴的。儘管如此，它會減少計算量。或者，我可以爲每個單元格分配一個ArrayList ，並希望垃圾收集不會太糟糕。我想我會試試這些，謝謝 – 2012-03-12 17:35:15

如果你把它設置爲一個'LinkedList [cellX] [cellY]'索引一個單元格中的所有Ball，那麼你可以在沒有太多GC的情況下添加/刪除它們。但它可能仍然很慢 – zapl 2012-03-12 17:44:28

如果我有固定數量的球。我只是在想，如果我爲網格的每個單元都有另外一個結構會怎樣。它可以包含單元格中球的索引。例如，它可以存儲1,4,7 - 意思是ballArray [1]，ballArray [4]等在單元格中。有沒有一種方法可以維護這些列表而不會留下那些必須由gc清理的內存？ – 2012-03-12 17:45:00

嘗試按位置排序球。這可能會減少您需要執行的計算次數，因爲您只需將每個球與附近的其他球進行比較 - 一旦球距離太遠（在您排序的軸上，至少），那麼你不需要考慮更遠的球。

來源

2012-03-12 17:06:49

只是一個短期的觀點： - 在你的第二個循環中，您可以開始從i + 1（我相信這是你的意圖）

for(int j = i+1; j < size; j++){

如果你真的要搜索的數據結構，那麼你可以看看空間分區樹。（例如，kd-trees,Quad-trees等等。從你的代碼我假設一個2D空間）。但是，您應該知道，在動態環境（移動球）中維護這些數據結構可能太昂貴了。您應該決定爲您帶來最佳回報的細節水平。

來源

2012-03-12 17:26:27 PhyBandit

你經常打電話給handleCollisions（）？這些球移動有多快？

我的猜測是你必須在這兩個數字之間進行更好的匹配，並用距離進行比賽。例如，如果一個球離最近的球有20個單位，並且自上次呼叫處理碰撞（）以來所有的球都移動了2個單位，那麼這個球就不可能碰撞，所以請跳過它。在某些情況下，也許您可以跳過所有球（跳過處理碰撞事件的呼叫）。

來源

2012-03-12 17:34:47

有趣的想法。我目前每幀調用handleCollisions（）。球的速度是可變的，但範圍在0-5像素/幀之間。我想我可以用一些代碼來確定附近是否沒有球，並在下一次迭代中跳過它。謝謝！ – 2012-03-12 17:51:02

你是否也考慮過不打擾將當前球分配給變量？您可能看到「訪問數組」的時間實際上是花在分配和分配局部變量上。您可以通過索引數組來簡單地訪問球。我不確定它會有多大的差異，但值得一試。

來源

2012-03-12 18:31:23 Matt

處理碰撞 - 陣列查找昂貴

回答

相關問題