Помогите разобраться с пересечением объектов..

SiDDD · 08.03.2011, 00:59

Столкнулся с очередной головоломкой!

Наглядный пример - пули должны разбиваться о блок, что и происходит, пока пули летят через фрейм или реже (первая часть примера). Но стоит запустить их в каждом фрейме (вторая часть) - как нате вам.. Видно под таким напором блок устоять не может и поддается

Ширина пули больше её шага. Плюс ширина блока. Перескакивание невозможно! И если fps маленький - отлично видно, что пули ПЕРЕСЕКАЮТ блок.

Основной код:

Код AS3:

var aBlt:Array = [];    // массив для хранения пуль
var j:Number = 0;
var fMode:Boolean=true;
mBlck.x = 500;
 
 
stage.addEventListener(Event.ENTER_FRAME, fn1);
 
stop();
 
function fn1(event:Event):void{
 
  mBlck.x-=1;       // двигаем блок навстречу пулям
  if(mBlck.x<50){
    mBlck.x=500;
    fMode=!fMode;    // переключаем режимы 'стрельбы'
  }
 
  if(fMode){      // режимы 'стрельбы'
    if(j++>0){      // добавляем пулю через фрейм
      j=0;
      var mc:MovieClip=new mBullet();
      mc.x = 0;
      mc.y = 100 + Math.random() * 30;
      this.addChild(mc);
      aBlt.push(mc);
    }
  } else {
    // ..тоже самое! Но каждый фрейм.
    mc = new mBullet();
    mc.x = 0;
    mc.y=300 - Math.random() * 30;
    this.addChild(mc);
    aBlt.push(mc);
  }
 
  // проверяем на пересечение с блоком
  for each(var m:MovieClip in aBlt){
    if(mBlck.hitTestObject(m)){
      m.fnHit();                // сообщаем пуле о попадании
      aBlt.splice(aBlt.indexOf(m), 1);      // удаляем из списка
      this.removeChild(m);
    }
  }
}
 
 
 
function fnDel(zzz:DisplayObject):void {
  this.removeChild(zzz);
  zzz = null;
}

Код пули:

Код AS3:

var m:MovieClip=MovieClip(this.parent);
var nStp:Number=10;		// шаг для пули
 
 
this.addEventListener(Event.ENTER_FRAME, fn1);
 
 
function fn1(event:Event):void{
	if(x>550){			// если вылетели за этот предел..
		this.removeEventListener(Event.ENTER_FRAME, fn1);	// ..удаляем обработчик..
		m.fnDel(this);										// ..и себя
		return;
	}
	x+=nStp;				// двигаемся на этот шаг
}
 
function fnHit():void{
	this.removeEventListener(Event.ENTER_FRAME, fn1);
}

stweet · 08.03.2011, 01:16

Предлагаю более подробно ознакомиться с методами "hitTestObject()" и "hitTestPoint()" в вашей ситуации я бы поступил иначе:
1) Проверка дистанции от объекта до пули.

Код AS3:

public function hitTest (target:DisplayObject):void {
 
	for (var i:int = 0; i < objects.length; i++) {
		if (target != objects[i]) {
			// Тут мы проверяем дистанцию. "Википедия, Вычисление дистанции".
			if (dis < needDis) {
				// Вуаля, столкновение. =)
			}
		}
	}
}

2) Элементарная проверка координат пули и объекта.

Код AS3:

public function hitTest (target:DisplayObject):void {
 
	for (var i:int = 0; i < objects.length; i++) {
		if (target != objects[i]) {
			// Тут мы проыеряем на касание пули с объектом.
			if (target.x < objects[i].x + 10 &&
				target.x > objects[i].x - 10 &&
				target.y < objects[i].y + 10 &&
				target.y > objects[i].y - 10 ) {
				// Вуаля, столкновение. =)
			}
		}
	}
}

как-то так =)

maxkar · 08.03.2011, 02:09

Код AS3:

for each(var m:MovieClip in aBlt){
    aBlt.splice(aBlt.indexOf(m), 1);
}

Код выше - это плохая идея. Вообще, менять массив любым способом по ходу его итерации - плохая идея. Во втором случае в некоторые моменты времени с массивом пересекаются две соседних плашки. Удаляется только первая (вторая при итерации пропускается). На следующей итерации она удалится, но не удалится следующая и т.д. С учетом размера и скорости плашек, "пропускание" накапливается и в конце концов пуля преодолевает потенциальный барьер

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

