Jak ustalić kolejność losowania w grze flash w widoku izometrycznym?

To jest gra flash z widokiem izometrycznym. Muszę wiedzieć, jak sortować obiekty, aby nie było potrzeby sprawdzania bufora Z podczas rysowania. To może wydawać się łatwe, ale istnieje inne ograniczenie, scena może zawierać ponad 10 000 obiektów, więc algorytm musi być uruchomiony w mniej niż O (n ^ 2). Wszystkie obiekty są prostokątnymi polami, a na scenie poruszają się 3-4 obiekty. Jak najlepiej to zrobić?

AKTUALIZACJA

w każdym kafelku jest tylko obiekt (mam na myśli, że obiekty nie mogą się ustawiać jeden na drugim). a my mamy dostęp do mapy obiektów, a obiekty mają swoją pozycję.

AKTUALIZACJA 2

zobacz te liczby:

w pierwszym należy narysować pierwszy niebieski obiekt, a następnie zielony, a następnie czerwony. podczas gdy w drugim musisz je narysować w odwrotnej kolejności. najpierw musisz narysować czerwony, a następnie zielony, a na końcu niebieski obiekt. jak widać, nie ma różnicy w położeniu niebieskich i czerwonych obiektów, oba mają różną odległość od aparatu i tak dalej. ale ze względu na ich względne położenie względem zielonego pola, musisz zmienić ich kolejność rysowania między dwoma obrazkami. to sprawia, że ​​ten problem jest bałaganem.

uwaga dodatkowa: ponieważ wszystkie obiekty są prostokątnymi pryzmatami, matematycznie można udowodnić, że istnieje co najmniej jedna kolejność rysowania w celu zaspokojenia potrzeb problemowych.

Jest to w rzeczywistości bardzo proste, jeśli twoje obiekty pasują do twoich płytek izometrycznych. Spójrz na ten obraz:

Powinieneś najpierw narysować obiekt w pozycji czerwonej, następnie obiekty w kolorze niebieskim, następnie zielonym, następnie żółtym, następnie purpurowym i tak dalej ... Powinno być całkiem oczywiste, jak to zaimplementować, jeśli na planszy są obiekty zamiast obiektów mając pozycję jako atrybut. Jeśli tak nie jest, powinieneś zachować oddzielną strukturę danych, aktualizując ją za każdym razem, gdy obiekt się porusza (co również powinno być dość łatwe).

Ma to nowy problem: możesz łatwo zobaczyć, jak teraz jego złożoność wynosi O (N), gdzie N jest rozmiarem twojej płyty ( N=W*H). Aby rozwiązać ten problem, po prostu utwórz nową liniową strukturę danych, w której każdy indeks w strukturze pasuje do określonej głębokości, aktualizując ją za każdym razem, gdy obiekt zmienia głębokość.

Przypadek, w którym obiekt nie pasuje do jednego kafelka, jest nieco trudniejszy, więc opublikuję go, jeśli będzie potrzebny, jak tylko zaktualizujesz swoje pytanie.

Nie mam specjalnej wiedzy na ten temat, ale oto myśl.

Zacznij od oznaczenia każdej komórki jako „nie narysowanej”. (Lub, równoważnie, użyj tablicy do reprezentowania położenia najbliższej „narysowanej” rzeczy na każdej „bliskiej linii” komórek lub zestawu itp.) Następnie dla każdej komórki (prawdopodobnie przejrzałbym je w kolejność opisana kaoD): sprawdź, czy ta komórka została narysowana; jeśli nie został narysowany i zawiera obiekt, sprawdź, czy każda komórka, która byłaby zasłonięta przez ten obiekt, została narysowana, a jeśli nie, narysuj go rekurencyjnie; w razie potrzeby narysuj obiekt zawarty w tej komórce; i zaznacz tę komórkę i wszystkie komórki zajmowane przez jej obiekt jako „narysowane”.

Zakładam, że możesz szybko odwzorować komórkę na znajdujący się w niej obiekt, jeśli taki istnieje. Wydaje mi się, że jest to czas O (n), ale może skończyć się budowaniem dużego stosu (który możesz chcieć zmienić w połączoną listę, jeśli martwisz się brakiem miejsca na stosie).

Jeśli naprawdę potrzebujesz listy, możesz dołączyć do listy zamiast rysować. Podejrzewam, że rozpoczęcie od najczęściej posortowanej listy nie pomaga.

Chciałbym skorzystać z algorytm malarza z odległości taksówki od najdalszej celi z dala od aparatu, rysunek te najbliżej aparatu, a następnie przeniesienie na zewnątrz.

Edycja: To nie działa, chyba że możesz narysować zawartość każdej komórki osobno.

Co sprawia, że ​​uważasz, że „matematycznie można udowodnić, że istnieje co najmniej jedno polecenie losowania w celu zaspokojenia potrzeb problemowych”? Oto prosty przykład, w którym nie można polegać na obiektach sortujących Z: