Tilemap isometrisch rendern.

Übersicht Sonstiges Gamedesign

Neue Antwort erstellen

 

feider

ehemals "Decelion"

Betreff: Tilemap isometrisch rendern.

BeitragDi, Feb 17, 2015 12:34
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi!

Ich habe mir ein paar Gedanken gemacht, wie ich am besten das isometrische Darstellen einer Tilemap realisieren könnte. Hierbei geht es darum das ganze möglichst mit 2D-Mitteln, aber mit einer 3D-Tilemap zu machen.

Wie mache ich das, worum geht es dabei?

Erstmal die Grundlagen.
Wenn ich meine Tilemap einfach so vorliegen habe, als zweidimensionales Array, dann ist das Ganze recht einfach.
Nehmen wir an, die Tiles sind tx = 64 Pixel breit und ty = 32 Pixel hoch. x und y sind die Position des Tiles im Array, sx und sy sind die Position auf dem Bildschirm. Nimmt man an, dass die obere linke Ecke der Tilemap in der gerenderten Isometrie oben liegen soll, verschiebt jeder Schritt in x-Richtung das dargestellte Tile um tx/2 nach rechts und um ty/2 nach unten. Jeder Schritt in y-Richtung verschiebt das dargestellte Tile um tx/2 nach links und auch um ty/2 nach unten.

Also zusammengefasst:
BlitzBasic: [AUSKLAPPEN]

sx = ( x*(tx/2) ) - ( y*(tx/2) )
sy = ( x*(ty/2) ) +( y*(ty/2) )


Nun kann ich für jedes Tile noch eine Höheninformation speichern, fals mein Gelände uneben ist.
Nehmen wir also an z(x, y) liefert mir für jedes Tile die Höhe und tz sei die Anzahl von Pixeln, die das isometrische Tile nach oben verschoben werden muss.

Es gilt nach obiger Berechnung:
BlitzBasic: [AUSKLAPPEN]

sy = sy - ( tz * z(x, y) )


So weit so gut, jetzt kommen wir jedoch zu dem Punkt, ab dem das einfache Zeichnen der Tilemap nicht mehr möglich ist: höhere Tiles können niedrigere Tiles verdecken.

Meine Lösung wäre es nun, die gesamte Tilemap durchzulaufen und die Tiles als Tupel bestehend aus (tileart, sx, sy, distance) in eine Priority Queue einzuordnen. distance beschreibt hierbei den Abstand zur "Kamera", die Tiles sind nach dem Abstand geordnet. Beim Rendern wird immer das Tile mit dem aktuell größten Abstand zur Kamera ausgewählt und aus der PQ entfernt. Für jedes Tile auf der tiefesten Ebene entspricht der Abstand der negativen y-Koordinate auf dem Bildschirm. Daraus folgt, dass für die hinteren Tiles der Abstand groß ist, für die forderen Tiles gering. Für jede höhere Ebene gilt erstmal das gleiche - Mit dem Unterschied, dass für jede höhere Ebene die Bildschirmhöhe vom Wert "distance" abgezogen wird. Somit haben Tiles immer einen niedrigeren distance-Wert als die Tiles einer niedrigeren/daruntergelegenen Ebene und werden später gezeichnet - also über die schon gezeichneten Tiles drüber.

Auch eine richtige 3D-Tilemap liesse sich damit Zeichnen, falls ich eine entsprechende Repräsentation habe. unklug wäre es, JEDES 3D-Tile zu durchlaufen von Ebene -50000 bis +50000, falls die Mehrheit dieser Tiles durch darüberliegende Tiles verdeckt werden / sowieso nur solide (Erd-)blöcke sind. Eine schöne Repräsentation wäre eine 2D-Tilemap, bei der für jede (x, y)-Position mehr als ein Tile gespeichert werden kann. Somit könnten beim Rendering der Map alle Tiles einer Position in die PQ aufgenommen werden und durchlaufen werden. In dieser 2D-Tilemap würden nur die Surface-Tiles gespeichert werden, also nicht die, die innerhalb eines ausgefüllten Volumens liegen. Tunnels etc würden hingegen gespeichert werden.

Ich muss sehen, ob es performant genug ist, alle 1/60 Sekunden diesen Vorgang durchzuführen. Normales Tilemapzeichnen sollte sich bei n tiles in O(n) schaffen lassen. Einfügen jedes Tiles dauert O(log n), entfernen genauso O(log n). Natürlich weniger, wenn die PQ noch nicht voll/nicht mehr voll ist, aber rechnen wir damit.

Statt O(n) zum Zeichnen der Tiles hätte man nun eine Laufzeit von maximal 2*n*log n, was O(n*log n) entspricht.
Ist natürlich nicht so schön wie O(n), aber falls man mehrere Ebenen hat, müsste man die von unten nach oben durchlaufen. Somit hätte man mit e := Anzahl der Ebenen eine Laufzeit von O(n*e) , während man in meiner Variante nach wie vor eine Laufzeit von ungefähr O(n*log n) hat.

