Подскажите эффективный способ упорядочения объектов в контейнере

[mikhailk]

Задача стандартная. Есть containerObjects, в котором порядка 10-40 объектов. В общем случае все они могут двигаться.

По таймеру вызываем функцию, которая заменяет индексы у объектов containerObjects в соответствии с их позицией y (чем больше y - тем больше индекс).

Вариант 1 я сделал с массивом, но он мне реально не понравился, поскольку вылезли тормоза:


var objectsList:Array = new Array();
for(var i:int=0;i<containerObjects.numChildren;i++) {
var currObj:Object = containerObjects.getChildAt(i);
var objectY:int = currObj.y;
objectsList.push({object:currObj, objY:objectY});
}
objectsList.sortOn(["objY"]);
for(var i = 0; i < objectsList.length; i++) {
containerObjects.setChildIndex(object, i);
}


Потом я еще поэксперементировал со swapChildren (тут в одной из тем было), но тоже получается не очень.

Интересует максимально простое решение.

[Котяра]

при большом количестве объектов для пересортировки нужно использовать разделение на сетки (http://www.gskinner.com/blog/archives/2009/11/as3_proximityma.html)
кроме того сортировать только те объекты у которых реально поменялись координаты y c прошлой сортировки.

[mikhailk]

ну, у меня все-таки не 5000 объектов, к счастью... )))

конкретный пример

10 объектов, индексы упорядочены по возрастанию. Объект с индексом 1 встал перед объектом с индексом 5, а объект с индексом 8 встал за ними обоими. Поменялись координаты у объектов 1 и 8, но сортировать нужно 1, 5 и 8. Это я к тому, что сортировкой только переместившихся не обойтись, наверное.

[bicubic_bublic]

сортировка массива. сложность: n * ln(n);
изменение положение одного элемента в упорядоченном массиве: ln(n)

[mikhailk]

это понятно
просто в примере, который я привел, нужно еще выяснить, кто с кем перекрывается. Двигались-то 1-й и 8-й, а упорядочивать нужно 1-й, 5-й и 8-й. Т.е, этого 5-го еще нужно вычислить.

или я неправильно понял?

или так?

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

[Zebestov]

private function sortChildren(mc:MovieClip):void
{
var arr:Array = [];
var num:uint = mc.numChildren;
var i:uint;
var chld:MovieClip;
for (i = 0; i < num; i++)
{
chld = mc.getChildAt(i);
arr.push([chld.y, chld]);
}
arr.sort();
for (i = 0; i < num; i++)
{
mc.setChildIndex(arr[i][1], num-1)
}
}


честно - не проверял нифига на скорость, но может так будет хоть немного быстрее?
а то как-то у тебя выходит, что для серьезных методов объектов маловато, но несерьезные все равно тормозят =) вот еще один несерьезный... по сути немного модифицированый твой.

[mikhailk]

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

кстати, про оптимизацию, где-то проскакивало, что еще while(i--) работает быстрее, чем for(i...

[gloomyBrain]

Для 40 объектов - как могут быть тормоза? =)
Попробуйте изначально все объекты пихать в массив (при создании) - тогда Вам не нужно будет при каждой сортировке создавать новый массив из дисплей листа.

[Котяра]

вот у меня (для теста) 50 персов двигаются. При каждом движении (перерисовка по таймеру раз в 10 мс - тоже для теста, в реале можно увеличить) идёт пересчёт глубины для поменявших позицию y.
Тормоза, в принципе, заметны когда двигаются все 50, хотя не совсем ясно в чём дело: или в сортировке или в отрисовке (хотя отрисовка идёт постоянно, даже для стоящих на месте)
примерчик (1.5. Мб) (http://k0t0vich.megaforce.ru/test/flashfight/Animtest.swf)
ps: глюкает хост (временно недоступен)

[derhab]

метод в классе контейнера детей которого нужно сортировать, list - список всех объектов подлежащих сортировке...они туда сразу после добавления на сцену заносятся

public function zSort():void
{
list.sortOn('y', Array.NUMERIC);
var l:int = list.length;

while (l--) {
var o:DisplayObject = list[l] as DisplayObject;
if (getChildAt(l) != o) setChildIndex(o, l);
}
}


хотя не совсем ясно в чём дело: или в сортировке или в отрисовке
так отключи сортировку и станет ясно:)

[mikhailk]

метод в классе контейнера детей которого нужно сортировать, list - список всех объектов подлежащих сортировке...они туда сразу после добавления на сцену заносятся


ок, все работает ))
фенкс, взял это решение

[gloomyBrain]

И еще такой моментик (касается сортировки):
1) Перс должен диспатчить событие о том, что он сдвинулся.
2) Контейнер должен ловить события от всех персов.
3) (!) Если в течении одного кадра пришло хотя бы одно событие (кто-то сдвинулся) тогда сортируем и рисуем. Нет - ... ну понятно =)

То есть сортировка происходит не прямо по событию, а только раз в кадр (чаще просто незачем, а ресурсов экономится масса)

И второй момент, про отрисовку:
Есть такая штука: stage.invalidate()
Данный метод говорит FlashPlayer'у, о том, что нужно перерисовать что-то на сцене.
Для чего это нужно?
... хотел объяснить словами, но проще кодом =) Вот:

public class BitmapPanel extends Sprite {

private var _bitmap:Bitmap;
private var _width:uint;
private var _height:uint;

private var changed:Boolean; // Вот это важно

public function HeroePanel(bitmap:Bitmap, width:int = 150, height:int = 200) {

super();

this.addEventListener(Event.ADDED_TO_STAGE, onAdd);
this.addEventListener(Event.REMOVED_FROM_STAGE, onRemove);

}

public function set bitmap(bitmap:Bitmap):void {
this._bitmap = bitmap;
changed = true; // отмечаем, что нам нужно перерисоваться
if (this.stage) {
this.stage.invalidate(); // если есть возможность, запрашиваем перерисовку
}
}


public function get bitmap():Bitmap {
return this._bitmap;
}

private function onAdd(evt:Event):void {
this.addEventListener(Event.RENDER, redraw);
}

private function onRemove(evt:Event):void {
this.removeEventListener(Event.RENDER, redraw);
}

private function redraw(evt:Event):void {

if (this.changed) {
this.changed = false;
// вот тут перерисовываем все что нужно исходя из _bitmap, _width ...
//...
//...
}

}

}


Что тут происходит?
Первое - подписываемся на Event.RENDER, когда мы на сцене и отписываемся, когда нас там нет. Потому что незачем нам получать событие RENDER, если нас невидно.
Второе - если срабатывает сеттер (то есть наш внешний вид поменялся), отмечаем это в переменной changed.
Компот - перерисовка происходит только если мы на сцене и только если она нужна.
Десерт - можно добавить опцию, проверяющую, попадаем ли мы в экран (если мы на сцене), соответственно, если нет - нафиг нам перерисовываться.

Приятного аппетита =)

[Котяра]

я делал по другому (http://www.flasher.ru/forum/showpost.php?p=861876&postcount=17):
по таймеру контроллер сцены опрашивал модели персов об изменении (флаг isInvalidated) если он изменился меняем у вида перса координаты и сортируем по глубине. я намеренно ушел от схемы изменение модели вида - событие. т.к. здесь изменение модели конкретного перса влияет не только на вид перса но и на виды всех остальных персов (глубина).