Обнаружение пересечения объектов

[Mylton]

Здравствуйте, у меня генерируется объекты на поле

function addscull (e:Event)
{	
	scull_Num = scull_Num+1;
	var menuscull = new menuskullobj();
	menuscullposition_x = Math.random()*(stage.stageWidth+stage.stageWidth/4)-stage.stageWidth/8;
	menuscullposition_y = Math.random()*(stage.stageHeight+stage.stageHeight/4)-stage.stageHeight/8;
	menuscull.x = menuscullposition_x;
	menuscull.y = menuscullposition_y;
	menuscull.ymov = Math.random()*6-3;
	menuscull.xmov = Math.random()*6-3;
	titlescreen.addChildAt (menuscull,0);
	menuscull.addEventListener (Event.ENTER_FRAME, scullmove);
	if (scull_Num == 100)
	{
		menusculltimer.stop();
		//trace ("генерация закончилась");
	}
}
 
function scullmove (e:Event)
{
	var singlescull = e.currentTarget;
	singlescull.x += singlescull.xmov;
	singlescull.y += singlescull.ymov;
	if (singlescull.y > stage.stageHeight+stage.stageHeight/8)
	{
		singlescull.ymov *= -1;
	}
	if (singlescull.x > stage.stageWidth+stage.stageWidth/8)
	{
		singlescull.xmov *= -1;
	}
	if (singlescull.y < -stage.stageHeight/8)
	{
		singlescull.ymov *= -1;
	}
	if (singlescull.x < -stage.stageWidth/8)
	{
		singlescull.xmov *= -1;
	}
}

Есть ли возможность как то придать идентификатор каждому появляющемуся объекту, чтобы потом вычислить их пересечения? Я недалек в AS3, поэтому и спрашиваю.
Чтобы получилось что то вроде:

scull_Num = scull_Num+1;
var menuscull[scull_Num] = new menuskullobj();
if (singlescull[this.scull_Num].hitTestObject (menuscull[scull_Num < this.scull_Num < scull_Num])
{trace("cross")}

Я понимаю, что тут ересь написана, но смысл в том, чтобы он определял hitTestObject'ом пересечения со всеми другими, кроме себя.

Заранее спасибо.

[dimarik]

Как вариант. Обычный перебор каждого с каждым на двух циклах

var a:Array /* of DisplayObject */;
const len:uint = a.length;
for (var outer:uint = 0; outer < len; outer++) {
    var master:DisplayObject = a[outer] as DisplayObject;
    for (var inner:uint = 0; inner < len; inner++) {
        if (outer == inner) // самого себя не проверяем
            continue;
        var slave:DisplayObject = a[inner] as DisplayObject;
        if ( master.hitTestObject(slave) ) {
            trace('Bingo!');
        } 
    }
}

Только здесь присутствует избыточная проверка, т.к. в определенные моменты master меняется местами со slave.
А вот это вам на десерт.

[caseyryan]

dimarik, вопрос, у вас там в mail.ru специально ставят программистам задачи без необходимости усложнять даже самые простые вещи? Видимо поэтому сервисы мэйл.ру всегда самые тормозные и наполненные ошибками из всех.
Честно сказать, не понял зачем здесь гонять 2 цикла, когда задачу можно решить одним

var array:			Array 			= [/*какие-то объекты*/];
var length:			uint 			= array.length;
var targetObject:	DisplayObject 	= null;
 
for (var i:int = 0; i < length; i++) {
    targetObject = array[i] as DisplayObject;
	if (targetObject != this) {
		if (this.hitTestObject(targetObject)) {
			trace("столкновение");
		}
	}
}

Ну или, если задача не относится к this, то как-то так

var array:			Array 			= [/*какие-то объекты*/];
var length:			uint 			= array.length;
var targetObject:	DisplayObject 	= null;
var myObjectIndex:	int				= array.indexOf(someObject); // хоть indexOf и использует цикл внутри, но, во-первых он выполнится всего 1 раз, а во-вторых не засоряет код лишними строчками
 
for (var i:int = 0; i < length; i++) {
    targetObject = array[i] as DisplayObject;
	if (i != myObjectIndex) {
		if (someObject.hitTestObject(targetObject)) {
			trace("столкновение");
		}
	}
}

Это хотя бы выглядит более читабельно

[samana]

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

Только здесь присутствует избыточная проверка, т.к. в определенные моменты master меняется местами со slave.

Если что, можно же и без лишней проверки сделать:

//псевдокод
var objects:Array = [1, 2, 3, 4, 5, 6];
 
for (var i:int = 0; i < arr.length; i++) 
{
	for (var j:int = i+1; j < arr.length; j++) 
	{
		trace("проверка пары",i,j)
		if (objects[i].hitTextObject(objects[j]))
		{
			trace("Было столкновение между объектами", i, "и", j);
		}
	}
}

проверка пары 0 1
проверка пары 0 2
проверка пары 0 3
проверка пары 0 4
проверка пары 0 5
проверка пары 1 2
проверка пары 1 3
проверка пары 1 4
проверка пары 1 5
проверка пары 2 3
проверка пары 2 4
проверка пары 2 5
проверка пары 3 4
проверка пары 3 5
проверка пары 4 5

[nubideus]

Есть ли возможность как то придать идентификатор каждому появляющемуся объекту, чтобы потом вычислить их пересечения?

var a:Array /* of DisplayObject */;
var array: Array = [/*какие-то объекты*/];
//псевдокод
var objects:Array = [1, 2, 3, 4, 5, 6];

лол

да что вы все усложняете, перебор делается очень просто, да еще и в один цикл

var arr:Array = [1, 2, 3, 4];
var result:Array = [];
var i:uint = 0;
var j:uint = 0;
while(1){
  if(++j === arr.length){
    j = ++i + 1;
    if(i >= arr.length - 1) break;
  }
  result.push([arr[i], arr[j]]);
}
trace(result.join(" | ")); // "1,2 | 1,3 | 1,4 | 2,3 | 2,4 | 3,4"

[samana]

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

да что вы все усложняете, перебор делается очень просто, да еще и в один цикл

Возможно и так, способов много, но прочитать Ваш код, понять его алгоритм довольно не просто.
p.s. а может это только для меня так...

[dimarik]

N циклов в один можно легко уложить. Значительно сложнее привести сложность алгоритма из o(n^2) хотя бы в o(n log n). Так что все кайзерманы идут лесом со своими претензиями к моей компании. samana разрулил избыточность, хотя я предполагал, что это сделает топикстартер сам.

[nubideus]

что значит "хотя бы", n log n это очень хорошо, я бы даже сказал что сделать проще невозможно

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

но там все равно n^2

[dimarik]

Кхм, ты читал?

[nubideus]

Кхм, ты читал?

что читал?
если ты про дерево то там n log n