本文介紹了二維均勻網(wǎng)格碰撞檢測(cè)算法的處理方法，對(duì)大家解決問(wèn)題具有一定的參考價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧！
問(wèn)題描述
我正在做一個(gè)2D街機(jī)游戲，我有5種不同大小的圓圈：船、導(dǎo)彈和3種怪物。
如下所示：
目前我正在使用暴力碰撞檢測(cè)，在不考慮碰撞概率的情況下，我檢查每一枚導(dǎo)彈和每一只怪物。遺憾的是，這會(huì)讓這個(gè)過(guò)程變得非常緩慢。
這是我的網(wǎng)格類，但它不完整。我將非常感謝你的幫助。
public class Grid {
int rows;
int cols;
double squareSize;
private ArrayList<Circle>[][] grid;
public Grid(int sceneWidth, int sceneHeight, int squareSize) {
this.squareSize = squareSize;
// Calculate how many rows and cols for the grid.
rows = (sceneHeight + squareSize) / squareSize;
cols = (sceneWidth + squareSize) / squareSize;
// Create grid
this.grid = (ArrayList[][]) new ArrayList[cols][rows]; //Generic array creation error workaround
}
The addObject method inside the Grid class.
public void addObject(Circle entity) {
// Adds entity to every cell that it's overlapping with.
double topLeftX = Math.max(0, entity.getLayoutX() / squareSize);
double topLeftY = Math.max(0, entity.getLayoutY() / squareSize);
double bottomRightX = Math.min(cols - 1, entity.getLayoutX() + entity.getRadius() - 1) / squareSize;
double bottomRightY = Math.min(rows - 1, entity.getLayoutY() + entity.getRadius() - 1) / squareSize;
for (double x = topLeftX; x < bottomRightX; x++) {
for (double y = topLeftY; y < bottomRightY; y++) {
grid[(int) x][(int) y].add(entity); //Cast types to int to prevent loosy conversion type error.
}
}
}
但這就是我完全不知所措的地方。我甚至不確定我提供的源代碼是否正確。請(qǐng)讓我知道如何使基于網(wǎng)格的碰撞工作。我基本上讀過(guò)了我能弄到的所有教程，但沒有多少效果。
謝謝。
推薦答案
我發(fā)現(xiàn)在對(duì)象本身中存儲(chǔ)表示對(duì)象與哪些單元格重疊的二進(jìn)制數(shù)更容易(我猜也更快)(而不是為每個(gè)單元格保存一個(gè)數(shù)組)。我認(rèn)為它被稱為空間蒙版。
更具體地說(shuō)，在任何碰撞測(cè)試之前，我為topLeft、topRight計(jì)算2^(x/column_width + columns*y/row_width)…然后將這4個(gè)組合成一個(gè)數(shù)字(使用按位OR)，這樣我就得到了一個(gè)類似5(00000011，表示對(duì)象命中單元格1和2)的數(shù)字。
使用這種方法，然后使用所有其他對(duì)象繼續(xù)測(cè)試每個(gè)對(duì)象，但如果它們不在同一單元格中，則跳過(guò)較慢的部分：
-
檢查兩個(gè)對(duì)象中數(shù)字的位與(僅當(dāng)兩個(gè)對(duì)象的某些單元格都為
1時(shí)才為!=0)。如果結(jié)果不是
0，請(qǐng)執(zhí)行適當(dāng)?shù)?緩慢的)沖突檢查(在您的情況下可能是畢達(dá)哥拉斯，因?yàn)樗鼈兪菆A，我認(rèn)為畢達(dá)哥拉斯比檢查邊界正方形更快)。
這篇關(guān)于二維均勻網(wǎng)格碰撞檢測(cè)算法的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，