Bei 1000 zu zeichnenden Tiles, verteilt auf 50 Ebenen wären das bei der Standardvariante n*e = 1000*50 = 50,000 Aktionen. In meiner Variante sind es 1000*ln(1000) ~= 1000*7 = 7000 Aktionen.

Falls das nicht schnell genug ist, wäre meine nächste Idee, die Spielwelt in Chunks zu unterteilen. pro Chunk wird die Zeichenreihenfolge fest gespeichert und nur neu berechnet, wenn sich die Spielwelt ändert.

Ich werde das Ganze in den nächsten Tagen in C++ implementieren und dann berichten, wie es aussieht/funktioniert, wie performant das Ganze ist.

Hat sonst noch jemand Fragen oder Vorschläge, wie das Ganze schöner und effizienter gemacht werden könnte?

Gruß
feider

DAK

BeitragDi, Feb 17, 2015 14:39
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich weiß nicht, ob es wirklich schneller ist, aber was hälst du von dieser Idee:

-) Gezeichnet müssen eigentlich nur Oberflächen-Tiles werden. Das heißt, wenn ein Tile eingefügt wird, dann wird gecheckt, ob es entweder auf der Oberseite oder einer der beiden Seiten, die Richtung Kamera schauen, frei ist. Wenn nicht, dann wird es als Nicht-Oberflächen-Tile geflaggt und nicht gezeichnet. Bei dem Einfügen wird der gleiche Check auch für benachbarte Tiles durchgeführt. Einfügen ist insofern immer konstant schnell ( O(1) ).

-) Dadurch, dass durch die Oberflächentile-Bestimmung eh schon die meisten unsichtbaren Tiles verschwinden, kann man eigentlich schon naiv zeichnen. Eine weitere Optimierung zahlt sich hier wohl in den meisten Fällen nicht aus, ansonsten kannst du deine Optimierung für alle Oberflächentiles durchführen.

-) Beim naiven Zeichnen gehst du alle Tiles zuerst anhand ihrer Distanz zur Kamera entlang der XZ-Ebene durch (ohne Berücksichtigung ihrer Y-Koordinate) und zeichnest alle Oberflächentiles jedes "Stapels" von unten nach oben. Auf diese Weise hast du das Z-Sorting fix drinnen ohne dich extra drum kümmern (und somit was berechnen) zu müssen.
Gewinner der 6. und der 68. BlitzCodeCompo
 

feider

ehemals "Decelion"

BeitragDi, Feb 17, 2015 15:37
Antworten mit Zitat
Benutzer-Profile anzeigen
In meiner beschriebenen Datenstruktur für die Tiles werden eh nur die Tiles gespeichert, die von irgend einer Seite aus sichtbar sind.

Und nur weil ein Tile nach allen Seiten frei ist, muss es ja nicht unbedingt gezeichnet werden. Ein Tunnelboden ist auch nach oben hin frei, besonders, wenn es ein geräumiger Tunnel ist - dennoch muss er von einer Kamera an der Oberfläche nicht unbedingt gesehen werden.

Ich kann aktuell nicht sehen, wie das einen Vorteil bringt!

Zitat:

-) Beim naiven Zeichnen gehst du alle Tiles zuerst anhand ihrer Distanz zur Kamera entlang der XZ-Ebene durch (ohne Berücksichtigung ihrer Y-Koordinate) und zeichnest alle Oberflächentiles jedes "Stapels" von unten nach oben. Auf diese Weise hast du das Z-Sorting fix drinnen ohne dich extra drum kümmern (und somit was berechnen) zu müssen.


Darüber habe ich auch schon nachgedacht. Ich müsste dennoch erstmal die Tiles nach ihrer Entfernung zur Kamera sortieren! Ich bin mir nicht sicher, ob mir das wirklich viel bringt.

DAK

BeitragDi, Feb 17, 2015 16:02
Antworten mit Zitat
Benutzer-Profile anzeigen
Brauchstas ned wirklich sortieren. Ich nehme an, dass deine Kamera (da du von Iso redest) nicht frei drehbar ist, sondern im besten Fall in vier Richtungen schauen kann.

Die Zeichenreihenfolge lässt sich leicht anhand eines Bildes zeigen:
user posted image

Zuerst Rot, dann Blau, dann Grün, dann Gelb, dann Magenta, und so weiter.

Lässt sich einfach über zwei verschachtelte For-Schleifen lösen.
Gewinner der 6. und der 68. BlitzCodeCompo
 

feider

ehemals "Decelion"

BeitragDi, Feb 17, 2015 16:04
Antworten mit Zitat
Benutzer-Profile anzeigen
Oh.
Da hast du recht! Dann wird das wohl doch ein wenig einfacher.
Keine PQ, einfach nur O(n) Very Happy

Danke für den Hinweis! Wenn man zu viel darüber nachdenkt, hat man irgendwann ein Brett vorm Kopf gegenüber den einfachen Lösungen.

Neue Antwort erstellen


Übersicht Sonstiges Gamedesign

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group