Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 09.04.2011, 14:33
Jewelz вне форума Посмотреть профиль Отправить личное сообщение для Jewelz Найти все сообщения от Jewelz
  № 1  
Ответить с цитированием
Jewelz
 
Аватар для Jewelz

Регистрация: Aug 2008
Адрес: Рязань
Сообщений: 723
По умолчанию Оптимизация сортировки объектов в изометрии

перелопатил много существующих изо движков, но нашел пока только один самый стабильно работающих способ сортировки (к сожалению довольно медленный: 350 элементов ~80мс)

требуется помощь в оптимизации или в подборе другого алгоритма

исходные данные:
- 2d объекты с известными координатами в изометрическом мире (x,y) и габаритами (width, height), а также уровнем высоты, для упрощения сортировки "слоев"
- для нахождения крайних точек объектов используется класс Bounds со св-ми left=x, right=x+width, back=y, front=y+height

условия:
- сортировка должна происходить по изометрическим законам

и текущий алгоритм:

Код AS3:
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 +

Старый 09.04.2011, 18:05
BlooDHounD вне форума Посмотреть профиль Отправить личное сообщение для BlooDHounD Посетить домашнюю страницу BlooDHounD Найти все сообщения от BlooDHounD
  № 2  
Ответить с цитированием
BlooDHounD
стервочка (я мужик)
 
Аватар для BlooDHounD

