Оптимизация сортировки объектов в изометрии
Вложений: 1
перелопатил много существующих изо движков, но нашел пока только один самый стабильно работающих способ сортировки (к сожалению довольно медленный: 350 элементов ~80мс)
требуется помощь в оптимизации или в подборе другого алгоритма исходные данные: - 2d объекты с известными координатами в изометрическом мире (x,y) и габаритами (width, height), а также уровнем высоты, для упрощения сортировки "слоев" - для нахождения крайних точек объектов используется класс Bounds со св-ми left=x, right=x+width, back=y, front=y+height условия: - сортировка должна происходить по изометрическим законам и текущий алгоритм: http://www.flasher.ru/forum/attachme...1&d=1302341473 Код AS3:
|
проще поворачивать в другую сторону. тогда и координаты и рейтинг сортировки высчитывается проще.
расчёт рейтинга становится элементарным: x + y. у кого это число больше - тот ближе к экрану. принцип оптимизации сортировки тоже очень прост: составляешь массив, в котором у тебя лежат объекты с их рейтингами. индекс элемента в массиве должен соответствовать его в глубине на сцене. в этом случаи алгоритм в общем виде будет выглядеть так: Код AS3:
код не тестировался и набросан прямо тут, но смысл я надеюсь передал. такой метод сортировки гарантирует, что не происходит постоянного перебора всех объектов, а сравниваются только рейтинги. |
Вложений: 1
>>x + y. у кого это число больше - тот ближе у экрану
если верно понял про поворот, то при следующей ситуации возникнет ошибка - объект с индексом 2 окажется ниже объекта с индексом 3 за наводку спасибо, думал про сортировку рейтингов, попробую |
эта ошибка возникнет независимо от поворота. это свойство объекта данной формы.
я привёл пример z-сортировки. она работает только для точек. объёмные объекты сложной формы невозможно отсортировать корректно во всех случаях. они должны соответствовать условиям: 1. они должны быть выпуклые 2. его формы должны приближаться к кругу. если всё же необходимо отсортировать сложный объект, то придётся делать его составным. тобишь сделать из него несколько объектов соответствующих условию. p.s.: не пытайтесь сортировать объекты. сортируйте точки. Добавлено через 39 секунд ну либо пишите эвристические алгоритмы определения форм =) Добавлено через 3 минуты и да. на картинке перепутаны x и y =) |
Разбивайте объект 2 на части согласно тайлам. Общую z считайте по максимальной из z частей.
UPD. хотя если использовать формулу x+y, то и 2 и 3 имеют рейтинг 8. Надо подумать.. |
Котяра, как ты высчитал их рейтинг не зная где находятся их центры?
|
Я же говорю, если по максимальным считать. Максимальный - это нижний угол (если принять бесконечно малый размер тайла)
|
Вложений: 1
Цитата:
Пути решения: - внедрить топологический алгоритм (не лажает, вообще, даже если некоторые объекты пересекаются - остальные сортируются правильно, если впринципе можно отсортировать - сортурует) - максимум что удалось выжать - 200мс для 1000 и 1 мс для 100 объектов (сложность построения графа квадратная) - не парится и использовать бинарную вставку - лажает не намного больше, зато бдет сортировать 1000 объектов за 1-5 мс. - отказаться от прямоугольных объектов, возможно использование "почти прямоугольных": Вложение 26418 - ухищрения с разрезаниями в стиле OpenSpace P.S. Для сортировки изометрии на плоскости классической ситуации с невозможностью сортировки возникнуть не может (по-крайней мере я такую придумать не смог), даже если некоторые объекты пересекаются - остальные можно отсортировать. Цитата:
|
Цитата:
|
линк на тему:
http://code.google.com/p/as3isolib/s...outRenderer.as но выполнить правильную сортировку как в примере(good) всё равно не получится http://members.gamedev.net/osan/images/boxes.gif |
Часовой пояс GMT +4, время: 15:57. |
Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.