Wie bestimme ich die Ziehungsreihenfolge in einem Flash-Spiel mit isometrischer Ansicht?

12

Dies ist für ein Flash-Spiel mit isometrischer Ansicht. Ich muss wissen, wie Objekte sortiert werden, damit beim Zeichnen keine Überprüfung des Z-Puffers erforderlich ist. Dies mag einfach erscheinen, es gibt jedoch eine weitere Einschränkung: Eine Szene kann mehr als 10.000 Objekte enthalten, sodass der Algorithmus in weniger als O (n ^ 2) ausgeführt werden muss. Alle Objekte sind rechteckige Kästchen, und in der Szene bewegen sich 3-4 Objekte. Wie geht das am besten?

AKTUALISIEREN

In jedem Plättchen gibt es nur Objekte (ich meine, Objekte können nicht übereinander gestapelt werden). und wir greifen sowohl auf die Karte von Objekten zu als auch auf Objekte, die ihre eigene Position haben.

UPDATE2

siehe diese Figuren:

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Zuerst sollte ein erstes blaues Objekt gezeichnet werden, dann grün und dann rot. während im zweiten musst du sie in umgekehrter Reihenfolge zeichnen. Sie müssen zuerst rot und dann grün und schließlich blau Objekt zeichnen. Wie Sie sehen, gibt es keinen Unterschied in der Position von blauen und roten Objekten, beide haben unterschiedliche Abstände von der Kamera und so weiter. Aufgrund ihrer relativen Position zur grünen Box müssen Sie jedoch die Zeichenreihenfolge zwischen zwei Bildern ändern. Das ist es, was dieses Problem zu einem Chaos macht.

Randnotiz: Da alle Objekte rechteckige Prismen sind, ist es mathematisch nachweisbar, dass es mindestens eine Zeichenreihenfolge gibt, um die Problembedürfnisse zu befriedigen.

Ali1S232
quelle
2
Sie sollten weitere Informationen posten. Können Objekte gestapelt werden (3d)? Objekte haben Positionen oder die Karte hat Objekte? etc.
KaoD
2
Ist dies dasselbe wie gamedev.stackexchange.com/questions/8151/…
Tetrad
@Tetrad ja, aber es gibt wenig Unterschied zu den Objekten, die wir in die Szene setzen.
Ali1S232
@Gajet (nach Ihrem Update) Objekte können nur 1 * X und X * 1 oder auch X * Y sein? Könnten Sie es sich leisten, die Objekte in mehrere Unterobjekte aufzuteilen? (wie Grün 4 untergrüne Objekte darstellt) Ist die Ausrichtung des Objekts festgelegt?
KaoD
Außerdem: Wie viele benachbarte Kacheln verdecken die Höhe Ihres Objekts?
KaoD

Antworten:

8

Dies ist eigentlich sehr einfach, wenn Ihre Objekte mit Ihren isometrischen Kacheln übereinstimmen. Schauen Sie sich dieses Bild an:

Isometrische Zeichnungsreihenfolge

Sie sollten zuerst das Objekt an der roten Position zeichnen, dann Objekte an der blauen, dann an der grünen, dann an der gelben, dann an der magentafarbenen und so weiter. Es sollte ziemlich offensichtlich sein, wie dies implementiert wird, wenn Ihr Board Objekte anstelle von Objekten enthält Position als Attribut haben. Wenn dies nicht der Fall ist, sollten Sie eine separate Datenstruktur beibehalten und diese aktualisieren, wenn sich ein Objekt bewegt (was ebenfalls recht einfach sein sollte).

Dies hat ein neues Problem: Sie können leicht erkennen, wie komplex O (N) ist, wobei N Ihre Platinengröße ist ( N=W*H). Um dieses Problem zu lösen, erstellen Sie einfach eine neue lineare Datenstruktur, bei der jeder Index in Ihrer Struktur einer bestimmten Tiefe entspricht, und aktualisieren Sie sie, wenn sich die Tiefe eines Objekts ändert.

Der Fall, dass ein Objekt nicht mit einer einzelnen Kachel übereinstimmt, ist etwas schwieriger. Ich werde es veröffentlichen, wenn Sie es benötigen, sobald Sie Ihre Frage aktualisieren.

