Проверка столкновения шариков

[baka]

Мне нужно рассчитать столкновения шариков, я использую алгоритм из книжки Джоба Макара:

(проверяется столкнутся ли шары в следующем кадре)

function ballToBallDetection(b1, b2) {
	//set the speed variables
	var xspeed1 = _root.yiff[b1].xspeed;
	var yspeed1 = _root.yiff[b1].yspeed;
	var xspeed2 = _root.yiff[b2].xspeed;
	var yspeed2 = _root.yiff[b2].yspeed;
	//set the position variables
	var xl1 = _root.yiff[b1].xpos;
	var yl1 = _root.yiff[b1].ypos;
	var xl2 = _root.yiff[b2].xpos;
	var yl2 = _root.yiff[b2].ypos;
	//define the constants
	var R = _root.yiff[b1].radius + _root.yiff[b2].radius;
	var a = -2 * xspeed1 * xspeed2 + xspeed1 * xspeed1 + xspeed2 * xspeed2;
	var b = -2 * xl1 * xspeed2 - 2 * xl2 * xspeed1 + 2 * xl1 * xspeed1 + 2 * xl2 * xspeed2;
	var c = -2 * xl1 * xl2 + xl1 * xl1 + xl2 * xl2;
	var d = -2 * yspeed1 * yspeed2 + yspeed1 * yspeed1 + yspeed2 * yspeed2;
	var e = -2 * yl1 * yspeed2 - 2 * yl2 * yspeed1 + 2 * yl1 * yspeed1 + 2 * yl2 * yspeed2;
	var f = -2 * yl1 * yl2 + yl1 * yl1 + yl2 * yl2;
	var g = a + d;
	var h = b + e;
	var k = c + f - R * R;
	//solve the quadratic equation
	var sqRoot = Math.sqrt(h * h - 4 * g * k);
	var t1 = (-h + sqRoot) / (2 * g);
	var t2 = (-h - sqRoot) / (2 * g);
	if (t1 > 0 && t1 <= 1) {
		var whatTime = t1;
		var ballsCollided = true;
	}
	//trace(t1 + "  " + t2);               
	if (t2 > 0 && t2 <= 1) {
		if (whatTime == null || t2 < t1) {
			var whatTime = t2;
			var ballsCollided = true;
		}
	}
	if (ballsCollided) {
		//Collision has happened, so throw a trace
		ball2BallReaction(b1, b2, xl1, xl2, yl1, yl2, whatTime);
	}
}

Перебор комбинаций:

for (var i = 20; --i; ) {
	for (var j = i; --j; ) {
		//проверка столкновения шара i с шаром j
	}
}

Однако если шаров больше 20 то начинает заметно тормозить. Есть ли более быстрое решение?

[VVall]

Не очень понял, зачем такой сложный код - почему просто не проверить расстояние между центрами шаров? Как вариант, можно сначала проверять расстояние, и если шары достаточно близко, делать более точную проверку.

[baka]

Сообщение от VVall

Не очень понял, зачем такой сложный код - почему просто не проверить расстояние между центрами шаров?

Летят себе 2 шара друг на встречу другу, у обоих радиусы 10, начальное расстояние между ними допустим 100, а скорость у каждого 1000. Проверяем расстояние между центрами в первом кадре - получаем 100, проверяем во втором кадре, получаем 1900. Ну и где столкновение?

Сообщение от VVall

Как вариант, можно сначала проверять расстояние, и если шары достаточно близко, делать более точную проверку.

Понятие "достаточно близко" определяется максимальной скоростью шаров, если скорость не ограничена то такого понятия не существует. У меня она ограничена 1/3 размера экрана, так что такая оптимизация практически ничего не дает.

[Division]

baka, читай про broad phase. Сделать хеширование какое-то - самый простой способ. тут была интересная тема про шарики: http://www.gamedev.ru/code/forum/?id=88430 - если порыться, можно найти исходники и объяснения как люди делают.

UPD: тут лучше: http://noregret.org/tutor/n/grid/

[VVall]

baka, а зачем вы так делаете, что у вас скорость может быть 1000? Это легко решается разбиением одного шага на много более маленьких шагов.

[baka]

Сообщение от VVall

baka, а зачем вы так делаете, что у вас скорость может быть 1000?

Она может быть намного больше суммы радиусов летящих объектов.

[VVall]

Я уже сказал - это легко решается.

[Division]

baka, VVall, без broad phase ничего не выйдет. Серьёзно.