Jak posortować duszki izometryczne we właściwej kolejności?

W normalnej grze 2D z góry można sortować obrazy za pomocą osi y ekranu. W tym przykładzie drzewa są odpowiednio posortowane, ale ściany izometryczne nie są:

Ściana 2 znajduje się jeden piksel poniżej ściany 1, dlatego jest rysowana za ścianą 1 i kończy się na górze.

Jeśli posortuję według izometrycznej osi y, ściany pojawią się we właściwej kolejności, ale drzewa nie:

Jak to zrobić poprawnie?

Gry izometryczne są funkcjonalnie 3D, więc wewnętrznie powinieneś przechowywać współrzędne 3D dla każdej jednostki w grze. Rzeczywiste współrzędne, które wybierzesz, są dowolne, ale powiedzmy, że X i Y są dwiema osiami na ziemi, a Z leży nad ziemią w powietrzu.

Moduł renderujący musi następnie rzutować go na 2D, aby rysować elementy na ekranie. „Izometryczny” to jedna z takich projekcji. Rzutowanie izometryczne z 3D na 2D jest dość proste. Powiedzmy, że oś X przechodzi od lewego górnego do prawego dolnego i dolnego o jeden piksel na każde dwa piksele poziome. Podobnie oś Y biegnie od górnego prawego do dolnego lewego. Oś Z idzie prosto w górę. Aby przekonwertować z 3D na 2D, wystarczy:

function projectIso(x, y, z) {
    return {
        x: x - y,
        y: (x / 2) + (y / 2) - z
    };
}

Teraz twoje pierwotne pytanie, sortowanie. Teraz, gdy pracujemy z naszymi obiektami bezpośrednio w 3D, sortowanie staje się znacznie prostsze. W naszej przestrzeni współrzędnych tutaj najdalszy duszek ma najniższe współrzędne x, y i z (tzn. Wszystkie trzy osie wskazują na ekran). Więc posortuj je według sumy tych:

function nearness(obj) {
    return obj.x + obj.y + obj.z;
}

function closer(a, b) {
    if (nearness(a) > nearness(b)) {
        return "a";
    } else {
        return "b";
    }
}

Aby uniknąć ponownego sortowania bytów w każdej klatce, użyj sortowania w szufladzie, szczegółowo opisanego tutaj .

Zakładając, że twoje duszki zajmują zestawy płytek, które są prostokątami (jeśli zajmują dowolne zestawy, to w ogóle nie możesz narysować poprawnie w ogóle), problem polega na tym, że nie ma całkowitej relacji między elementami, więc nie możesz sortować używając metody sortowania, która spowodowałaby porównania O (nlogn).

Zauważ, że dla dowolnych dwóch obiektów A i B albo A należy narysować przed B (A <- B), B należy narysować przed A (B <- A) lub można je narysować w dowolnej kolejności. Tworzą częściowe zamówienie. Jeśli narysujesz sobie kilka przykładów z 3 nakładającymi się obiektami, możesz zauważyć, że chociaż pierwszy i trzeci obiekt mogą się nie nakładać, a zatem nie mają bezpośredniej zależności, ich kolejność rysowania zależy od drugiego obiektu, który jest między nimi - w zależności od tego, jak umieścisz go, otrzymasz różne zamówienia rysowania. Dolna linia - tradycyjne rodzaje nie działają tutaj.

Jednym z rozwiązań jest użycie porównania (wspomnianego przez Dani) i porównanie każdego obiektu ze sobą w celu ustalenia ich zależności i utworzenia wykresu zależności (który będzie DAG). Następnie wykonaj sortowanie topologiczne na wykresie, aby określić kolejność rysowania. Jeśli nie ma zbyt wielu obiektów, może to być wystarczająco szybkie (to jest O(n^2)).

Innym rozwiązaniem jest użycie (do równoważenia - pseudo ) drzewa quad i przechowywanie w nim prostokątów wszystkich obiektów.

Następnie iteruj przez wszystkie obiekty X i użyj drzewa quadów, aby sprawdzić, czy w pasku nad obiektem X znajdują się obiekty Y, które zaczynają się od skraju lewej i kończą skrajnym prawym narożnikiem obiektu X - dla wszystkich takich Y, Y < - X. W ten sposób nadal będziesz musiał utworzyć wykres i sortować topologicznie.

Ale możesz tego uniknąć. Używasz listy obiektów Q i tabeli obiektów T. Powtarzasz wszystkie widoczne szczeliny od mniejszych do większych wartości na osi x (jeden rząd), przechodząc rząd po rzędzie na osi y. Jeśli w tym gnieździe znajduje się dolny róg obiektu, wykonaj powyższą procedurę, aby określić zależności. Jeśli obiekt X zależy od jakiegoś innego obiektu Y, który jest częściowo nad nim (Y <- X), a każde takie Y jest już w Q, dodaj X do Q. Jeśli istnieje jakieś Y, które nie jest w Q, dodaj X do T i oznaczają, że Y <- X. Za każdym razem, gdy dodajesz obiekt do Q, usuwasz zależności obiektów oczekujących w T. Jeśli wszystkie zależności zostaną usunięte, obiekt z T jest przenoszony do Q.

Zakładamy, że duszki obiektów nie wystają ze swoich szczelin na dole, z lewej lub z prawej strony (tylko u góry, jak drzewa na zdjęciu). To powinno poprawić wydajność dla dużej liczby obiektów. Takie podejście znów będzie O(n^2), ale tylko w najgorszym przypadku, który obejmuje przedmioty o dziwnych rozmiarach i / lub dziwne konfiguracje obiektów. W większości przypadków tak jest O(n * logn * sqrt(n)). Znajomość wysokości twoich duszków może wyeliminować sqrt(n), ponieważ nie musisz sprawdzać całego paska powyżej. W zależności od liczby obiektów na ekranie możesz spróbować zastąpić drzewo quadów tablicą wskazującą, które miejsca są zajęte (ma to sens, jeśli jest wiele obiektów).

