|
|
|||||
Сортировка дисплей объектов
Необходимо сортировать дисплей объекты по оси y в реальном времени так, чтобы чем ниже был объект, тем выше он бы был в дисплей листе.
Сложность заключается в том, что объекты имеющие одинаковую координату y, находящиеся рядом друг с другом - периодически перекрывают себя, то один то другой выходит на более верхний уровень отображения чем его сосед. Сортировка по одной только оси y не подходит. Перед тем как думать над более сложным алгоритмом, может, кто-то уже делал такое или знает как проще?
__________________
Дети не должны знать о своих родителях |
|
|||||
sortvalue = y * 10000 + x
вместо икса ширину можно, а вместо 10k любое значение исключающее повторы |
|
|||||
Да, на ум ток координата x приходит, как наиболее адекватное уникальное значение. Кому интересно, вот итоговый класс для сортировки:
package mvc.view.map { import flash.display.DisplayObject; import flash.display.DisplayObjectContainer; /** * Сортировщик дисплей объектов по оси y. * Чем выше координата y тем ниже в списке отображения объект. * * @author Tails */ public class Sorter{ // Приват private var _contaner:DisplayObjectContainer; public function Sorter() { } // ГЕТТЕР-СЕТТЕРЫ /** Контейнер сортируемых объектов. **/ public function get sorterContaner():DisplayObjectContainer { return _contaner; } public function set sorterContaner(value:DisplayObjectContainer):void { _contaner = value; } // ПАБЛИК /** Сортировать объекты. **/ public function sort():void { if (!_contaner) throw new Error(this + ' Сортировочный контейнер не выбран.'); var length:uint = _contaner.numChildren; if(length > 1) qSort(_contaner, 0, length - 1); } /** * Алгоритм быстрой сортировкки. * http://ru.wikipedia.org/wiki/%D0%91%...B2%D0%BA%D0%B0 */ private function qSort(a:DisplayObjectContainer, low:int, high:int):void { var i:int = low; var j:int = high; var child:DisplayObject = a.getChildAt(int((low + high) / 2)); var x:Number = child.y + child.x * 0.00001; // x - опорный элемент посредине между low и high do { while(a.getChildAt(i).y + a.getChildAt(i).x * 0.00001 < x) ++i; // поиск элемента для переноса в старшую часть while(a.getChildAt(j).y + a.getChildAt(j).x * 0.00001 > x) --j; // поиск элемента для переноса в младшую часть if(i <= j){ // обмен элементов местами: a.swapChildrenAt(i, j); // переход к следующим элементам: i++; j--; } } while(i < j); if(low < j) qSort(a, low, j); if(i < high) qSort(a, i, high); } } }
__________________
Дети не должны знать о своих родителях |
|
|||||
Если модуль разницы y-координат контейнеров меньше некого минимума - не предпринимаю никаких действий, а к x - координате привязываю порядок чтения контейнеров
|
|
|||||
Tails, попробуй связный список а не сортировку. То есть вместо того чтобы сортировать ВСЕ объекты, можно лишь двигать те, что поменяли координаты. Быстрее во много раз. Идеально для твоего случая.
__________________
...вселенская грусть |
|
|||||
Регистрация: Nov 2009
Адрес: СПб
Сообщений: 2,236
|
Цитата:
По сабжу - я тоже при сортировке по y дополнительно использовал значение x, чтобы исключить неоднозначность ситуации, когда рядом стоят два объекта с одним y. |
|
|||||
gloomyBrain,
В таком случае, мы сможем сэкономить только на формирований некого списка для порядка вывода статических объектов на экран. Всё равно придётся дёргать статичные дисплей объекты в контейнере при выводе списка динамических и статических объектов. Сперва я что-то такое хотел сделать. Способ с сортировкой кажется более простым и возможно более быстрым, так-как перебираются объекты довольно быстро, а свапаются только изменившие координаты. В целях оптимизаций, если понадобиться, можно сделать сортировку только объектов на экране. Всё познаётся в сравнений, если у кого-то есть другой реализованный способ сортировки, можно было-бы сравнить результаты тестов
__________________
Дети не должны знать о своих родителях |
|
|||||
Цитата:
1) объект поменял координаты -> заносим его в список апдейтов 2) раз в кадр проходим по всему списку объектов 3) Для каждого объекта в списке - вычисляем индекс глубины заново - сравниваем свой индекс с индексом соседа "сверху" - если у соседа индекс такой, что он должен быть "снизу", спрашиваем следующего - повторяем до тех пор, пока список "вверх" не заканчивается или пока не находим того, кто точно должен быть "сверху" от нас после апдейта ... то же самое "вниз" если нужно ... setChildIndex перемещает только один объект Стоит учесть, что на практике объекты не прыгают через всю карту, а значит количество шагов вверх или вниз всегда небольшое. Вычислений реально мало. Количество объектов на экране вообще значения не имеет (в отличие от quickSort), важно только сколько из них передвинулось. Вру конечно про "не имеет", но можно пренебречь, когда попробуете сами увидите. Это называется сортировка вставками и на данных, которые уже отсортированы она показывает офигитительные результаты, смотрите сами: http://www.sorting-algorithms.com/
__________________
...вселенская грусть |
|
|||||
Регистрация: Nov 2009
Адрес: СПб
Сообщений: 2,236
|
Цитата:
Я уж думал, откровение какое свершилось. |
Часовой пояс GMT +4, время: 19:38. |
|
« Предыдущая тема | Следующая тема » |
Опции темы | |
Опции просмотра | |
|
|