spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi Nexus auch hier.

Also das was du vorhast bringt dir überhaupt nix.
Im schlimmsten Fall hast du sogar Nachteile.
Ich benutze für meine Tilemap einen std::vectro<std::vector<Tile>>
Und glaub mir. Das Problem von der Performance liegt ganz wo anders.

Und da kannst du mir auch glaube. Ich habe schon seeeehr viele Tiles da mal reingestopft. Einer hat beim testen, weil er meinte, dass es Pixel sind mal 2000x2000 gemacht. Naja.. Es ist gelaufen. Verständlicheweise langsam, aber vector war nicht das Problem.

EDIT:
Ich habe dein Thread bei cpp auch kurz angeschaut und wie schon gesagt irgendwelche binäre Bäume sind da einfach Overkill.
Und wenn du lieb bist,gebe ich dir einen Tipp, wo der Zugriff auf ein Tile extreeem billig ist.
Das kostet dich dann ein paar Multiplikationen und ein paar Additionen. Fertig.

Also wenn du unbednigt einen besseren Zugriff haben willst, dann schreib dir lieber einen kleinen Wrapper für einen 2 Dimensionalen vector. Da hast du dann alles drin. Performance und Handhabung.
Aber mal so am Rande wofür musst du deine Tilemap so extrem bearbeiten?
Also vergrössern/verkleiner musst du eigl. nie dynamisch. Spalten/Zeilen hinzufügen/entfernen?! :roll:
Mach ein 2 dimensionalen vector und dann kannst du da drin einen Zeiger auf ein Tile speichern. Wenn dort nix sein soll, machst du hal einen Null Zeiger rein und prüfst dementsprechend. Bearbeiten musst du da nix, ausser das Tile, dass da ist, aber auf das kannst du leicht zugreifen.

Also ich habe das so gemacht, dass ich sage, dass jedes Tile gleich gross ist auf einer Map. Dann, kannst du ganz einfach, wenn du z.B das Tile an Position 35.43:77.66 haben willst ganz einfach duch allfällige Multiplikation der Grösse direkt auf das Tile 35:78 kommen, wenn du dann noch abrundest. (und je nach Darstellung der Position musst du hald noch ein 50% dazurechnen bevor du abrundest, aber das kennst du ja wahrscheinlich schon).
Das funktioniert bei mir so recht gut.

Also ich muss Drakon zustimmen. Es gibt kaum etwas statischeres in einem Spiel als die Tilemap (Wann man sich nicht gerade im Editor befindet). Da sollte man einen Container nehmen der möglichst schnelles Zeichnen und auffinden von Tiles ermöglicht.

Und ich denke für beides ist vector optimal. Aber wenn du es wirklich flexibel haben willst. Mach dir eine abstrakte Klasse, diese implementierst du einmal mit einem Vector einmal mit listen. So kannst du für den Editor die Listenversion nehmen um schnelleres einfügen zu erlauben und für Ingame die Vector version.

Wobei ich bezweifle, dass sich der Aufwand lohnt. Performancemäßig kommt vermutlich auf jede "Einschub" und "Vergrößerungs" Aktion der Tilemap tausende von Rendervorgängen und Lookups von Feldern ("Setzte Feld 23,34 auf xyz").
Und gerade was den Lookup angeht sind vectoren schneller, listen müssen von Anfang an komplett durchlaufen werden, vectoren nicht.

Also.. summa summarum.. ich würde sagen, dass der Vector eigentlich ziemlich ideal ist für Tilemaps.

Zitat von »"Nexus"«

Zitat von »"drakon"«

Aber mal so am Rande wofür musst du deine Tilemap so extrem bearbeiten?
Also vergrössern/verkleiner musst du eigl. nie dynamisch. Spalten/Zeilen hinzufügen/entfernen?! :roll:

Eben nicht extrem, aber es sollte trotzdem einigermassen konfortabel sein. Ich werde einen Level-Editor haben, bei dem ich die Ränder verändern oder die Dimension explizit angeben kann. Aber der Vector-Wrapper ist eine Überlegung wert.

Naja. Wenn für dich konfortablen bedeutet, dass du den einen eigenen vector oder ne map schreiben musst, gehts du lieber über vector und machst dir hald einen Wrapper das ist vieel konfortabler.

Zitat von »"Nexus"«

Zitat von »"drakon"«

Mach ein 2 dimensionalen vector und dann kannst du da drin einen Zeiger auf ein Tile speichern. Wenn dort nix sein soll, machst du hal einen Null Zeiger rein und prüfst dementsprechend. Bearbeiten musst du da nix, ausser das Tile, dass da ist, aber auf das kannst du leicht zugreifen.

Bringt es mehr, es über einen Zeiger zu lösen? Ich hätte jetzt eher an direkten Zugriff auf die Tiles gedacht, sonst bringt mir ja die automatische Speicherverwaltung vom Vektor nicht viel. Oder kommt man ernsthaft in Probleme wegen der Grösse, wenn man nicht Zeiger verwendet?

Du kannst auch ganze Objekte (Tile) speichern. Spielt eigentlich nicht so eine grosse Rolle. Musst dann hald einfach intern speichern, ob das Tile übrehaupt gerendert werden soll, oder nicht.
Naja. vector ist nicht unbedingt besser, wegen dem automatischen Speicherverwaltung. Das hast du mit normalen Arrays genau so, dass wenn das Array zerstört wird auch der Inhalt zerstört wird. (natürlich bei keinem von beidem wird delete aufgerufen). Das musst du dann hald schon noch selber machen beim zerstören, dass ist aber echt keine Sache.

Zitat von »"Nexus"«

Zitat von »"drakon"«

Also ich habe das so gemacht, dass ich sage, dass jedes Tile gleich gross ist auf einer Map.

Ja, das ist bei mir auch so.

Zitat

Dann, kannst du ganz einfach, wenn du z.B das Tile an Position 35.43:77.66 haben willst ganz einfach duch allfällige Multiplikation der Grösse direkt auf das Tile 35:78 kommen, wenn du dann noch abrundest. (und je nach Darstellung der Position musst du hald noch ein 50% dazurechnen bevor du abrundest, aber das kennst du ja wahrscheinlich schon).

Sorry, hier kann ich dir nicht ganz folgen. Wozu brauchst du Multiplikationen, um das auf das nächste Tile runden?

Damit wir uns nicht missverstehen: Ich hab es immer so gehandhabt, dass die Tiles rasterförmig angeordnet und quadratisch sind. Die einzelnen Tiles haben dann ganzzahlige Indizes, was meinst du mit 35.43:77.66? Oder wäre das nur ein Spezialfall (z.B. in der Kollisionsabfrage)? Und beim Zeichnen würde ich schauen, welche im Bild sind, und diese dann in zwei For-Schleifen durchgehen.

Naja, wenn du sagen wir sagst, dass ein Tile 1x1 gross ist (nicht Pixel, sondern Relativ), und dann die ganze map auf 0.5 skalierst, dann müsstest du hald die Abstände auch noch skalieren.
Das mit den Kommas meinte ich, wenn du einen Spieler auf Kollision testen willst genau. (Der kann sich ja auch ausserhalb der ganzzahligen Tiles befinden)

Ok. Ich gebe dir nochmal einen Tipp, wie du das ganze nochmal optimieren kannst. Wir haben ja gesagt, dass die Tilemap im Spiel recht statisch ist. Nun habe ich das bei mir so gemacht, dass ich hald beim laden die ganze Map (oder bei grösseren maps) zuerst einmal einfach z.B 30x30 Tiles in einen statischen VB schiebe. Wenn du jetzt eine Map hast, die 60x60 gross ist, hast du hald 4 VB's mit jeweils 30x30 Tiles drin. Jetzt kannst du ganz einfach diesen ganzen VB rendern, ohne jedesmal jedes Tile druchgehen zu müssen. (Das heisst, dass Quadtree o.ä. schon mal überflüssig ist und wahrscheinlich auch aufwendiger). Wenn du jetzt sagen wir 120x120 haben willst, hast du auch schon recht viele VB's. Nun kannst du aber einfach jede "Untermap" darauf kontrollieren, ob sie irgendwie sichtbar ist. (das ist dann lediglich ein sehr grosses Rect, dass du überprüfen musst). Und hast du so je nachdem zwischen 1-4 gerenderten Maps.
In meinem Editor rendere ich dann hald direkt aus einem vector<vector>. Ist dementsprechend langsamer, kann aber die Tilemap direkt verändern, wenn ich dann die Map speichere und wieder in meinem Spiel lade, ist die Veränderung da und die Geschwindigkeit auch.
Du musst dann lediglich den vector mit den Tiles gespeichert lassen, damit man im Spiel die Tiles abfragen kann, was aber, wie erwähnt eigentlich keinen Aufwand bringt.

Alles klar?

Wäre noch interessant zu Wissen, wie andere das gelöst haben? Jemand da, der ne Tilemap geschrieben hat?

Zitat

Ich dachte beim Rendern eher, dass linear geprüft wird, welche Tiles alle zu rendern sind. Also nichts mit Untermaps. Dazu schaut man, wo sich die Ränder des Fensters relativ zur linken oberen Ecke der gesamten Karte befinden. So kann man mit Ganzzahldivisionen herausfinden, welches das erste zu rendernde Tile ist (links oben im Bildschirm) und geht dann in zwei For-Schleifen alle Tiles von links oben nach rechts unten durch. Ist das irgendwie zu wenig performant? Der ganze Rendervorgang läuft ja (abgesehen von nicht zu rendernden Tiles) in konstanter Zeit.

Naja. So hatte ich das auch mal. Aber das rendern alleine war einfach zu langsam. Ein statischer VB (Vertexbuffer) ist einfach extrem performant zu rendern. Viele einzelne Tiles rendern ist (mit 99%) Wahrscheinlichkeit langsamer. Im übrigen ist Rendern nicht konstant. Das ist extrem exponentiell.

Gegen eine deque spricht eigentlich nix, ausser der Name.
Sollte keine Rolle spiele, was du nimmst.

Naja. Ich habe dir nur erlärt, wie ich es gelöst habe. Die genaue Implementierung kannst du natürlich anderst machen, aber ich habe da sehr viel ausprobiert, um eine Tilemap performant zu rendern und am Schluss ist dann eben das rausgekommen.

Aber um ehrlich zu sein, weiss ich immer noch nicht, warum du überhaupt so einen Klasse haben willst. Zufügen/löschen tust du lediglich am Ende einer Map und das geht ganz einfach mit ::Resize() fertig. Dann auf jede Reihe anwenden und die Sache ist gegessen. Da es dir ja auch nicht auf die Geschwindigkeit ankommt, ist das doch keine Sache. (Vor allem, da es ja lediglich 1 - 2 mal vorkommt und das auch nur im Editor) :roll:

Solltest du eine relativ kleine, statische Tilemap haben (z.B. ein einzelner Raum) kann es sich lohnen, diesen nur einmalig auf eine Textur zu rendern und dann mit der Textur weiterzuarbeiten. Es zwingt dich ja niemand etwas neu zu rendern, was sich nicht ändert

Sowas kommt grad bei Tilemaps häufiger vor als man denkt.