Была такая же проблема в игре было много кораблей и снарядов. И надо было найти все пересечения снарядов со всеми кораблями. Алгоритм с простым перебором был жутко медленный. Поэтому мы сделали так:
Разбили пространство на виртуальные квадраты с размером
size
Для этого мы создаем
map и для каждой окружности мы ищем ее
key.
key = Math.floor(circle.x / size) + "_" + Math.floor(circle.y / size)
if(!map[key]) map[key] = [];
map[key].push(circle);
Далее мы просто проходимся по ключам
map и проверяем пересечения окружностей внутри квадрата. Получается, что проверок становится намного меньше благодаря группировки кругов в квадраты.
Так же можно оптимизировать проверку пересечений кругов. Для круга мы должны знать его радиус.
function isCollided(circle0, circle1)
{
var maxDistanceSquared = circle0.radius + circle1.radius;
maxDistanceSquared *= maxDistanceSquared;
var dx = circle0.x - circle1.x;
var dy = circle0.y - circle1.y;
var currentDistanceSquared = dx * dx + dy * dy;
return currentDistanceSquared < maxDistanceSquared;
}
Средний
