|
|
« Предыдущая тема | Следующая тема » |
Опции темы | Опции просмотра |
|
|
|||||
Регистрация: Aug 2008
Адрес: Рязань
Сообщений: 723
|
Оптимизация сортировки объектов в изометрии
перелопатил много существующих изо движков, но нашел пока только один самый стабильно работающих способ сортировки (к сожалению довольно медленный: 350 элементов ~80мс)
требуется помощь в оптимизации или в подборе другого алгоритма исходные данные: - 2d объекты с известными координатами в изометрическом мире (x,y) и габаритами (width, height), а также уровнем высоты, для упрощения сортировки "слоев" - для нахождения крайних точек объектов используется класс Bounds со св-ми left=x, right=x+width, back=y, front=y+height условия: - сортировка должна происходить по изометрическим законам и текущий алгоритм: protected function sort(itemsToRender:Array):Array { //создаем копию исходного массива var list:Array = itemsToRender.slice(0); itemsToRender = []; var i:int; var j:int; var listLength:int = list.length; for (i = 0; i < listLength; i++) { //неотсортированный элемент var notSortedObj:IIsoItem = list[i] as IIsoItem; var notSortedObjBounds:Bounds = notSortedObj.bounds; var added:Boolean = false; var moLength:int = itemsToRender.length; for (j = 0; j < moLength; j++) { var sortedObj:IIsoItem = itemsToRender[j] as IIsoItem; var sortedObjBounds:Bounds = sortedObj.bounds; //если хоть одна точка notSortedObj попадает в правый верхний квадрант sortedObj, то notSortedObj лежит ниже if (notSortedObj.level == sortedObj.level && notSortedObjBounds.right > sortedObjBounds.left && notSortedObjBounds.back < sortedObjBounds.front) { itemsToRender.splice(j, 0, notSortedObj); added = true; break; }else if (notSortedObj.level < sortedObj.level) { itemsToRender.splice(j, 0, notSortedObj); added = true; break; } } //если ни одно из условий не выполнилось, то объект лежит выше всех if (!added) itemsToRender.push(notSortedObj); } list = null; //возвращает отсортированные элементы return itemsToRender; }
__________________
low + |
|
|||||
стервочка (я мужик)
|
проще поворачивать в другую сторону. тогда и координаты и рейтинг сортировки высчитывается проще.
расчёт рейтинга становится элементарным: x + y. у кого это число больше - тот ближе к экрану. принцип оптимизации сортировки тоже очень прост: составляешь массив, в котором у тебя лежат объекты с их рейтингами. индекс элемента в массиве должен соответствовать его в глубине на сцене. в этом случаи алгоритм в общем виде будет выглядеть так: /** * @private * контейнер, в котором отображается всё наше барахло */ private var _content:DisplayObjectContainer; /** * хэш, где хранятся соответствия модели их вьюхам * model -> view */ private const _elements:Dictionary = new Dictionary(); /** * @private * храним рейтинги сортировки */ private const _sortings:Vector.<uint> = new Vector.<uint>(); /** * @private * принудительно обновляет позицию вьюхи относительно модели */ private function updatePosition(data:MapElement):void { // получаем ссылку на вьюшку var view:DisplayObject = this._elements[ data ]; var x:Number = data.x; var y:Number = data.y; // изменяем координаты вьюшки view.x = ( x - y ) * COOEF_X; view.y = ( x + y ) * COOEF_Y; // получаем текущий индекс var lastIndex:uint = this._content.getChildIndex( view ); var lastRating:uint = this._sortings[ lastIndex ]; // новый рейтинг var newRating:uint = Math.round( x + y ) + COOEF_SORT; // считаем новый рейтинг сортировки // если рейтинг не изменился, то ничего не делаем if ( lastRating != newRating ) { // удаляем себя из списка this._sortings.splice( lastIndex, 1 ); // найдём куда ставить и поставим var newIndex:uint = this._sortings.length; while ( --newIndex ) { if ( this._sortings[ newIndex ] <= newRating ) break; } // вставляем новый индекс this._sortings.splice( i, 0, newRating ); this._content.setChildIndex( view, newIndex ); } } код не тестировался и набросан прямо тут, но смысл я надеюсь передал. такой метод сортировки гарантирует, что не происходит постоянного перебора всех объектов, а сравниваются только рейтинги. Последний раз редактировалось BlooDHounD; 09.04.2011 в 19:58. |
|
|||||
Регистрация: Aug 2008
Адрес: Рязань
Сообщений: 723
|
>>x + y. у кого это число больше - тот ближе у экрану
если верно понял про поворот, то при следующей ситуации возникнет ошибка - объект с индексом 2 окажется ниже объекта с индексом 3 за наводку спасибо, думал про сортировку рейтингов, попробую
__________________
low + |
|
|||||
стервочка (я мужик)
|
эта ошибка возникнет независимо от поворота. это свойство объекта данной формы.
я привёл пример z-сортировки. она работает только для точек. объёмные объекты сложной формы невозможно отсортировать корректно во всех случаях. они должны соответствовать условиям: 1. они должны быть выпуклые 2. его формы должны приближаться к кругу. если всё же необходимо отсортировать сложный объект, то придётся делать его составным. тобишь сделать из него несколько объектов соответствующих условию. p.s.: не пытайтесь сортировать объекты. сортируйте точки. Добавлено через 39 секунд ну либо пишите эвристические алгоритмы определения форм =) Добавлено через 3 минуты и да. на картинке перепутаны x и y =) |
|
|||||
буду краток
модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
|
Разбивайте объект 2 на части согласно тайлам. Общую z считайте по максимальной из z частей.
UPD. хотя если использовать формулу x+y, то и 2 и 3 имеют рейтинг 8. Надо подумать..
__________________
Отряд Котовскага Последний раз редактировалось Котяра; 09.04.2011 в 21:23. |
|
|||||
стервочка (я мужик)
|
Котяра, как ты высчитал их рейтинг не зная где находятся их центры?
|
|
|||||
буду краток
модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
|
Я же говорю, если по максимальным считать. Максимальный - это нижний угол (если принять бесконечно малый размер тайла)
__________________
Отряд Котовскага |
|
|||||
Цитата:
Пути решения: - внедрить топологический алгоритм (не лажает, вообще, даже если некоторые объекты пересекаются - остальные сортируются правильно, если впринципе можно отсортировать - сортурует) - максимум что удалось выжать - 200мс для 1000 и 1 мс для 100 объектов (сложность построения графа квадратная) - не парится и использовать бинарную вставку - лажает не намного больше, зато бдет сортировать 1000 объектов за 1-5 мс. - отказаться от прямоугольных объектов, возможно использование "почти прямоугольных": - ухищрения с разрезаниями в стиле OpenSpace P.S. Для сортировки изометрии на плоскости классической ситуации с невозможностью сортировки возникнуть не может (по-крайней мере я такую придумать не смог), даже если некоторые объекты пересекаются - остальные можно отсортировать. Цитата:
Последний раз редактировалось expl; 09.04.2011 в 22:17. |
|
|||||
стервочка (я мужик)
|
Цитата:
|
|
|||||
буду краток
модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
|
линк на тему:
http://code.google.com/p/as3isolib/s...outRenderer.as но выполнить правильную сортировку как в примере(good) всё равно не получится
__________________
Отряд Котовскага Последний раз редактировалось Котяра; 09.04.2011 в 23:32. |
Часовой пояс GMT +4, время: 11:02. |
|
« Предыдущая тема | Следующая тема » |
|
|