Как эффективно просчитывать столкновения сотен объектов?

[Tahion]

Котяра для сотен вполне сгодится для тысяч вероятно нет но не факт). Разчет колизий даже по битмап дате сотен и тысяч объектов не особо трудоемкая задача для ас3. Так что тут просто Zebestov разводит флейм о непонять чем). Даже не буду читать что он там в очередной раз написал

А вот игнорирование оптимизации приводит к тому, что все кричат: "Флэш - ***** и тормоз" (извините, но слов из песни не выкинешь) - Зависит от автора приложения мой вариант не будет трудоемким для 200 объектов типа круг или квадрат . Так что для данной задачи больше не надо

Волгоградец -Ага можно но не всегда удобно) к томуже я когда делал посмотрел что и так сойдет, главное Point.distance убрал который работает в 4 раза медленней :/

Zebestov
"
повторюсь: отставить троллизм!

P.S.
это слово пишется так: collision
__________________
"
Куда же смотрит модератор? Человеку уже нечего сказать причем сказать не в тему

Не удивительно слышать это от человека, который настолько пренебрегает оптимизацией, что не додумался сравнивать не корень квадратный с непонятной суммой в скобках, а просто квадрат дистанции с заранее и один раз подсчитанным квадратом диаметра шарика.

1. Радиус круга
2. В скобках 2 радиуса круга 1 сложение совершенно не трудоемкая операция...
3. Тут вообще не нужен никакой квадрат диамитра шарика. Вы вообще о чем говорите?)

К слову пример котрый игра астеройды давольно отвратителен если кто его разбирал, я когда то его дасканально изучал . И думаю тут нужно было бы скорее приводить в пример любой физический движок из популярных например box2d etc...

[-De-]

Макконел про всё писал, по-моему. У флэша легко получить тормозной рендер (и он правда не шибко быстрый), вот и есть слава тормоза.
Ну вот с кодом lumaca перебор занял 15 мс (в цикле и я ещё оптимизировал(тм), убрав Math.abs, 60 раз - 701 мс), где без оптимизации(тм), а тупо

var dx:Number = (xx - other.x);
var dy:Number = (yy - other.y);
if (dx*dx+dy*dy < mine.r2 + other.r2) {
	collision(mine, other);
}

11 мс и 631 мс в цикле 60 раз.
Многобукав полный код:

package 
{
	import flash.display.MovieClip;
	import flash.display.Sprite;
	import flash.events.*;
	import flash.net.*;
	import flash.utils.*;
 
	public class Main extends Sprite 
	{
 
		public function Main():void 
		{
			if (stage) init();
			else addEventListener(Event.ADDED_TO_STAGE, init);
		}
		private var objs:Array = new Array();
		private function init(e:Event = null):void 
		{
			removeEventListener(Event.ADDED_TO_STAGE, init);
			for (var i:int = 0; i < 200; ++i) {
				objs.push(new Obj(Math.random() * 1000, Math.random() * 1000, Math.random() * 10));
			}
			trace(objs.length);
			var t:Number = getTimer();
			for (i = 0; i < 60; ++i) colTest();
			trace(getTimer() - t);
		}
 
		private function colTest():void {
			var i:int;
			var j:int;
			for (i = 0; i < 199; ++i) {
				for (j = i+1; j < 200; ++j) {
					var mine:Obj = objs[i];
					var other:Obj = objs[j];
					var xx:Number = mine.x;
					var yy:Number = mine.y;
					/* unoptimized */
					var dx:Number = (xx - other.x);
					var dy:Number = (yy-other.y);
					if (dx*dx+dy*dy < (mine.r + other.r)*(mine.r + other.r)) {
						collision(mine, other);
					}
					/*end unoptimized */
					/* optimized */
					/*var rr:Number = mine.r + other.r;
					var dx:Number = (xx - other.x);// Math.abs(xx - other.x);
					if (dx < 0) dx = -dx;
					if (dx<rr){
						var dy:Number = (yy - other.y);// Math.abs(yy - other.y);
						if (dy < 0) dy = -dy;
						if (dy<rr) {
							var distance:Number = dx*dx+dy*dy;
							if (distance<(mine.r + other.r)*(mine.r + other.r)) {
								collision(mine, other);
							}
						}
					}*/
					/* end optimized */
				}
			}
		}
		private function collision(i:Obj, j:Obj):void {
 
		}
	}
 
}
class Obj {
	public var x:Number;
	public var y:Number;
	public var r:Number;
	public var r2:Number;
	public function Obj(_x:Number, _y:Number, _r:Number) {
		x = _x;
		y = _y;
		r = _r;
		r2 = r * r;
	}
}

[Tahion]

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

Поидее for each быстрее должен работать кстати). Ну это так... :[ ну и еще если объявление перменных вынести из цикла. Ну это так небольшие изменения

Добавлено через 1 час 26 минут
Кстати говоря вот во вложении хит тест по битмапу 40000 - 200х200 поставить
мой результат 150 и 33 хит тест обжект ну это конечно для такого количество объектов уже плоховато в ентерфрейме если висит . Но помню както это делалось быстрее чем у меня есть но как не помн...

[Zebestov]

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

1. Радиус круга
2. В скобках 2 радиуса круга 1 сложение совершенно не трудоемкая операция...
3. Тут вообще не нужен никакой квадрат диамитра шарика. Вы вообще о чем говорите?)

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

если же шарики имеют произвольный радиус, то вычислять квадрат суммы радиусов столкнувшихся шаров и сравнивать с суммой квадратов dx и dy. именно в этом оптимизация даже твоего приведенного кода.

и еще. количество итераций при проверке столкновений N шариков можно свести не к N * (N - 1), а к половине этого числа. при такой оптимизации еще и уйдет if.

[Tahion]

Можно вообще сортирвоать список объектов по координатам и хитрым способом зарание знать что часть из них не столкнулись с частью других, хотя об этом было с самого начала но там немного не так. Вообще можно посомреть в либе алгоритмов математических, наверника все давно придумали .

Добавлено через 20 часов 32 минуты
Сейчас решил сделать как написал Zebestov

и еще. количество итераций при проверке столкновений N шариков можно свести не к N * (N - 1), а к половине этого числа. при такой оптимизации еще и уйдет if.

И просто тестировал вариант -De- одно тоько вынесение объявление каждый раз main уменьшает время вдвое почти

[Zebestov]

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

...
И просто тестировал вариант -De- одно только вынесение объявление каждый раз main уменьшает время вдвое почти

ну вот видишь! порой оптимизация сводится к простому вынесению строчки кода за пределы цикла, а ты говоришь "тратить время"