stweet, не поможет изменение проверки.

SiDDD · 08.03.2011, 03:18

stweet Проверка была математической. Без всяких hitTest. Грешил, что где-то накосячил в расчетах. Постепенно выкинул все что мог пытаясь найти причину. Плюнул и написал этот пример с нуля, чтобы исключить все нестыковки. Но не тут то было.. Пришел к мысли, что ошибка связана с массивом, но как её поймать так и не решил.

maxkar Вот пасибо! А то я так и не понял в чем секрет slice!

Помогли исправить данную проблему таким советом: for each(var m:MovieClip in aBlt) -> for each(var m:MovieClip in aBlt.slice()).

Получается во время обхода всех элементов массива - я выдергивал из него один элемент - массив сжимался - и на следующем обходе я "терял" один элемент? Но чем помогает slice? slice выполняется каждый раз в начале цикла?

maxkar · 08.03.2011, 10:06

Цитата:

Получается во время обхода всех элементов массива - я выдергивал из него один элемент - массив сжимался - и на следующем обходе я "терял" один элемент?

Да, все правильно. По действию код был эквивалентен

Код AS3:

for (var i : int = 0; i < aBlt.length; i++)
    if (...)
        aBlt.splice(aBlt.indexOf(aBlt[i]), 1);

При удалении в позицию i перемещался следующий элемент (i+1), после чего i увеличивалось. Т.е. "следующий" элемент пропускался. Причем я еще не уверен, что на самом деле код итерации for each должен быть эквивалентен предыдушему (не особо искал в документации правда). А если он может быть не эквивалентен, то изменения при итерации могут иметь и еще более непредсказуемые эффекты.

Цитата:

Но чем помогает slice?

Со slice эквивалентный код становится примерно следующим:

Код AS3:

var tmp : Array = aBlt.slice();
for (var i : int = 0; i < tmp.length; i++)
    if (checkIntersection(tmp[i]))
        aBlt.splice(aBlt.indexOf(tmp[i]));

В этом коде tmp - это новая копия aBlt, ничем не связанная со своим оригиналом. Ну а так как ее изменений в цикле не производится, то все работает предсказуемо.

Цитата:

slice выполняется каждый раз в начале цикла?

Да, в начале каждой итерации. "Эквивалент" кода чуть выше.

Хотя в вашем случае slice все таки тяжеловат. Лишняя копия, затем поиск в массиве (хотя и быстрый) и удаление. Можно проще, с явной итерацией по индексу:

Код AS3:

