|
|
« Предыдущая тема | Следующая тема » |
Опции темы | Опции просмотра |
|
|
|||||
Регистрация: Nov 2009
Адрес: СПб
Сообщений: 2,236
|
Я у себя решил проблему сортировки объектов привязкой их к тайлам. Т.е., геометрические размеры фигуры не имеют значения и не учитываются. С фигурами, стоящими на одном тайле, этот подход, естественно, работает железно. Со сложными фигурами - приходится либо разбивать на части (иногда это все равно надо делать, например, для арок, в которые проходит перс), либо так подгонять их точки привязки и так строить локации, чтобы все вставало правильно.
Кстати, когда я предложил команде на выбор - делить сложные фигуры на однотайловые или аккуратно строить локации - был спокойно выбран второй вариант, дизайнеры обкатались на одной локации и теперь они лепят их как пирожки. Это я к тому, что мы иногда решаем задачи более сложные, нежели требуется на самом деле. |
|
|||||
стервочка (я мужик)
|
mikhailk, собственно я об этом с самого начала и говорил.
|
|
|||||
Цитата:
- на плоскости такого не бывает. - приведенный в топике алгоритм лажает даже в его отсутствие. Цитата:
В альтернативном варианте можно заменить поиск ближайшего индекса на бинарный поиск, не всегда надо, но все-таки: плюсы: гарантированное время n*log n при загрузке карты минусы: Если перемещающихся больше чем стоящих на месте - log(n) это больше чем найти ближайший индекс за 1-2 шага (они ж не далеко за шаг уходят) Зато, если бинарную вставку не использовать подморозим флешку алгоритмом со сложностью n * n при загрузке карты. Последний раз редактировалось expl; 10.04.2011 в 00:01. |
|
|||||
стервочка (я мужик)
|
Цитата:
Добавлено через 1 минуту и заодно расскажите чем мы подморозим флэшку моим алгоритмом? |
|
|||||
Более формально:
"Для любого количества объектов в виде прямогольных параллелепипедов любых размеров, если 1. они не пересекаются физически 2. нижней частью лежат на одной плоскости всегда можно найти такой порядок отображения, при котором они будут правильно выглядеть в изометрической проекции" (здесь речь не о конкретном алгоритме, а о принципиальной возможности) Уверен на 95% Цитата:
ложим 1-й - ищем ему место среди 0 объектов, ложим 2-й - ищем ему место среди 1 объекта, ... ложим n-1 -й - ищем ему место среди n-2 объектов ложим n-й - ищем ему место среди n-1 объектов Т.к. объекты добавляются в неотсортированном порядке - то поиск ближайшего объекта будет пропорционален n уже существущих Т.е. общаяя сложность пропорциональна n*n. Что-то типа сортировки пузырьком получается. А когда объекты уже отсортированы и на каждом шаге их относительное положение меняется несильно - новый индекс находится быстро. Просто на старте пик будет. Нет, не совсем так, у Вас поиск идет, насколько понял, не от текущего индекса элемента, а от начала. Т.е. в любом случае сложность квадратная. Экономия достигается только за счет НЕсортировки неподвижных объектов. Последний раз редактировалось expl; 10.04.2011 в 01:27. |
|
|||||
стервочка (я мужик)
|
вы скажите сколько объектов должно быть, что на старте из-за моего алгоритма всё залипло. я могу гарантировать, что на 1К объектов всё залипнет не из-за сортировки, а из-за добавления на сцену большого количество графики.
я алгоритм писал прямо тут. вы ж понимаете, что вставить один иф, для ограниченного поиска при перемещении - дело 1 минуты? и да скорость достигается за счёт того, что статика не изменяет своих рейтингов. Добавлено через 9 минут Цитата:
Последний раз редактировалось BlooDHounD; 10.04.2011 в 13:49. |
|
|||||
Цитата:
А я и не говорю что Ваш алгоритм нежизнеспособен - я подобный много где видел и он отлично справлялся. Просто есть альтернативное решение - бинарный поиск (которому вообще плевать на состояние на карте - он всегда выдает стабильное время), только и всего. Цитата:
Всмысле зашить порядок стены и дерева в локацию? Ну не знаю. Если игра типа "город" - там пользователь сам распологает изометрические объекты и ему поставить их "неудобно для примитивной сортировки" не запретишь. Последний раз редактировалось expl; 10.04.2011 в 14:14. |
|
|||||
стервочка (я мужик)
|
Цитата:
Цитата:
|
|
|||||
Цитата:
Короче, +1 в пользу простого поиска. Цитата:
Но я понял, что вы хотели скзать, честная сортировка с учетом размеров с этим кустом и деревом ничего хорошего не сделает. Еще эта честная сортировка с такой производительностью практически не применима (100-200 сортируемых объектов - это мало даже для социалок) Похоже все, кому нужны прямоугольные объекты, юзают какие-то хаки, потому что не смог найти ни одного НЕлажащего алгоритма, даже сортировка из книги ActionScript for Multiplayer Games and Virtual Worlds ошибается на достаточно простых ситуациях. |
|
|||||
Регистрация: Nov 2009
Адрес: СПб
Сообщений: 2,236
|
Я так понимаю, надо все-таки определиться, какая задача решается. Задача сортировки объектов для социалки типа "город", на мой взгляд, элементарная, поскольку объекты-здания стационарные, а движущиеся объекты типа людей-машинок - мелкие и не отягощенные анимацией. Такую задачу вполне можно решить в общем виде.
Ходилка-бродилка в лесу с разномасштабными анимированными кустами-деревьями для перса со сложной анимацией (например, он берет в руки предметы разного размера), который встречает таких же анимированных NPC - это качественно другая задача. Класть жизнь на ее решение в общем виде, наверное, не совсем разумно. Проще решить конфликтные ситуации во время сборки локаций - расставить объекты так, чтобы они не мешали друг другу и запретить персу ходить туда, где ему ходить незачем. |
Часовой пояс GMT +4, время: 14:23. |
|
« Предыдущая тема | Следующая тема » |
Опции темы | |
Опции просмотра | |
|
|