блогер
Регистрация: Mar 2004
Адрес: Борисов
Сообщений: 3,161
Записей в блоге: 22
проще поворачивать в другую сторону. тогда и координаты и рейтинг сортировки высчитывается проще.
расчёт рейтинга становится элементарным: x + y. у кого это число больше - тот ближе к экрану. принцип оптимизации сортировки тоже очень прост: составляешь массив, в котором у тебя лежат объекты с их рейтингами. индекс элемента в массиве должен соответствовать его в глубине на сцене. в этом случаи алгоритм в общем виде будет выглядеть так:
Код AS3:
/**
 * @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 );
	}
 
}
Добавлено через 1 минуту
код не тестировался и набросан прямо тут, но смысл я надеюсь передал. такой метод сортировки гарантирует, что не происходит постоянного перебора всех объектов, а сравниваются только рейтинги.


Последний раз редактировалось BlooDHounD; 09.04.2011 в 19:58.
Старый 09.04.2011, 18:24
Jewelz вне форума Посмотреть профиль Отправить личное сообщение для Jewelz Найти все сообщения от Jewelz
  № 3  
Ответить с цитированием
Jewelz
 
Аватар для Jewelz

Регистрация: Aug 2008
Адрес: Рязань
Сообщений: 723
>>x + y. у кого это число больше - тот ближе у экрану
если верно понял про поворот, то при следующей ситуации возникнет ошибка - объект с индексом 2 окажется ниже объекта с индексом 3

за наводку спасибо, думал про сортировку рейтингов, попробую
Изображения
 
__________________
low +

Старый 09.04.2011, 19:55
BlooDHounD вне форума Посмотреть профиль Отправить личное сообщение для BlooDHounD Посетить домашнюю страницу BlooDHounD Найти все сообщения от BlooDHounD
  № 4  
Ответить с цитированием
BlooDHounD
стервочка (я мужик)
 
Аватар для BlooDHounD

блогер
Регистрация: Mar 2004
Адрес: Борисов
Сообщений: 3,161
Записей в блоге: 22
эта ошибка возникнет независимо от поворота. это свойство объекта данной формы.
я привёл пример z-сортировки. она работает только для точек. объёмные объекты сложной формы невозможно отсортировать корректно во всех случаях. они должны соответствовать условиям:
1. они должны быть выпуклые
2. его формы должны приближаться к кругу.

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

p.s.: не пытайтесь сортировать объекты. сортируйте точки.

Добавлено через 39 секунд
ну либо пишите эвристические алгоритмы определения форм =)

Добавлено через 3 минуты
и да. на картинке перепутаны x и y =)

Старый 09.04.2011, 21:17
Котяра вне форума Посмотреть профиль Отправить личное сообщение для Котяра Посетить домашнюю страницу Котяра Найти все сообщения от Котяра
  № 5  
Ответить с цитированием
Котяра
буду краток
 
Аватар для Котяра

модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
Отправить сообщение для Котяра с помощью ICQ Отправить сообщение для Котяра с помощью Skype™
Разбивайте объект 2 на части согласно тайлам. Общую z считайте по максимальной из z частей.
UPD. хотя если использовать формулу x+y, то и 2 и 3 имеют рейтинг 8.
Надо подумать..
__________________
Отряд Котовскага


Последний раз редактировалось Котяра; 09.04.2011 в 21:23.
Старый 09.04.2011, 21:32
BlooDHounD вне форума Посмотреть профиль Отправить личное сообщение для BlooDHounD Посетить домашнюю страницу BlooDHounD Найти все сообщения от BlooDHounD
  № 6  
Ответить с цитированием
BlooDHounD
стервочка (я мужик)
 
Аватар для BlooDHounD

блогер
Регистрация: Mar 2004
Адрес: Борисов
Сообщений: 3,161
Записей в блоге: 22
Котяра, как ты высчитал их рейтинг не зная где находятся их центры?

Старый 09.04.2011, 21:52
Котяра вне форума Посмотреть профиль Отправить личное сообщение для Котяра Посетить домашнюю страницу Котяра Найти все сообщения от Котяра
  № 7  
Ответить с цитированием
Котяра
буду краток
 
Аватар для Котяра

модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
Отправить сообщение для Котяра с помощью ICQ Отправить сообщение для Котяра с помощью Skype™
Я же говорю, если по максимальным считать. Максимальный - это нижний угол (если принять бесконечно малый размер тайла)
__________________
Отряд Котовскага

Старый 09.04.2011, 21:57
expl вне форума Посмотреть профиль Отправить личное сообщение для expl Найти все сообщения от expl
  № 8  
Ответить с цитированием
expl

блогер
Регистрация: Feb 2006
Сообщений: 1,474
Записей в блоге: 3
Цитата:
но нашел пока только один самый стабильно работающих способ сортировки
Спешу обрадовать - этот подход будет лажать для многих случаев (не считая классический, который впринципе невозможно отсортировать)

Пути решения:
- внедрить топологический алгоритм (не лажает, вообще, даже если некоторые объекты пересекаются - остальные сортируются правильно, если впринципе можно отсортировать - сортурует) - максимум что удалось выжать - 200мс для 1000 и 1 мс для 100 объектов (сложность построения графа квадратная)
- не парится и использовать бинарную вставку - лажает не намного больше, зато бдет сортировать 1000 объектов за 1-5 мс.
- отказаться от прямоугольных объектов, возможно использование "почти прямоугольных":
Название: object.jpg
Просмотров: 613

Размер: 8.6 Кб
- ухищрения с разрезаниями в стиле OpenSpace

P.S. Для сортировки изометрии на плоскости классической ситуации с невозможностью сортировки возникнуть не может (по-крайней мере я такую придумать не смог), даже если некоторые объекты пересекаются - остальные можно отсортировать.

Цитата:
p.s.: не пытайтесь сортировать объекты. сортируйте точки.
Эх, если бы это прокатывало для прямоугольников, а тем более для параллелепипедов.


Последний раз редактировалось expl; 09.04.2011 в 22:17.
Старый 09.04.2011, 23:03
BlooDHounD вне форума Посмотреть профиль Отправить личное сообщение для BlooDHounD Посетить домашнюю страницу BlooDHounD Найти все сообщения от BlooDHounD
  № 9  
Ответить с цитированием
BlooDHounD
стервочка (я мужик)
 
Аватар для BlooDHounD

блогер
Регистрация: Mar 2004
Адрес: Борисов
Сообщений: 3,161
Записей в блоге: 22
Цитата:
Эх, если бы это прокатывало для прямоугольников, а тем более для параллелепипедов.
см. ограничения.

Старый 09.04.2011, 23:17
Котяра вне форума Посмотреть профиль Отправить личное сообщение для Котяра Посетить домашнюю страницу Котяра Найти все сообщения от Котяра
  № 10  
Ответить с цитированием
Котяра
буду краток
 
Аватар для Котяра

модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
Отправить сообщение для Котяра с помощью ICQ Отправить сообщение для Котяра с помощью Skype™
линк на тему:
http://code.google.com/p/as3isolib/s...outRenderer.as
но выполнить правильную сортировку как в примере(good)
всё равно не получится
__________________
Отряд Котовскага


Последний раз редактировалось Котяра; 09.04.2011 в 23:32.
Создать новую тему Ответ Часовой пояс GMT +4, время: 15:38.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 15:38.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.