kaoD
quelle
Dieser Algorithmus ist auch der erste, der mir in den Sinn gekommen ist, aber siehe mein Update, deshalb können Sie ihn nicht ohne Änderung verwenden.
Ali1S232
1
@Gajet und das ist die Art von Dingen, die Sie in Ihrer Frage an erster Stelle
posten müssen
3
Dies ist der richtige Weg, um die großen Teile in "Fliesen" +1 aufzuteilen
Valmond
2

Ich habe keine speziellen Kenntnisse zu diesem Thema, aber hier ist ein Gedanke.

Beginnen Sie, indem Sie jede Zelle als "nicht gezeichnet" markieren. (Oder verwenden Sie gleichermaßen ein Array, um die Position des nächsten "gezeichneten" Objekts auf jeder "Nah-Fern-Linie" von Zellen oder einer Menge usw. darzustellen.) Dann für jede Zelle (ich würde sie wahrscheinlich durchgehen) die Reihenfolge kaoD beschrieben): Überprüfen Sie, ob diese Zelle gezogen wurde; Wenn es nicht gezeichnet wurde und ein Objekt enthält, prüfen Sie, ob jede Zelle, die von diesem Objekt verdeckt würde, gezeichnet wurde, und wenn nicht, rekursiv gezeichnet wurde. Zeichnen Sie gegebenenfalls das Objekt, das in dieser Zelle enthalten ist. und markiere diese Zelle und alle Zellen, die von ihrem Objekt besetzt sind, als "gezeichnet".

Ich gehe davon aus, dass Sie dem Objekt darin schnell eine Zelle zuordnen können, falls vorhanden. Ich glaube, dies ist O (n) Zeit, obwohl es dazu führen könnte, dass ein großer Stapel erstellt wird (den Sie möglicherweise in eine verknüpfte Liste umwandeln möchten, wenn Sie befürchten, dass Ihnen der Stapelplatz ausgeht).

Wenn Sie wirklich eine Liste benötigen, können Sie an eine Liste anhängen, anstatt zu zeichnen. Ich vermute, dass es nicht hilft, mit einer meist sortierten Liste zu beginnen.

Vincent Povirk
quelle
Ich glaube, dieser Algorithmus kann als eine Form von topologischer Sortierung angesehen werden, die an das Problem angepasst ist. Ich wollte gerade selbst vage in diese Richtung zeigen. Topologische Sortierung ist eine Lösung für die meisten Ordnungs- / Abhängigkeitsprobleme.
Kevin Reid
1

Ich würde den Algorithmus des Malers mit einem Taxidistanz von der am weitesten von der Kamera entfernten Zelle verwenden, indem ich zuerst diejenigen zeichne, die der Kamera am nächsten sind, und mich dann nach außen bewege.

Bearbeiten: Dies funktioniert nur, wenn Sie den Inhalt jeder Zelle einzeln zeichnen können.

Quasiperfect
quelle
das mag funktionieren, aber ich kann nicht sagen, wie es sich von den vorgeschlagenen Algorithmen byte56 oder kaoD unterscheidet. für mich scheint es immer noch die gleichen probleme zu geben wie in meinem zweiten edit beschrieben.
Ali1S232
1

Was lässt Sie glauben, dass es „mathematisch nachweisbar ist, dass es mindestens eine Zeichnungsreihenfolge gibt, um die Problemanforderungen zu erfüllen“? Hier ist ein triviales Gegenbeispiel, bei dem Sie sich nicht auf Objekte mit Z-Sortierung verlassen können:

Bildbeschreibung hier eingeben

sam hocevar
quelle
Nur aus Neugierde ... könnten Sie das Gegenbeispiel erläutern? Das ist kein Gitter.
KaoD
Beachten Sie, dass es auf jeder Kachel nur ein Objekt gibt und das Objekt eine oder mehrere Kacheln belegen kann, diese jedoch immer eine rechteckige Projektion in der Ebene haben. Diese beiden Bedingungen reichen aus, um diese Aussage zu beweisen.
Ali1S232
Okay, mit diesen Einschränkungen und der Tatsache, dass das Gitter flach ist, gibt es eine Lösung. Ich werde es später posten.
Sam Hocevar