Na koniec zachęcamy do sprawdzenia tego kodu źródłowego pod kątem niektórych pomysłów: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala

Nie sądzę, że istnieje matematyczne rozwiązanie. Prawdopodobnie nie masz wystarczającej ilości danych w świecie 2D, w którym żyją twoje przedmioty. Jeśli twoje ściany byłyby dublowane na X, byłyby w „poprawnej” kolejności. Z drugiej strony możesz być w stanie wykonać testy nakładania się z ramką ograniczającą obrazu, ale nie jest to obszar, który jest mi obcy.

Prawdopodobnie powinieneś posortować według ekranu Y według kafelków i powiedzieć, że bardziej skomplikowane jest „problem projektowy”. Na przykład, jeśli tworzysz treść, po prostu powiedz swoim projektantom algorytm sortowania i przesuń wall2 2 piksele w górę, aby rozwiązać problem. Tak musieliśmy to naprawić w grze izometrycznej, nad którą pracowałem. Może to obejmować wzięcie „długich” przedmiotów i rozbicie ich na kawałki wielkości płytek.

Jeśli pozwalasz użytkownikom edytować zawartość, całkowicie bezpieczne jest, aby wszystko opierać się na kafelkach, a co najwyżej jeden kafelek był duży. W ten sposób unikniesz problemu. Być może uda ci się zrobić wszystko, co większe niż kafelek, ale być może tylko wtedy, gdy będzie kwadratowy. Nie bawiłem się tym.

Idealne sortowanie izometryczne jest trudne. Ale dla pierwszego podejścia, aby właściwie posortować swoje przedmioty, powinieneś użyć bardziej złożonej funkcji porównawczej dla każdego nakładającego się obiektu. Ta funkcja musi sprawdzić ten warunek: Nakładający się obiekt „a” znajduje się za „b”, jeśli:

(a.posX + a.sizeX <= b.posX) lub (a.posY + a.sizeY <= b.posY) lub (a.posZ + a.sizeZ <= b.posZ)

Oczywiście jest to pierwszy pomysł naiwnej implementacji izometrycznej. W przypadku bardziej złożonego scenariusza (jeśli chcesz obrócić widok, pozycje na piksel na osi Z itp.) Musisz sprawdzić więcej warunków.

Używam bardzo prostej formuły, która działa dobrze z moim małym silnikiem izometrycznym w OpenGL:

Każdy z was obiektów (drzewa, płytki podłogowe, postacie, ...) ma pozycję X i Y na ekranie. Musisz włączyć TESTOWANIE GŁĘBOKOŚCI i znaleźć dobrą wartość Z dla każdej wartości. Możesz po prostu wykonać następujące czynności:

z = x + y + objectIndex

Używam innego indeksu dla podłogi i obiektów, które będą nad podłogą (0 dla podłogi i 1 dla wszystkich obiektów, które mają wysokość). To powinno działać dobrze.

Obszerna odpowiedź z wieloma rozwiązaniami, zdjęciami i całą matematyką tutaj:

/programming/892811/drawing-isometric-game-worlds

Jeśli porównasz wartości y w tej samej pozycji x, będzie działać za każdym razem. Więc nie porównuj środka do środka. Zamiast tego porównaj środek jednej ikonki z tą samą pozycją x na drugiej ikonce.

Ale wymaga to pewnych danych geometrycznych dla każdego duszka. Może to być tak proste, jak dwa punkty od lewej do prawej strony, które opisują dolną granicę dla duszka. Lub możesz przeanalizować dane obrazu duszków i znaleźć pierwszy piksel, który nie jest przezroczysty.

Łatwiejszym podejściem jest podzielenie wszystkich duszków na trzy grupy: przekątna wzdłuż osi x, przekątna wzdłuż osi y i płaska. Jeśli oba obiekty są ukośne wzdłuż tej samej osi, posortuj je na podstawie drugiej osi.

Musisz przypisać unikalne identyfikatory do wszystkich obiektów tego samego typu. Następnie sortujesz wszystkie obiekty według ich pozycji i rysujesz grupy obiektów według ich identyfikatorów. Tak więc obiekt 1 w grupie A nigdy nie zastąpi obiektu 2 w grupie A itp.

To nie jest tak naprawdę odpowiedź, ale tylko komentarz i głosowanie na górę. Chciałbym udzielić odpowiedzi na pytanie tego axel22 tutaj /gamedev//a/8181/112940

Nie mam wystarczającej reputacji, aby głosować lub komentować inne odpowiedzi, ale drugi akapit jego odpowiedzi jest prawdopodobnie najważniejszą rzeczą, o której należy pamiętać, próbując uporządkować byty w grze izometrycznej bez polegania na „nowoczesnym” 3D techniki takie jak bufor Z.

W moim silniku chciałem robić rzeczy „oldschoolowe”, czyste 2D. Spędziłem dużo czasu, próbując zrozumieć, dlaczego moje wezwanie do „sortowania” (w moim przypadku było to c ++ std :: sort) nie działa poprawnie w niektórych konfiguracjach map.

Dopiero gdy zdałem sobie sprawę, że jest to sytuacja „częściowego porządku”, udało mi się ją rozwiązać.

Do tej pory wszystkie działające rozwiązania, które znalazłem w sieci, używały pewnego rodzaju sortowania topologicznego, aby poprawnie rozwiązać problem. Najlepszym rozwiązaniem wydaje się sortowanie topologiczne.