Wie sortiere ich isometrische Sprites in der richtigen Reihenfolge?

In einem normalen 2D-Spiel von oben nach unten könnte man die y-Achse des Bildschirms verwenden, um die Bilder zu sortieren. In diesem Beispiel sind die Bäume richtig sortiert, die isometrischen Wände jedoch nicht:

Wand 2 ist ein Pixel unter Wand 1, daher wird sie nach Wand 1 gezeichnet und endet oben.

Wenn ich nach der isometrischen y-Achse sortiere, erscheinen die Wände in der richtigen Reihenfolge, die Bäume jedoch nicht:

Wie mache ich das richtig?

Isometrische Spiele sind funktionell 3D, daher sollten Sie intern die 3D-Koordinaten für jedes Objekt im Spiel speichern. Die tatsächlichen Koordinaten, die Sie auswählen, sind willkürlich. Nehmen wir jedoch an, X und Y sind die beiden Achsen auf dem Boden, und Z ist vom Boden aus in die Luft gerichtet.

Der Renderer muss das dann in 2D projizieren, um Dinge auf dem Bildschirm zu zeichnen. "Isometrisch" ist eine solche Projektion. Die isometrische Projektion von 3D auf 2D ist ziemlich einfach. Angenommen, die X-Achse verläuft von links oben nach rechts unten und für jeweils zwei horizontale Pixel um ein Pixel nach unten. Ebenso verläuft die Y-Achse von rechts oben nach links unten. Die Z-Achse fährt gerade nach oben. Von 3D nach 2D zu konvertieren ist dann nur noch:

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

Nun zu Ihrer ursprünglichen Frage: Sortieren. Da wir jetzt mit unseren Objekten direkt in 3D arbeiten, wird das Sortieren viel einfacher. In unserem Koordinatenraum hat das am weitesten entfernte Sprite die niedrigsten x-, y- und z-Koordinaten (dh alle drei Achsen zeigen vom Bildschirm aus). Also sortieren Sie sie einfach nach der Summe dieser:

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

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

Um zu vermeiden, dass Sie Ihre Objekte bei jedem Frame neu sortieren, verwenden Sie eine hier beschriebene Sortierung für die Ablagefächer .

Angenommen, Ihre Sprites belegen Gruppen von Kacheln, bei denen es sich um Rechtecke handelt (wenn sie beliebige Gruppen belegen, können Sie im allgemeinen Fall die Kacheln überhaupt nicht richtig zeichnen), besteht das Problem darin, dass zwischen den Elementen keine Beziehung zur Gesamtreihenfolge besteht und Sie daher nicht sortieren können Sie verwenden eine Sortierung, die zu O (nlogn) -Vergleichen führen würde.

Beachten Sie, dass für zwei beliebige Objekte A und B entweder A vor B (A <- B), B vor A (B <- A) oder in beliebiger Reihenfolge gezeichnet werden kann. Sie bilden eine Teilordnung. Wenn Sie sich selbst einige Beispiele mit 3 überlappenden Objekten zeichnen, werden Sie feststellen, dass das 1. und das 3. Objekt sich möglicherweise nicht überlappen und somit keine direkte Abhängigkeit haben. Ihre Zeichenreihenfolge hängt vom 2. Objekt ab, das zwischen ihnen liegt - je nachdem, wie Wenn Sie es platzieren, erhalten Sie unterschiedliche Zeichenreihenfolgen. Fazit: Traditionelle Sorten funktionieren hier nicht.

Eine Lösung besteht darin, den Vergleich (von den Dani erwähnt) zu verwenden und jedes Objekt mit dem anderen Objekt zu vergleichen, um deren Abhängigkeiten zu bestimmen und einen Abhängigkeitsgraphen (der eine DAG sein wird) zu bilden. Führen Sie dann eine topologische Sortierung im Diagramm durch, um die Zeichenreihenfolge zu bestimmen. Wenn nicht zu viele Objekte vorhanden sind, ist dies möglicherweise schnell genug O(n^2).

