如何從在C給定位置++

我有對象的集合與位置（X，Y）
這些對象隨機移動
可能有成千上萬的得到它的距離內對象的列表

在任何時刻我將不得不對象從一個位置POS（恆定）半徑RAD名單。如何從在C給定位置++

編輯 - 上下文：這是一個遊戲服務器，它將（虛構）擁有數千名玩家。當玩家移動/ [製作動作]時，我想將更新發送給半徑內的其他玩家。

最簡單的方式，每次我需要的資源列表：

near_objects; 
foreach(objects o) { 
    if(o.distance(POS) < RAD) 
     near_objects.add(o) 
}

我想有更好/更快的方法，但我不知道要搜索什麼。

來源

2013-07-01 Malandrain

不同方法的效率取決於您擁有多少個對象，以及他們移動的頻率與其中有多少位於範圍內（平均）。例如，如果他們不經常移動，你可以在每次移動後檢查，如果他們在範圍內 – aryjczyk

這是一個遊戲服務器，這將（虛構）有數以千計的球員。當玩家移動/ [製作動作]時，我想將更新發送給半徑中的其他玩家。 – Malandrain

我會將此信息添加到您的問題中，這會產生很大的差異 – aryjczyk

您可以將您的對象放入一個有序的數據結構中，並根據它們與POS的距離進行索引。這與優先級隊列類似，但您不希望始終推送/彈出項目。

無論何時移動到新位置，您都必須更新對象的鍵。要遍歷給定半徑RAD內的項目，只要距離（鍵）小於RAD，就可以迭代此有序數據結構的項目。

來源

2013-07-01 12:16:16 arne

這裏有兩個建議。

通常你計算使用SQRT距離（（AX-BX）^ 2 +（AY-通過）^ 2）和昂貴的部分被計算SQRT（）時，如果計算RAD^2一次循環外，並比較它到sqrt（）的內部，你可以避免在循環中計算sqrt（）。

如果大部分物體的距離很遠，您可以通過使用

if(abs(a.x-b.x) > RAD) continue; 
if(abs(a.y-b.y) > RAD) continue;

來源

2013-07-01 12:22:27

消除這些我認爲這是某種MMO的 - 無法想象的選手「千人」在任何其他情況。所以你的問題實際上更加複雜 - 你需要確定哪些玩家應該接收關於每個玩家的更新，所以它變成O（n^2）問題，我們正在處理數百萬個問題。首先要考慮的是你真的想發送僅基於距離的更新嗎？你可以將你的世界劃分爲區域，併爲每個區域保留單獨的隊員名單，並且只對這些列表進行檢查，因此對於m個區域，我們有O（m *（n/m）^ 2）= O（n^2/m ）。很明顯，你也希望將更新發送給同一方的玩家，並允許區域轉場點附近的玩家彼此瞭解（但要確保保持該區域小而不吸引玩家，這樣他們不會站在那裏）。同時考慮到巨大的世界和相對較慢的玩家速度，你不必經常更新那些信息。另外請記住，內存/緩存的使用對性能來說非常重要，我將列表稱爲抽象術語 - 您應該在數組中緊密地循環訪問數據，但要確保元素不會太大。在這種情況下，考慮製作一個簡單的類，其中包含用於這些密集循環的基本玩家數據，並保持指向包含其他數據的更大類的指針

並且總的說明 - 您的問題似乎很基本，但您正在嘗試構建一個MMO，這不僅在技術上很複雜，而且還需要大量工作。我相信，追求一個規模較小，不那麼雄心勃勃的項目，你實際上能夠完成將會更有益。

來源

2013-07-01 13:23:19 aryjczyk

感謝您的回覆。我的問題只是關於搜索附近物體的算法。我知道還有很多其他方面。（這就是爲什麼我沒有在第一次放置上下文的原因）。 – Malandrain

但沒有上下文arnes響應是正確的 - 與它它沒有任何意義，因爲可怕的數據重複。我也沒有寫任何低級別的優化，因爲它們遠沒有正確的設計重要，現在你不應該考慮它們。編寫一個適用於50人的服務器，當你將這個數字轉到gt時，服務器將開始出汗，然後優化內部循環。或者不要因爲你的程序的其他部分對perf來說更重要 – aryjczyk

如何從在C給定位置++

回答

相關問題