代表java中的2d球

我正在創建一個應用程序，我需要使用java爲大量的二維「球」（圓圈）建模（並顯示）。我已經開始創建一個ArrayList的Circle對象（我定義的一個類，它的x/y像素座標是圓的中心，半徑，顏色和x方向上的速度）。我用一個java.util.Timer對象與重複的TimerTask來控制圓圈的運動。圓圈的大小從10-50像素半徑變化。代表java中的2d球

我想要發生的是球從屏幕的頂部落下（隨機分佈在X軸上），直到它們到達屏幕的底部，這就像一個地板球，它到達它停止移動，並且到達停止的球的球在其他球上向下滾動，直到它們停在低點/平坦點。在未來，我可能想讓他們的行爲更復雜一點，所以我想創建靈活的代碼，以便我可以輕鬆擴展。現在它的工作原理是，每個圈子的每個時間段檢查一下，看看它們與其他圈子有多接近。如果附近沒有其他圈子，他們會繼續正常下降。如果兩個（或更多）圓圈彼此靠近，則會有代碼確定它們將如何進行交互。

我對小數目的圓圈（< 200）完美地工作，但是當我獲得更大數目的圓圈（> 400）時，它開始顯着減慢。我確信我可以優化一些邏輯來使比較更快一些，但是我想知道是否有任何方法將圓存儲在除了無組織的ArrayList之外的某種結構中，以便我可以輕鬆找到接近於彼此，所以我不必做N^2比較每個圓與其他每個圓的操作，而只是比較一個圓與最接近它的5-10個圓。例如，我已經考慮使用二維數組來表示每個像素（或者可能是5x5像素的正方形），並在其中心位置存儲一個圓圈（這樣我可以檢查是否有任何附近單元格中有圓圈，並忽略休息）。但是，這仍然看起來效率很低，就好像我使用800x1000像素的畫布和500個圓圈一樣，在2d陣列中會出現TON空白空間，我會浪費時間檢查。我也考慮過某種hashmap，但我還沒有想過使用它的好方法。

那麼，任何人都可以想到一個有效的方式來存儲這些圓對應於它在2d空間的位置，並可以很容易地找到附近的圓圈嗎？提前致謝！

來源

2012-07-26 scaevity

http://en.wikipedia.org/wiki/Quadtree – Bart 2012-07-26 22:06:33

這通常與四叉樹完成：http://en.wikipedia.org/wiki/Quadtree – corsiKa 2012-07-26 22:06:43

這個問題被稱爲「碰撞檢測的物理模擬」。有一個關於它的巨大文獻。試試谷歌搜索。你說得對，一個簡單的二維空間哈希方案會對你的特定問題產生很大的加速。但是，每個像素不需要一個bin。更大的垃圾箱將產生很好的加速。 – Gene 2012-07-26 22:09:49

您可以使用QuadTree查找近鄰。或者您可以簡單地按照一個方向排序，這將更容易實施，並且仍然允許您將候選鄰居的數量減少到一個小窗口。

來源

2012-07-26 22:06:36 MvG

謝謝，四叉樹聽起來像它可能非常有用！ – scaevity 2012-07-27 16:10:32

Quadtree可以很好地解決許多物品靜止不動的問題。但是當許多項目都在同時運動時，可能不太好。每幀更新一次比單純的二維網格要貴得多。每幀排序一次是合理的，但應該使用一種在「幾乎排序的數據」上表現良好的算法。 – Gene 2012-07-27 20:05:05

也許你對二維數組的想法並不那麼瘋狂。我想你想要的是你所有圈子的一個列表，以及一個可以引用這些圈子的二維數組。所以每次都可以遍歷你的List<Circle>來檢查每一個。每個Circle都有x，y座標，你只需要在你的數組上循環（x，y +/- 5）。沒有必要爲Circles檢查整個可能的空間，因爲你已經在跟蹤每個Circle的中心。只需抓住中心，並檢查其他圈子。

來源

2012-07-26 22:14:35 Carl

代表java中的2d球

回答

相關問題