Оптимизация сортировки объектов в изометрии

[mikhailk]

Я у себя решил проблему сортировки объектов привязкой их к тайлам. Т.е., геометрические размеры фигуры не имеют значения и не учитываются. С фигурами, стоящими на одном тайле, этот подход, естественно, работает железно. Со сложными фигурами - приходится либо разбивать на части (иногда это все равно надо делать, например, для арок, в которые проходит перс), либо так подгонять их точки привязки и так строить локации, чтобы все вставало правильно.

Кстати, когда я предложил команде на выбор - делить сложные фигуры на однотайловые или аккуратно строить локации - был спокойно выбран второй вариант, дизайнеры обкатались на одной локации и теперь они лепят их как пирожки.

Это я к тому, что мы иногда решаем задачи более сложные, нежели требуется на самом деле.

[BlooDHounD]

mikhailk, собственно я об этом с самого начала и говорил.

[expl]

Сообщение от Котяра

линк на тему:
http://code.google.com/p/as3isolib/s...outRenderer.as
но выполнить правильную сортировку как в примере(good)
всё равно не получится

Ага, это тот классический случай, который нельзя отсортировать, но:
- на плоскости такого не бывает.
- приведенный в топике алгоритм лажает даже в его отсутствие.

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

Ну да, ну да.
В альтернативном варианте можно заменить поиск ближайшего индекса на бинарный поиск, не всегда надо, но все-таки:
плюсы: гарантированное время n*log n при загрузке карты
минусы: Если перемещающихся больше чем стоящих на месте - log(n) это больше чем найти ближайший индекс за 1-2 шага (они ж не далеко за шаг уходят)
Зато, если бинарную вставку не использовать подморозим флешку алгоритмом со сложностью n * n при загрузке карты.

[BlooDHounD]

- на плоскости такого не бывает.

расскажите это дереву и стене.

Добавлено через 1 минуту
и заодно расскажите чем мы подморозим флэшку моим алгоритмом?

[expl]

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

расскажите это дереву и стене.

Более формально:
"Для любого количества объектов в виде прямогольных параллелепипедов любых размеров, если
1. они не пересекаются физически
2. нижней частью лежат на одной плоскости
всегда можно найти такой порядок отображения, при котором они будут правильно выглядеть в изометрической проекции"
(здесь речь не о конкретном алгоритме, а о принципиальной возможности)
Уверен на 95%

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

Добавлено через 1 минуту
и заодно расскажите чем мы подморозим флэшку моим алгоритмом?

допустим загружаем 1000 объектов
ложим 1-й - ищем ему место среди 0 объектов,
ложим 2-й - ищем ему место среди 1 объекта,
...
ложим n-1 -й - ищем ему место среди n-2 объектов
ложим n-й - ищем ему место среди n-1 объектов
Т.к. объекты добавляются в неотсортированном порядке - то поиск ближайшего объекта будет пропорционален n уже существущих
Т.е. общаяя сложность пропорциональна n*n. Что-то типа сортировки пузырьком получается.

А когда объекты уже отсортированы и на каждом шаге их относительное положение меняется несильно - новый индекс находится быстро. Просто на старте пик будет.

Нет, не совсем так, у Вас поиск идет, насколько понял, не от текущего индекса элемента, а от начала. Т.е. в любом случае сложность квадратная. Экономия достигается только за счет НЕсортировки неподвижных объектов.

[BlooDHounD]

вы скажите сколько объектов должно быть, что на старте из-за моего алгоритма всё залипло. я могу гарантировать, что на 1К объектов всё залипнет не из-за сортировки, а из-за добавления на сцену большого количество графики.

я алгоритм писал прямо тут. вы ж понимаете, что вставить один иф, для ограниченного поиска при перемещении - дело 1 минуты?
и да скорость достигается за счёт того, что статика не изменяет своих рейтингов.

Добавлено через 9 минут

"Для любого количества объектов в виде прямогольных параллелепипедов любых размеров, если
1. они не пересекаются физически
2. нижней частью лежат на одной плоскости

другой алгоритм с другими ограничениями. просто 99% случаев не нужны эти самые ограничения. чаще нужно нарисовать дерево и стену. уверен на 100%.

[expl]

вы скажите сколько объектов должно быть, что на старте из-за моего алгоритма всё залипло. я могу гарантировать, что на 1К объектов всё залипнет не из-за сортировки, а из-за добавления на сцену большого количество графики.

я алгоритм писал прямо тут. вы ж понимаете, что вставить один иф, для ограниченного поиска при перемещении - дело 1 минуты?
и да скорость достигается за счёт того, что статика не изменяет своих рейтингов.

Да, если вставить этот иф он может и уделать в нормальном режиме бинарный поиск.
А я и не говорю что Ваш алгоритм нежизнеспособен - я подобный много где видел и он отлично справлялся. Просто есть альтернативное решение - бинарный поиск (которому вообще плевать на состояние на карте - он всегда выдает стабильное время), только и всего.

другой алгоритм с другими ограничениями. просто 99% случаев не нужны эти самые ограничения. чаще нужно нарисовать дерево и стену. уверен на 100%.

Не совсем фразу понял.
Всмысле зашить порядок стены и дерева в локацию? Ну не знаю.
Если игра типа "город" - там пользователь сам распологает изометрические объекты и ему поставить их "неудобно для примитивной сортировки" не запретишь.

[BlooDHounD]

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

Да, если вставить этот иф он может и уделать в нормальном режиме бинарный поиск.

бинарный поиск - это очень абстрактное понятие. вы имеете ввиду оставить мою систему с рейтингами и изменить алгоритм поиска в массиве? просто если так, то бинарный поиск будет периодически спотыкаться на элементах с одинаковым рейтингом. и будем наблюдать моргающие объекты. да и с двигающемся персонажем, где индекс меняется +/-5 на 1К элементов, это совершенно излишне.

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

Всмысле зашить порядок стены и дерева в локацию?

в смысле: "все объекты не пересекающиеся прямоугольники" - это сильное ограничение, это значит, что в рядом с размашистом деревом нельзя ставить куст.

[expl]

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

бинарный поиск - это очень абстрактное понятие. вы имеете ввиду оставить мою систему с рейтингами и изменить алгоритм поиска в массиве? просто если так, то бинарный поиск будет периодически спотыкаться на элементах с одинаковым рейтингом. и будем наблюдать моргающие объекты. да и с двигающемся персонажем, где индекс меняется +/-5 на 1К элементов, это совершенно излишне.

Именно поиск в массиве и имею ввиду. Проблема когда перс стоит на кусте и мигает действиельно существует - решается дополнительными приоритетами сортировки, кроме координаты.
Короче, +1 в пользу простого поиска.

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

в смысле: "все объекты не пересекающиеся прямоугольники" - это сильное ограничение, это значит, что в рядом с размашистом деревом нельзя ставить куст.

А если пареллелепипеды пересекающиеся - то впринципе не врезав их один в другой нормально отобразить в _общем_ случае не получиться.

Но я понял, что вы хотели скзать, честная сортировка с учетом размеров с этим кустом и деревом ничего хорошего не сделает.

Еще эта честная сортировка с такой производительностью практически не применима (100-200 сортируемых объектов - это мало даже для социалок)
Похоже все, кому нужны прямоугольные объекты, юзают какие-то хаки, потому что не смог найти ни одного НЕлажащего алгоритма, даже сортировка из книги ActionScript for Multiplayer Games and Virtual Worlds ошибается на достаточно простых ситуациях.

[mikhailk]

Я так понимаю, надо все-таки определиться, какая задача решается. Задача сортировки объектов для социалки типа "город", на мой взгляд, элементарная, поскольку объекты-здания стационарные, а движущиеся объекты типа людей-машинок - мелкие и не отягощенные анимацией. Такую задачу вполне можно решить в общем виде.

Ходилка-бродилка в лесу с разномасштабными анимированными кустами-деревьями для перса со сложной анимацией (например, он берет в руки предметы разного размера), который встречает таких же анимированных NPC - это качественно другая задача. Класть жизнь на ее решение в общем виде, наверное, не совсем разумно. Проще решить конфликтные ситуации во время сборки локаций - расставить объекты так, чтобы они не мешали друг другу и запретить персу ходить туда, где ему ходить незачем.