var idx : int = 0;
while (idx < aBlt.length) {
    if (checkIntersection(aBlt[i])
        aBlt.splice(i, 1);
    else
        idx++;
}

Итерация по индексу явно позволяет показать, когда выполнять сдвиг, а когда - нет.

В вашем конкретном случае есть и еще один принципиально отличный от приведенных выше вариант. Он использует то, что пули отсортированы по горизонтали и если какая-то пуля еще не долетела до стенки, все остальные тоже не долетели. Тогда проверка идет только по одному элементу:

Код AS3:

while (aBlt.length > 0 && checkIntersection(aBlt[0])) {
    var m : MovieClip = aBlt.shift(); // удаляет первый элемент из aBlt
    m.fnHit();                     
    this.removeChild(m);
}

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

Код AS3:

var firstMiss : int = 0;
while (firstMiss < aBlt.length && checkIntersection(aBlt[0]))
    firstMiss++;
if (firstMiss > 0)
    for each (var m : MovieClip in aBlt.splice(0, firstMiss)) {
        m.fnHit();                     
        this.removeChild(m);
    }

В ряде случаев вызов fnHit и removeChild не писал, там восстановление их должно быть очевидно.

Выбирать в данном случае стоит тот вариант, котороый вам понятнее

SiDDD · 08.03.2011, 17:07

Цитата:

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

В вашем конкретном случае есть и еще один принципиально отличный от приведенных выше вариант. Он использует то, что пули отсортированы по горизонтали..

..по горизонтали отсортированы только для наглядности примера

На деле - исходная точка пули и блоки могут быть где угодно.

В итоге имею два варианта:
- первый (кто точно знает - 'aBlt.slice()' создает копию исходного массива при КАЖДОЙ итерации или только один раз при вхождении в цикл?)

Код AS3:

for each(var m:MovieClip in aBlt.slice()){
	if(mBlck.hitTestObject(m)){
		m.fnHit();
		this.removeChild(m);
		aBlt.splice(aBlt.indexOf(m), 1);
	}
}

- второй с использованием 'while' и декрементом индексов. В таком случае сдвиг массива не критичен.

Код AS3:

var m:MovieClip;
var i:int=aBlt.length-1;
while(i){
	m=aBlt[i];
	if(mBlck.hitTestObject(m)){
		m.fnHit();
		this.removeChild(m);
		aBlt.splice(aBlt.indexOf(m), 1);
	}
	i--;
}

Какой из вариантов быстрее - надо еще проверить.

======================================================================================

Цитата:

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

"slice выполняется каждый раз в начале цикла"
Да, в начале каждой итерации. "Эквивалент" кода чуть выше.

..проверил таким способом:

Код AS3:

	...
trace("start");
for each(var m:MovieClip in fnMy()){
	if(mBlck.hitTestObject(m)){
		m.fnHit();
		this.removeChild(m);
		aBlt.splice(aBlt.indexOf(m), 1);
	}
}
trace("end");
...
 
 
function fnMy():Object{
	trace("fn");
	return aBlt.slice();
}

Output:

Код:

start
fn
end
start
fn
end

Получается ф-ция вызывается только один раз при первом входе в цикл.

======================================================================================

Более быстрым оказался цикл 'while': Странное поведение 'for each' при 50% отсеивания

(NNN=-1) Отсеивается 100%......while: 60.....for each: 95
(NNN=5000) Отсеивается 50%.....while: 32.....for each: 645!!
(NNN=20000) Отсеивается 0%.....while: 3.......for each: 3

Код AS3:

var aBlt:Vector.<Object> = new Vector.<Object>();		// массив для хранения пуль
var obj:Object;
var o:Object;
var t:int;
var i:int;
 
mBlck.x=NNN;
 
stage.addEventListener(Event.ENTER_FRAME, fn1);
stop();
 
 
function fn1(event:Event):void{
	for(i=0; i<10000; i++){
		obj=new Object();
		obj.x=i;
		aBlt.push(obj);
	}
 
	var t = getTimer();
	i=aBlt.length-1;
	while(i){
		o=aBlt[i];
		if(o.x>mBlck.x){
			fnZ(o);
			aBlt.splice(i, 1);
		}
		i--;
	}
	tOut.text="" + (getTimer()-t);
/*
	var t = getTimer();
	for each(o in aBlt.slice()){
		if(o.x>mBlck.x){
			fnZ(o);
			aBlt.splice(aBlt.indexOf(o), 1);
		}
	}
	tOut.text="" + (getTimer()-t);
*/
}
 
 
 
function fnZ(tmp:Object):void {
	var zzz:Object=tmp;
}

maxkar · 08.03.2011, 22:30

В while с декрементом багу поправьте. Там первый элемент не проверяется. Условие должно быть while(i >= 0).

Да, по производительности while с конца на самом деле будет не хуже итерации по for each. При удалении элемента в "середине" массива этот массив нужно сдвигать. Если сдвигать "конец" массива, то при итерации "с конца" там будут только "выжившие" элементы. А при цикле for each придется сдвигать и элементы, которые потом будут удалены. Как раз это и дает сильный рост при удалении половины элементов на for each. Флеш-плеер может пытаться оптимизировать удаление (удаление на границе оптимизирует, это видно по вашим тестам), но в этом случае это сделает итерации for each и while эквивалентными по времени.

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

И еще замечание. Если у вас в реальном приложении будет много удалений в середине массива, быстреер всего делать фильтрацию, это дает максимум 1 проход по массиву + затраты на выделение памяти. Псевдокод:

Код AS3:

var oldValues : Array = aBlt;
aBlt = new Array();
for each (var o : object in oldValues)
  if (isGood(o))
    aBlt.push(o);
  else {
    removeChild(o);
    ...
  }

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

SiDDD · 09.03.2011, 03:15

Исправил чутка по своему:

Код AS3:

i=aBlt.length;
while(i){
	i--;
	o=aBlt[i];
	if(o.x>mBlck.x){
		fnZ(o);
		aBlt.splice(i, 1);
	}
}