Наиболее оптимальная Y сортировка

[goodguy]

Решил перейти в своей игре с виду сверху на вид под углом 45 градусов, почти как в изометрии, но тут сразу же уперся в необходимость Y-сортировки. Вся фишка в том, что объектов у меня целая куча, как разных деревьев и домов, так и персонажей, а учитывая то, что игра работает на Box2D, да еще и Union, который тоже проводит огромное количество расчетов, покадровая сортировка массива объектов простым способом sortOn("y", Array.NUMERIC) мне представляется не самой лучшей идеей.
Но есть ли что-то лучше? Или мне прийдется "изобретать велосипед"?

[Zebestov]

Вектор, к слову, сортируется существенно быстрее массива.

[goodguy]

Только что мне даст вектор? Мне нужно сортировать разные типы объектов.
Хотя.. если попробовать добавлять их как DisplayObject.
Но в этом случае прийдется приводить все к типу DisplayObject, так как если верить справке адоби

Переменная, объявленная вместе с экземпляром вектора.Тип данных <T> может хранить экземпляр Vector только в том случае, если он создан с идентичным базовым типом T. Например, вектор, созданный путем вызова методаnew Vector.<String>() нельзя присвоить переменной, которая объявлена вместе с ним.Тип данных <int>. Базовые типы должны быть полностью идентичны. Например, следующий код не компилируется, поскольку базовый тип объекта отличается от базового типа, объявленного для переменной (несмотря на то, что Sprite — подкласс класса DisplayObject):

 // This code doesn't compile even though Sprite is a DisplayObject subclass
 var v:Vector.<DisplayObject> = new Vector.<Sprite>();

Боюсь это сведет на нет всю экономию в скорости

[Zebestov]

Можно создать объект с полями id и y (к примеру) и работать с ним при сортировке.

[goodguy]

Это все равно будет отжирать много ресурсов. Нужно же еще индексы всех этих объектов менять в контейнере. А карты там есть огромные.
Думаю нужно написать код, который позволит сортироваться только тем объектам, которые находятся в видимом поле, а остальные хранить в отдельном массиве. Не знаю, на сколько это будет эффективно, надо попробовать

[Zebestov]

Может я недостаточно вник, но насколько велика нагрузка от следующего алгоритма:

1. создать новый вектор
2. внести в него id и y видимых объектов (как я написал выше)
3. отсортировать вектор по y

Нормальный fps должен проглотить эту схему только так.

[goodguy]

3. отсортировать вектор по y

Зачем мне это?

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

[surlac]

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

Вектор, к слову, сортируется существенно быстрее массива.

Я так понимаю, Вы говорите о сортировке примитивных типов?

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

Только что мне даст вектор?
Мне нужно сортировать разные типы объектов. Хотя.. если попробовать добавлять их как DisplayObject.

Ничего не даст, т.к. Vector сортирует объекты не быстрее, чем Array.

И еще, раз уж тема об оптимальной сортировке: подскажите, каким алгоритмом Vector сортирует свои элементы? Возможно иной раз эффективнее самому реализовать например quicksort для сортировки, чем пользоваться "зашитым" алгоритмом.

[Zebestov]

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

Я так понимаю, Вы говорите о сортировке примитивных типов?

Я сортировал вектор массивов с двумя элементами z:Number и item:SomeClass. Скорость была существенно выше сортировки массива.

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

подскажите, каким алгоритмом Vector сортирует свои элементы? Возможно иной раз эффективнее самому реализовать например quicksort для сортировки, чем пользоваться "зашитым" алгоритмом.

У класса Vector как раз нет алгоритма сортировки. Его нужно описать самостоятельно и передать в sort().

[silin]

могу и ошибаться, просто собственные ощущения:
когда ковырял подобную тему, пришел к выводу, что время на саму сортировку не столь важно, потому как затраты на перемещение отсортированных объектов в дисплейлисте все равно все перекрывают
к слову, для сортировки остановился на http://artman.fi/2009/06/as3-sorting...ative-sorting/ , модифицировав его под сортировку по полю объекта