Container für Tilemap
-
eigentlich reicht ja schon ein array mit short oder char, dann hat man es ganz platzsparend, denn mehr als 256 Sprites wird man alleine ja wohl kaum zusammenpixeln. Aber wenn darum geht datenstrukturen zu lernen, die für die Spieleentwicklung von wichtiger Bedeutung sind, dann sollte man sich den Baum doch schon mal anschauen, ist jedenfalls auch Teil eines jeden Informatikstudiums.
-
viel wichtiger als random datencontainer zu lernen ist den am besten passenden zu nutzen um zum ziel zu gelangen. ansonsten waeren AABB, KD, BSP etc. auch moeglich. aber genau so wenig effizient wie quadtrees in diesem fall wo ein array optimal laeuft.
overengineering ist echt nichts positives.nichts gegen's lernen, aber wenn jemand einfach nur ein jump'n run machen will sind die ziele anders
-
Vielen Dank für die Vorschläge.
Im Moment finde ich QuadTrees auch ein bisschen übertrieben, zumal die Tiles ja alle gleich gross und rasterförmig angeordnet sind. Random Access ist bei einem Array sicher auch schneller als bei den Bäumen und die Implementierung ist einfacher. Deshalb werde ich eher eine sequenzielle Möglichkeit nutzen - eventuell befasse ich mich später ausführlich mit QuadTrees.
Das mit der Abwälzung auf eine Dimension habe ich mir auch schon überlegt; falls ich einen eigenen Container nutzen würde, könnte ich das intern auch so regeln (spielt ja eigentlich keine grosse Rolle, bei 2D-Arrays ist das Prinzip aber sofort klar).
Das Problem ist jedoch, wenn man z.B. bei einem 1D-Vector, der eine Tabelle aus Tiles repräsentiert, eine Zeile einfügen will, kann man n Einfügungen an n verschiedenen Stellen im Array durchführen - da wird einiges umkopiert. Bei meiner eigenen Lösung wären es wenigstens nur Pointer, und die Reallokation fände nur einmal statt.
Und was den unnötigen Speicherverbrauch der STL-Container betrifft, der sich vor allem bei grossen Tileklassen und grosser Dimension des Containers auswirkt, hab ich ja schon etwas dazu gesagt.
Wie stehts eigentlich mit
std::deque? Natürlich gilt für obige Nachteile das Gleiche wie fürstd::vector, aber lohnen sich die Vorteile gegenüberstd::vector(günstigere Speicherverwaltung (nicht immer vollständiges Umkopieren erforderlich), Einfügung am Anfang in konstanter Zeit)?@ rapso: Mit AABB etc. meinst du Kollisionsabfragetechniken, oder? Das hat aber mit der Tilemap nicht direkt etwas zu tun (evtl. später, mit Spieler).
-
Noch mal eine Frage, wozu genau willst du eigentlich, dass da etwas dynamisch ist? Die Levelgröße ändert sich doch für gewöhnlich nicht während des Spielens. Wenn während des Spielens ein paar blöcke kaputt gehen, ändert das auch nichts an der Größe, da sind immer noch normale Arrays am besten. Wenn du das level aus einer Datei laden möchtest, dann legst du das array halt mit new an.
-
Krux schrieb:
Wenn du das level aus einer Datei laden möchtest, dann legst du das array halt mit new an.
Genau, und dann ist ja es wieder dynamisch (auf dem Heap).
Wenn du dynamisch im Bezug auf die Flexibilität gemeint hast: Ich werde einen Level-Editor haben, mit dem es auch möglich sein soll, die Grösse der Tilemap zur Laufzeit zu verändern (d.h. entweder Dimension explizit angeben oder an den Rändern vergrössern/verkleinern).
-
In dem Fall würde ich einen std::vector nehmen, und selbst "reinindizieren" (also mit vec[X + Y * Width]). Und beim Vergrössern/Verkleinern einfach nen neuen Vektor anlegen, und den Inhalt mit Hand mit den neuen Indizes rüberkopieren.
vector<vector<Blubb> > finde ich persönlich halt eher doof. Von der Geschwindigkeit her wird der Unterschied allerdings vermutlich minimal sein.
p.S.: was den Indexoperator angeht, so könntest du den überladen so dass er einen Vektor2D (oder wie deine 2D Vektorklasse auch immer heisst, ggf. auch std::pair<int, int>) als Parameter nimmt.
-
hustbaer schrieb:
p.S.: was den Indexoperator angeht, so könntest du den überladen so dass er einen Vektor2D (oder wie deine 2D Vektorklasse auch immer heisst, ggf. auch std::pair<int, int>) als Parameter nimmt.
Ja, aber überladen könnte ich ihn nur für meine eigenen Containerklasse. Dann müsste man trotzdem einen expliziten Konstruktoraufruf aufschreiben (Komma-Ausdrücke werden ja nicht standardkonvertiert):
Tilemap[Vector2D(53, 22)]Dann schreib ich lieber
Tilemap.At(53, 22)oder noch lieber
Tilemap[53][22], was dann aber wieder mit Mehraufwand (Dummy-Struktur) verbunden wäre...
Aber wie ist es mit
std::deque, wird das überhaupt jemals verwendet? Oder nur bei sehr grossen Containern, wo man Reallokationen klein halten muss?
-
Hat jemand selber schon ein tilebasiertes Spiel geschrieben? Wenn ja, wäre ich froh, wenn dieser seine Implementierung aufzeigen könnte. Ich nehme an, standardmässig macht man es mit
std::vector, oder?
-
-
Ich hab mir den Quellcode von Blocks 5 mal angeschaut, und wenn ich es richtig gesehen habe, wird es dort mit einem statischen Array gelöst, was ja aufgrund der konstanten Dimension auch gut ist. Für meine Zwecke ist dieser Ansatz hingegen weniger geeignet.
Gut, ich werde das Problem mal im Spieleprogrammierer-Forum stellen. Wahrscheinlich fahre ich allerdings mit meiner eigenen Tabellenklasse nicht schlecht
-
Darf ich einen Tipp geben? Probiers zuerst einmal mit einem std::vector oder std::deque und schau dir dann den Speicherverbrauch an. Optimiere erst später, denn ich denke nicht, dass hier das grösste Problem sein wird
Grüssli
-
Danke für den Tipp
Vermutlich werde ich es doch mit
std::vectoroderstd::dequemachen, alle finden das besserWas mich allerdings noch interessieren würde: Welcher der beiden STL-Container ist denn besser geeignet?
std::dequehat halt den Vorteil von Einfügungen am Anfang und günstigerer Speicherverwaltung, dafür ist er etwas langsamer (was aber nichts ausmachen dürfte). Haben die wenigsten Erfahrung mitstd::deque, oder wieso spricht sich niemand wirklich dafür aus?
-
Hallo
Ich habe bisher noch nie mir std::deque gearbeitet und würde dir daher auch zu std::vector raten. Wie Dravere aber bereist schrieb, solltest du dir nicht so große Gedanken darum machen, weil das doch wahrscheinlich nicht die performancekritische Stelle deines Programms wird.
chrische
-
Nexus schrieb:
Danke für den Tipp
Vermutlich werde ich es doch mit
std::vectoroderstd::dequemachen, alle finden das besserhier im thread fanden doch so ziemlich alle vector besser.
Was mich allerdings noch interessieren würde: Welcher der beiden STL-Container ist denn besser geeignet?
std::dequehat halt den Vorteil von Einfügungen am Anfangdas ist auch der einzige vorteil, den du alle zeit mal hast. 99% der zeit wirst du vermutlich was anderes als einfuegen machen, wo std::vector von vorteil ist.
günstigerer Speicherverwaltung
wo hast du das gehoert? wie kann ein simples array im speicher mit 1byte/element schlechter sein, als ne ansammlung von nodes die (ohne optimierungen) 25byte/element haben(2*pointer auf child,pointer auf parent,pointer auf objekt,memoryallocator header von 4byte+memoryallocatorheader fuer das eigentliche element + 1byte fuers element) schlechter sein?
dafür ist er etwas langsamer (was aber nichts ausmachen dürfte). Haben die wenigsten Erfahrung mit
std::deque, oder wieso spricht sich niemand wirklich dafür aus?weil man mit ein bisschen nachdenken oder auch nur in referenzbuechern nachschlagen erfaehrt, dass dequeue (genau wie map) sehr heavy sind und man sie benutzt wenn die lightweight alternativen viel zu schlecht sind.
-
Dravere schrieb:
Darf ich einen Tipp geben? Probiers zuerst einmal mit einem std::vector oder std::deque und schau dir dann den Speicherverbrauch an. Optimiere erst später, denn ich denke nicht, dass hier das grösste Problem sein wird
Grüssli
Ich kann dir/ihm wirklich sagen, dass das Performance Problem bei einer Tilemap wirklich wo anders liegt. Das reine durchgehen von 2 vectoren ist im Relese ziemilich schnell. Jedoch das rendern von einem Tile nach dem anderen kann noch optimiert werden, da eine Tilemap ja statisch ist. Das vorgehen, wie ich das gelöst habe gibt es hier:
http://www.spieleprogrammierer.de/phpBB2/viewtopic.php?p=109314#109314
-
*hust* boost::multi_array
