避免基於網格的碰撞檢測中出現重複？

我的比賽，對於有效的再現和碰撞分爲區域。每個地區都會有很多動態移動的對象。當它們移動時，我確定它們處於哪個區域。

這意味着和對象可以是在多個區域中。

如果我知道的對象一個是在區域1和2以及對象B也是在1和2，然後會發生什麼事是我會做：

for each object in region 1 and 2 
if A collides with B...

我會有效地檢查同一對兩次。

我能做的只有這些檢查一次？是否有我應該使用的數據結構或算法？

來源

2012-11-08 jmasterx

如果您可以對對象強加一個排序，那麼您只需要檢查其中的排序對a < b。可能是任何東西：數組中的索引，指針（對於允許指針值訪問的語言，yay）。

for(Object a : list) { 
    for(Object b : list) { 
     if (a.compare(b) < 0) {

很簡單，實際上會解決問題。

如果你有整數索引存儲，你可以做

for(int i = 0; i < list.length; i++) { 
    for(int j = i + 1; j < list.length; j++) {

，你不會得到重複。這將適用於ArrayList，但可能不適用於任意類型。你也許可以克隆一些迭代器，但我不會對賭...

for(Iterator<Object> iter = list.iterator(); iter.hasNext();) { 
    Object a = iter.next(); 
    Iterator<Object> iter2 = iter.clone(); 
    for(;iter2.hasNext();) { 
     Object b = iter.next();

但嚴重的是，這是一個黑客。如果它適用於所有的java集合，我會感到驚訝。一個更可靠，但正如hackish的解決方法與Java迭代器：

for(Object a : list) { 
    Iterator<Object> biter = list.iter(); 
    while(biter.next() != a) { }; 
    for(; biter.hasNext();) { 
     Object b = biter.next();

一般情況下，Java的語法的foreach是for(Clazz object : iterable) {「可愛」，但強大得多比Iterator秒。實際上，上面的循環的舊整數也像魅力一樣。

來源

2012-11-08 20:11:46

爲什麼不存儲從先前計算的結果？

實際上，它會成爲：

for each object in region 1 and 2 
    if results doesn't contain (A collides with B) 
     ... 
     results = result of (A collides with B)

來源

2012-11-08 17:59:35 Lester

號它可以是你的網格太小。另外包圍盒在碰撞檢測方面不是很好，可以避免以插入和刪除爲代價的空白區域。

來源

2012-11-08 18:40:10 Bytemain

什麼是更好的方法？ – jmasterx

邊界框更好的方法？也許最近鄰問題的掃描線算法？但它看起來像你在這裏的微觀優化。我不認爲它會支付你賬單？ – Bytemain

而不是常規的間隔格柵，你可以使用一個四叉樹（http://en.wikipedia.org/wiki/Quadtree），它更好地適合於不同大小的索引對象。不必選擇單個單元格大小（對於某些對象而言可能太大，對於其他對象而言可能太大），則可以讓四叉樹確定合適的單元格大小。

然而，即使這樣你也不能阻止在多個樹節點中出現單個對象，但這不應該成爲你應該嘗試實現的目標 - 你應該防止的唯一事情就是每個對象都發生在數十或數百個單元或四元節點，因爲確實對造成傷害。

因此，如果所有的對象都差不多大小，規則的網格可能仍是最好的選擇，只要細胞是至少一樣大（或者兩倍大？）作爲對象。

來源

2012-11-08 20:07:06 Astrotrain

避免基於網格的碰撞檢測中出現重複？

回答

相關問題