Алгоритм z-сортировки объектов

[Maestro13]

Всем доброго времени суток!

Подскажите, возможно ли реализовать алгоритм z-сортировки объектов в изометрическом поле, если объект занимает более одной клетки на поле. Целый день промучился, так и не смог сделать! Помогите с решением!

[iflamberg]

проще всего разрезать на несколько клеток.

[lowka]

Либо за каждым объектом делать область из нескольких непроходимых клеток. В этом случае резать ничего не придется.

[iflamberg]

2lowka: ты нее понял суть проблемы. Проблема в правильной сортировке объектов - какой объект какой заслоняет.

[Maestro13]

В google искал, ничего подобного найти не смог... Разрезать на несколько клеток конечно можно, но хотелось бы все-таки сделать без разрезания(если это возможно)

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

[lowka]

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

2lowka: ты нее понял суть проблемы. Проблема в правильной сортировке объектов - какой объект какой заслоняет.

Понял. Но так как в первом сообщении все очень скупо(нет никаких ограничений - а они нужны т.к. зачем тратить время на реализацию ИЗЛИШНЕГО функционала) предложил мой вариант. Если прибегнуть к тому, что я написал не нужно резать объекты, и сортировка будет работать простейшая по (x+y) - правда этот метод работает в случае, если размер подвижных объектов 1 клетка, а для статических сколько угодно.

[expl]

если это возможно

Это точно возможно для параллельно стоящих параллелепипедов, даже c произвольными размерами без сетки.
Вопрос в том, сколько на это уйдет времени процессора.

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

Как-то смутно представяется работа этого алгоритма, напишите если прокатит.

Я делал по другому:
- пишем функцию сравнения 2-х объектов
в данном случае она выдает 3 результата - "1-й перед 2-м", "2-й перед первым", "не_известно". В этой функции придется учитывать не только координаты, но и размеры объектов
- сортируем пузырьком - почему-то только этот метод работал
но вместо сравнения используем эту функцию, если возвращает "не_знаю" - просто ничего с объектами не делаем - идем дальше.
Все.

Еще есть способы:

- Трюки с точками привязки изображений объектов (не работает для длинных и низких объектов)
http://www.openspace-engine.com/

- Глава "SortingAlgoritm" из книги "ActionScript for Multiplayer Games and Virtual Worlds" (сам не проверял)

P.S. Ну и если будут сильные траблы, на худой конец можно все порезать на кусочки или понаделать непроходимых областей за сложными объектами
P.S.2. Если все объекты имеют квадратную форму(1x1, 2x2, 3x3), то можно сортировать чисто по z-координате центра - все будет работать

[lowka]

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

В google искал, ничего подобного найти не смог... Разрезать на несколько клеток конечно можно, но хотелось бы все-таки сделать без разрезания(если это возможно)

Хотите, что все было честно*? Если да, то
- в случае, когда вывод спрайтами, то только резать.
- если не резать, только вывод в битмап - очень геморный алгоритм. когда искал решение этой же задачи нашел его на каком-то XNA форуме, но оно того не стоит, поверьте.

* - Т.е. все объекты полностью перекрывают друг друга, а оно вам точно надо? Просто везде где это есть - перекрытые объекты либо рисуются еще раз поверх всего, но с пропуском 1 пикселя (baldur's gate, icewind dale и др.) или во круг главного объекта "стираются" заслоняющее его объекты (fallout).

Если вам нужно общее решение - то только резать. А если нет, то нужны дополнительные данные т.е. какие объекты могут занимать больше 1 клетки и проч. ? это действительно важно.

[iflamberg]

не обязательно физически разрерать. Нужно, чтобы в сорировке учитывалось, что один объект занимает несколько индексов глубины, вот и всё.

[Maestro13]

Если вам нужно общее решение - то только резать. А если нет, то нужны дополнительные данные т.е. какие объекты могут занимать больше 1 клетки и проч. ? это действительно важно.

Все статические объекты могут быть произвольного размера и высоты, но прямоугольные(тоесть 2*3 или 4*8 или 5*5 или 1*1 и.т.д) динамические же объекты все 1*1. Уровень земли у всех объектов одинаковый. Объекты выводятся спрайтами

Добавлено через 1 минуту
expl, я не совсем понял ваш алгоритм, можно поподробнее