4. Container für Tilemap

Container für Tilemap

  • N

    Wenn dieses Problem eher in das Forum C++ gehört, bitte verschieben.

    Hallo zusammen,
    Ich möchte ein Jump'n'Run programmieren. Ich hab bereits einmal eines zu einer Zeit, wo ich noch nicht so viel Ahnung von C++ hatte, geschrieben. Damals habe ich für die Tiles ein zweidimensionales statisches Array mit dem Typ meiner Tileklasse verwendet, was natürlich nicht gerade eine optimale Lösung darstellt.

    Nun möchte ich das Ganze neu machen, und zwar dynamisch. Ich habe bereits daran gedacht, verschachtelte STL-Container (für 2D) zu verwenden. In Frage kämen ausschliesslich std::vector und std::deque wegen des Random Access. Letzterer wäre hierbei vielleicht etwas besser geeignet, weil die Tilemap leichter vergrössert werden kann (durch Funktion push_front() und günstigere Speicherverwaltung), jedoch ist der Random Access leicht langsamer als bei std::vector .

    Bei beiden STL-Containern besteht aber das Problem, dass Einfügungen relativ langsam wird und einiges an Speicherplatz verschwendet wird, der sich auf 2 Dimensionen noch quadriert - im ungünstigsten Fall wird gerade einmal ein Viertel des tatsächlich benötigten Speicherplatzes genutzt. Wenn meine Tile-Klasse dann grösser wird, könnte sich das ungünstig auswirken, vor allem bei grossen Tilemaps.

    Aus diesem Grund habe ich bereits über eine eigene Containerklasse Table und deren Implementierung als Template nachgedacht. Ich würde intern ein dynamisches, zweidimensionales Array aus Zeigern auf den Templatetypen T allokieren. Dadurch, dass Zeiger und nicht die Objekte selber verwaltet werden, sind interne Operationen wie Löschungen, Einfügungen und Reallokationen weniger schwerfällig. Zudem könnte ich die Funktionen InsertRow() , InsertCol() , RemoveRow() , RemoveCol() bereitstellen, die einiges vereinfachen würden.

    Andererseits wäre für den RandomAccess neben einer Funktion Table::At(unsigned int x, unsigned int y) auch ein operator [] nützlich. Allerdings ist es relativ mühsam, den Indexoperator dafür zu überladen, das ja folgendes erstes Konstrukt leider nicht möglich ist:

    /* 1. */  Table[x,y]
/* 2. */  Table[x][y]

    Die zweite Möglichkeit ist dagegen schon realisierbar, allerdings nur über eine Dummy-Struktur. Da gibt es auch keine bessere Möglichkeit ( operator () und At() gefallen mir eben nicht so ;)), oder?

    Gibt es triftige Gründe, die gegen eine solche Umsetzung sprechen? Sind die STL-Container hierbei vorteilhafter (Performance ist nicht extrem entscheidend, Random Access sollte einfach schnell sein)? Falls jemand bereits ein Jump'n'Run oder ein anderes Spiel mit ähnlichem 2D-Aufbau realisiert hat, wäre ich froh, wenn dieser seine Implementierung präsentieren könnte.

    0
  • K

    was du suchst, sind quadtrees. Die haben schnellen zugriff, sind immer erweiterbar, und brauchen minimalen Platz. Um die allerdings zu verstehen, sollte man sich aber erstmal Binäre Bäume anschauen, dann eine Umsetzung für 2D Spiele. Moderne 3D spiele nutzen meistens Octrees, also das gleiche in 3 Dimensionen. Ein Spiel, wo man auch die Datenstruktur erkennen kann, heißt Sauerbraten. Ich hab auch wohl mal 2D Bilder gesehen, an denen man die Struktur erkennen konnte, aber die weiß ich momentan nicht, wo man diese finden kann.

    0
  • R
    Mod

    mehr als ein array bzw vector brauchst du nicht.

    direkt drauf arbeiten willst du vermutlich auch nicht, sondern brauchst zusatzfunktionen
    also hast du etwas in der art von

    class CMap
{
std::vector<CSprite> m_Data;
int m_SizeX,m_SizeY;
public:
CMap(int X,int Y):m_SizeX(X),m_SizeY(Y){m_Data.resize(X*Y);}

CSprite& Sprite(int X,int Y){assert(X>=0);assert(X<m_SizeX)...  return m_Data[X+Y*m_SizeX];}
};
    0
  • K

    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.

    0
  • R
    Mod

    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

    0
  • N

    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ür std::vector , aber lohnen sich die Vorteile gegenüber std::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).

    0
  • K

    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.

    0
  • N

    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).

    0

  • 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.

    0
  • N

    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?

    0
  • N

    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?

    0
  • R
    Mod

    http://www.spieleprogrammierer.de/index.php?option=content&task=view&id=50&Itemid=2

    0
  • N

    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 🙂

    0
  • Administrator

    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

    0
  • N

    Danke für den Tipp 🙂

    Vermutlich werde ich es doch mit std::vector oder std::deque machen, alle finden das besser 😉

    Was mich allerdings noch interessieren würde: Welcher der beiden STL-Container ist denn besser geeignet? std::deque hat 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 mit std::deque , oder wieso spricht sich niemand wirklich dafür aus?

    0
  • ?

    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

    0
  • R
    Mod

    Nexus schrieb:

    Danke für den Tipp 🙂

    Vermutlich werde ich es doch mit std::vector oder std::deque machen, alle finden das besser 😉

    hier 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::deque hat halt den Vorteil von Einfügungen am Anfang

    das 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.

    0
  • D

    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

    0
  • ?

    *hust* boost::multi_array

    0
Anmelden zum Antworten