Как эффективно удалить повторяющиеся пары столкновений в пространственной хеш-сетке? ⇐ JAVA

[Anonymous]

Я работаю над 2D-игрой для Android, поэтому производительность — это реальная проблема, и она просто необходима. В этой игре может произойти много столкновений между любыми объектами, и я не хочу проверять перебором o(n^2), сталкивается ли какой-либо игровой объект с другим. Чтобы уменьшить возможное количество проверок на коллизии, я решил использовать пространственное хеширование в качестве широкофазного алгоритма, поскольку он кажется довольно простым и эффективным — разделение сцены на строки и столбцы и проверка коллизий между объектами, находящимися только в одном элементе сетки.

Вот основная концепция, которую я быстро набросал:

Код: Выделить всё

public class SpatialHashGridElement
{
HashSet gameObjects = new HashSet();
}
static final int SPATIAL_HASH_GRID_ROWS = 4;
static final int SPATIAL_HASH_GRID_COLUMNS = 5;
static SpatialHashGridElement[] spatialHashGrid = new SpatialHashGridElement[SPATIAL_HASH_GRID_ROWS * SPATIAL_HASH_GRID_COLUMNS];

void updateGrid()
{
float spatialHashGridElementWidth = screenWidth / SPATIAL_HASH_GRID_COLUMNS;
float spatialHashGridElementHeight = screenHeight / SPATIAL_HASH_GRID_ROWS;
for(SpatialHashGridElement e : spatialHashGrid)
e.gameObjects.clear();
for(GameObject go : displayList)
{
for(int i = 0; i < go.vertices.length/3; i++)
{
int row = (int) Math.abs(((go.vertices[i*3 + 1] / spatialHashGridElementHeight) % SPATIAL_HASH_GRID_ROWS));
int col = (int) Math.abs(((go.vertices[i*3 + 0] / spatialHashGridElementWidth) % SPATIAL_HASH_GRID_COLUMNS));
if(!spatialHashGrid[row * SPATIAL_HASH_GRID_COLUMNS + col].gameObjects.contains(go))
spatialHashGrid[row * SPATIAL_HASH_GRID_COLUMNS + col].gameObjects.add(go);
}
}
}

Код, вероятно, не самого высокого качества, поэтому, если вы заметите что-то, что нужно улучшить, не стесняйтесь сообщать мне, но самая тревожная проблема, которая возникает в настоящее время, заключается в том, что в двух ячейках сетки могут быть проверены одни и те же пары столкновений. Пример наихудшего случая (при условии, что ни один из объектов не занимает более двух ячеек):




Здесь у нас есть два сталкивающихся игровых объекта (красный и синий). Каждый из них находится в 4 ячейках => поэтому в каждой ячейке будет одна и та же пара для проверки.
Я не могу придумать какой-то эффективный подход, чтобы исключить возможность дублирования пар без необходимости фильтровать сетку после ее создания в updateGrid(). Есть ли какой-нибудь блестящий способ обнаружить, что какая-то пара коллизий уже была вставлена ​​даже во время функции updateGrid? Буду очень благодарен за любые советы!

Подробнее здесь: https://stackoverflow.com/questions/311 ... -hash-grid