Eine andere Lösung besteht darin, einen (zum Ausgleichen - Pseudo- ) Quad-Baum zu verwenden und die Rechtecke aller Objekte darin zu speichern.

Durchlaufen Sie dann alle Objekte X und überprüfen Sie mithilfe des Quad-Baums, ob sich Objekte Y in dem Streifen über dem Objekt X befinden, der ganz links beginnt und mit der ganz rechten Ecke von Objekt X endet - für alle diese Objekte Y, Y < - X. So müssen Sie immer noch ein Diagramm erstellen und topologisch sortieren.

Aber du kannst es vermeiden. Sie verwenden eine Liste von Objekten Q und eine Tabelle von Objekten T. Sie iterieren alle sichtbaren Slots von kleineren zu größeren Werten auf der x-Achse (eine Zeile), wobei Sie auf der y-Achse zeilenweise gehen. Befindet sich an diesem Steckplatz eine untere Ecke eines Objekts, gehen Sie wie oben beschrieben vor, um Abhängigkeiten zu ermitteln. Wenn ein Objekt X von einem anderen Objekt Y abhängt, das teilweise darüber liegt (Y <- X), und jedes Y bereits in Q ist, addiere X zu Q. Wenn es ein Y gibt, das nicht in Q ist, addiere X zu T und bezeichnen Y <- X. Jedes Mal, wenn Sie Q ein Objekt hinzufügen, entfernen Sie Abhängigkeiten von Objekten, die in T anstehen. Wenn alle Abhängigkeiten entfernt werden, wird ein Objekt von T nach Q verschoben.

Wir gehen davon aus, dass Objekt-Sprites nicht aus ihren Schlitzen unten, links oder rechts herausschauen (nur oben, wie Bäume in Ihrem Bild). Dies sollte die Leistung für eine große Anzahl von Objekten verbessern. Dies wird wieder O(n^2)der Fall sein , jedoch nur im schlimmsten Fall, der Objekte mit seltsamer Größe und / oder seltsame Konfigurationen von Objekten umfasst. In den meisten Fällen ist es O(n * logn * sqrt(n)). Wenn Sie die Höhe Ihrer Sprites kennen, können Sie das Problem beheben sqrt(n), da Sie nicht den gesamten Streifen oben überprüfen müssen. Abhängig von der Anzahl der Objekte auf dem Bildschirm können Sie versuchen, den Quad-Baum durch ein Array zu ersetzen, das angibt, welche Slots belegt sind (sinnvoll, wenn viele Objekte vorhanden sind).

Sie können diesen Quellcode auch auf Ideen überprüfen: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala

Ich glaube nicht, dass es eine mathematische Lösung gibt. Sie haben wahrscheinlich nicht genügend Daten in der 2D-Welt, in der Ihre Objekte leben. Wenn Ihre Wände auf X gespiegelt wären, wären sie in der "richtigen" Reihenfolge. Andererseits sind Sie möglicherweise in der Lage, Überlappungstests mit dem Begrenzungsrahmen des Bildes durchzuführen, aber dies ist ein Bereich, den ich nicht kenne.

Sie sollten wahrscheinlich nach Bildschirm Y pro Kachel sortieren und sagen, dass alles, was komplizierter ist, ein "Designproblem" ist. Wenn Sie zum Beispiel den Inhalt verfassen, teilen Sie Ihren Designern einfach den Sortieralgorithmus mit und schieben wall2 2 Pixel nach oben, um das Problem zu beheben. So mussten wir es in dem isometrischen Spiel beheben, an dem ich gearbeitet habe. Dies kann beinhalten, "lange" Gegenstände zu nehmen und sie in fliesengroße Stücke aufzubrechen.

Wenn Sie Benutzern erlauben, den Inhalt zu bearbeiten, ist es völlig sicher, alles kachelbasiert und höchstens eine Kachel groß zu machen. Auf diese Weise vermeiden Sie das Problem. Sie könnten damit auskommen, alles größer als eine Kachel zu machen, aber möglicherweise nur, wenn es quadratisch ist. Damit habe ich nicht rumgespielt.

