快速地找到對象在JavaScript

陣列的數量，我需要檢查的對象是否是在距離它顯示到屏幕上（它的一個側滾輪視頻遊戲）快速地找到對象在JavaScript

到目前爲止，我還這個：

for (var i=0; i < Coins.length; i++) 
{ 
    var obj = Coins[i]; 


    if (worldObj.distance > obj.distance && worldObj.distance < obj.distance + canvas.height) 
    { 

     DrawCoins(obj); 
    } 
}

其中worldObj.distance是玩家已經旅行的距離，obj.distance是物體的距離。

問題：

這對於迴路使移動設備上的巨大的性能下降由於硬幣在水平（超過10,000）的量和這個被執行每秒（每秒60幀）的60倍

我該如何解決這個問題？

謝謝！ :)

編輯：試圖將canvas.height緩存到循環前的變量（例如：var height = canvas.height;）。沒有性能差異（I5 2500K上44 ms vs 44 ms，想象在手機上！）。

編輯：在循環之前嘗試緩存Coins.length（例如：var len = Coins.length;）。沒有性能差異（44毫秒vs 44毫秒）。

編輯：這是我如何創建硬幣：

for(var i=0; i<10000; i++) 
{ 

    /* Coins */ 
    for (var z=0; z < 6; z++) 
    { 
     if (RNG(0,100) < Upgrades.coinChance) // random number generator, Upgrades.coinChance = 5; -> 5% chance 
     { 
      Coins.push({ active: 1, type: "Gold", cash: 5, x: 60*(z+1), distance: i*RNG(20,100) }); 
     } 
    } 
}

來源

2014-04-19 user3552137

你怎麼畫硬幣？如果你使用的是HTML5 Canvas，你應該[讓它爲你處理剔除]（http://stackoverflow.com/questions/16893626/should-i-cull-elements-before-rendering-to-html5-canvas-或者，讓最帆布剔除）。 –

似乎最明顯的將是a）只繪製可見的硬幣或b）只有當他靠近它們時刷新硬幣。 –

簡單地緩存canvas.height到一個var之前，循環將有相當大的幫助。緩存worldObj.distance也會很好。 – dandavis

好吧。我已經完成了一些數字處理，並提出了兩種算法，並在兩者之間進行權衡。

作爲測試平臺，我運行以下初始化代碼：

var n,m; 

var Coin=function(x) 
{ 
    return {x:x,r:1}; 
} 
var coins=[]; 
var map={}; 

var viewSize=50; 
var worldSize=1000; 

n=100000; 
while(n--) 
{ 
    coins[n]=Coin(worldSize*Math.random()); 
}

正如你所看到的，有10萬個金幣在這裏。我知道，比你在答案中規定的要多，但我想強調測試。

第一種算法是您在問題中發佈的算法的某種程度優化的版本。它只是循環並測試每個硬幣的最近邊緣是否小於距離某個點x的viewSize/2距離。如果是這樣，它將它添加到數組中，最終返回。

var checkCoins1=function(list,x,w) 
{ 
    var selected,k,n,no; 
    selected=[]; 
    n=list.length; 
    while(n--) 
    { 
     no=list[n]; 
     if(Math.abs(no.x-x)<w/2+no.r) 
     { 
      selected.push(no); 
     } 
    } 
    return selected; 
};

這種方法不需要額外的時間來設置，每次執行時使用我們的100000個硬幣7毫秒。絕對是動畫循環中的一項成本，但卻是一個可管理的成本。

第二種算法利用了一張圖。它從排列硬幣列表開始，然後在worldSize之間選擇一組點，每個viewSize與最後一個分開。它用這些點作爲關鍵點創建一個對象。然後它循環遍歷所有的硬幣並保存距離物體中每個點最近的索引。這需要一些時間，但只需要做一次。當實際的循環運行時，它只是在視圖的左邊（或更低的視情況）邊緣之前找到地圖中的點。然後它通過列表中的所有硬幣向前循環，並將它們保存到數組中，直到它到達比觀察窗的右邊（或上邊）更遠的硬幣。然後停止並返回數組。這樣，它不必檢查列表中的每一枚硬幣，而只需檢查其中的幾枚硬幣。

設置代碼如下所示：

coins.sort(
    function(a,b) 
    { 
     return -(a.x<b.x)+(a.x>b.x); 
    } 
); 
n=Math.floor(worldSize/viewSize); 
while(n--) 
{ 
    map[n*viewSize]=undefined; 
} 
n=coins.length; 
while(n--) 
{ 
    for(m in map) 
    { 
     if(map[m]===undefined || Math.abs(coins[n].x-m)<Math.abs(coins[map[m]].x-m)) 
     { 
      map[m]=n; 
     } 
    } 
}

和主循環如下所示：

var checkCoins2=function(list,map,x,w) 
{ 
    var selected,y,k,n,no; 
    selected=[]; 
    y=x-w/2; 
    n=map[Math.floor(y/w)*w]; 
    while(1) 
    { 
     no=list[n++]; 
     if(Math.abs(no.x-x)<w/2+no.r) 
     { 
      selected.push(no); 
     } 
     else if(no.x>x) 
     { 
      break; 
     } 
    } 
    return selected; 
};

初始化需要高達900毫秒，但循環只需要1毫秒它每次運行時。隨着worldSize和viewSize之間的比率增加，環路將變得越來越快。總的來說，我會說第一個算法比較簡單，但是如果你發現自己在動畫循環中按下了一段時間，並且在遊戲（或關卡）加載時可能需要一秒鐘才能初始化，那麼你應該使用第二種算法算法。也許，如果你知道硬幣開始的位置，你甚至可以在編寫代碼時預先對列表進行排序並預先構建地圖。那麼你根本不需要客戶端來完成初始化。

如果您有任何疑問，請詢問！

來源

2014-04-19 20:53:05 mindoftea

快速地找到對象在JavaScript

回答

相關問題