В попытке оптимизации нахождение коллизии(столкновение) блоков был найден способ сортировки методом "Регулярной сеткой" вопрос как с помощью алгоритма "Ограничителя" описать это условие:
Имеется массив блоков(зеленый цвет)
Из этого массива проверяются коллизия блоков находящиеся в кубе ограничителе(желтый цвет)
Проверка идёт между главным кубом(красный цвет) и массивом кубов(зелёный цвет)
Всё что за ограничителем (желтый цвет) не провертывается на столкновение.
Регулярная сеть
Как вы, вероятно, уже догадались из названия, суть алгоритма сводится к тому, что все пространство делится на равномерную сеть из маленьких квадратиков, размер которых равен диаметру частицы. Каждый такой квадратик(ячейка) этой сети представляет собой массив. Выглядеть это может, например, так:
const int _GRID_WIDTH = (int)(WIDTH / (RADIUS_P * 2.0f));
const int _GRID_HEIGHT = (int)(HEIGHT / (RADIUS_P * 2.0f));
std::vector<Particle *> _grid[_GRID_WIDTH][_GRID_HEIGHT];
На каждой итерации главного цикла эта сеть очищается и заново заполняется. Алгоритм заполнения предельно прост: индекс ячейки частицы вычисляется путем деления обеих координат на диаметр частицы и отбрасыванием дробной части. Пример:
int x = (int)(_particles[i].pos.x / (RADIUS_P * 2.0f));
int y = (int)(_particles[i].pos.y / (RADIUS_P * 2.0f));
Таким образом, для каждой частицы необходимо вычислить индекс и внести ее в ячейку с этим индексом(добавить элемент в массив). Теперь остается только пройтись по каждой ячейке и проверить все ее частицы со всеми частицами соседних, окружающих ее 8 ячеек, при этом не забыв проверить с самой собой.
Это можно сделать так:
void Update()
{
for (int i = 0; i < _GRID_WIDTH; ++i) {
for (int j = 0; j < _GRID_HEIGHT; ++j) {
_grid[i][j].clear();
}
}
for (int i = 0; i < MAX_P; ++i) {
int x = (int)(_particles[i].pos.x / (RADIUS_P * 2.0f));
int y = (int)(_particles[i].pos.y / (RADIUS_P * 2.0f));
_grid[x][y].push_back(&_particles[i]);
}
// далее много циклов проверки с соседними ячейками
}
Сложность: O(n)
Плюсы: * Самый быстрый из всех
- Прост в реализации
Минусы:
Требуется дополнительная память
Чувствителен к разным размерам частиц(требуется модификация)