Perfekte isometrische Sortierung ist schwierig. Für einen ersten Ansatz sollten Sie jedoch eine komplexere Vergleichsfunktion für jedes überlappende Objekt verwenden, um Ihre Elemente richtig zu sortieren. Diese Funktion muss diese Bedingung prüfen: Ein überlappendes Objekt "a" steht hinter "b", wenn:

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

Dies ist natürlich eine erste Idee für eine naive isometrische Implementierung. Für ein komplexeres Szenario (wenn Sie die Ansicht drehen möchten, Positionen pro Pixel auf der Z-Achse usw.) müssen Sie mehr Bedingungen überprüfen.

Ich verwende eine sehr einfache Formel, die mit meiner kleinen isometrischen Engine in OpenGL gut funktioniert:

Jedes Ihrer Objekte (Bäume, Bodenfliesen, Zeichen, ...) hat eine X- und eine Y-Position auf dem Bildschirm. Sie müssen DEPTH TESTING aktivieren und für jeden Wert den richtigen Z-Wert finden. Sie können einfach zu Folgendem übergehen:

z = x + y + objectIndex

Ich benutze einen anderen Index für den Boden und Objekte, die über dem Boden liegen (0 für den Boden und 1 für alle Objekte, die eine Höhe haben). Dies sollte gut funktionieren.

Umfassende Antwort mit mehreren Lösungen, Bildern und der ganzen Mathematik hier:

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

Wenn Sie die y-Werte an derselben x-Position vergleichen, funktioniert dies jedes Mal. Vergleichen Sie also nicht Mitte zu Mitte. Vergleichen Sie stattdessen die Mitte eines Sprites mit der gleichen x-Position auf dem anderen Sprite.

Dies erfordert jedoch einige Geometriedaten für jedes Sprite. Es können auch zwei Punkte von links nach rechts sein, die die untere Grenze für das Sprite beschreiben. Sie können auch die Sprites-Bilddaten analysieren und das erste Pixel finden, das nicht transparent ist.

Eine einfachere Methode besteht darin, alle Sprites in drei Gruppen zu unterteilen: diagonal entlang der x-Achse, diagonal entlang der y-Achse und flach. Wenn zwei Objekte entlang derselben Achse diagonal sind, sortieren Sie sie basierend auf der anderen Achse.

Sie müssen allen Objekten desselben Typs eindeutige IDs zuweisen. Anschließend sortieren Sie alle Objekte nach ihrer Position und zeichnen Objektgruppen in der Reihenfolge ihrer IDs. Damit Objekt 1 in Gruppe A niemals Objekt 2 in Gruppe A usw. überzeichnet.

Dies ist nicht wirklich eine Antwort, sondern nur ein Kommentar und eine Aufwertung der Antwort von axel22 hier /gamedev//a/8181/112940

Ich habe nicht genug Reputation, um zu stimmen oder andere Antworten zu kommentieren, aber der zweite Absatz seiner Antwort ist wahrscheinlich das Wichtigste, das man beachten sollte, wenn man versucht, die Entitäten in einem isometrischen Spiel zu sortieren, ohne sich auf "modernes" 3D zu verlassen Techniken wie ein Z-Puffer.

In meinem Motor wollte ich Sachen "old-school" machen, reines 2D. Und ich habe viel Zeit damit verbracht, mein Gehirn zu zerbrechen, um herauszufinden, warum mein Aufruf zum "Sortieren" (in meinem Fall war es c ++ std :: sort) bei bestimmten Kartenkonfigurationen nicht richtig funktionierte.

Erst als ich merkte, dass dies eine "Teilordnungssituation" ist, konnte ich sie lösen.

Bisher verwendeten alle funktionierenden Lösungen, die ich im Web gefunden habe, eine Art topologische Sortierung, um das Problem richtig zu behandeln. Topologische Sortierung scheint der richtige Weg zu sein.