Datenstruktur 2d/3d Array von Fliesen C++

Question

Ich programmiere einen Level-Editor für ein neues Spiel. Das Problem ist, ich bin nicht sicher, welche Struktur zum Speichern meiner Daten verwendet werden soll.

Es ist eine Kachel-basierte Karten-Engine, die x- und y-Koordinaten und eine ID für die Kachel an dieser Position verwendet.

Ich habe mehrere Ebenen, die Größe der Karte ist veränderbar, daher kann ein Array mir Probleme bereiten, deshalb habe ich für diesen Fall einen std :: vector gewählt. Um eine große Überlastung zu vermeiden, füge ich nur eine Kachel hinzu, wenn jemand sie platziert, also ist die Vektorgröße Null, wenn keine Kacheln vorhanden sind, und erhöht sich, je mehr Kacheln platziert werden.

struct tile { 
     unsigned short tile_id; 
     unsigned short tile_x; 
     unsigned short tile_y; 
    }; 

Und mein Vektor:

std::vector<tile> tiles; 

Die Sache ist, bevor Sie eine neue Kachel hinzugefügt ich überprüfen müssen, ob es bereits eine Kachel an dieser x- und y-Position.

// Returns true/false if there is a tile at given position or not 
bool Layer::has_tile_at(unsigned short x, unsigned short y) { 

    unsigned int i; 
    for (i = 0; i < tiles.size(); i++) { 
     if (tiles[i].tile_x == x && tiles[i].tile_y == y) 
     return true; 
    } 

    return false; 
} 

Mein Problem ist, dass für jede Kachel platziert, muss ich Schleife durch den ganzen Vektor, der schnell am Anfang, aber wirklich ein Schmerz in den Arsch bekommt, nachdem einige Fliesen gelegt wurden.

Glaubst du, mein Ansatz ist soweit in Ordnung, oder ist etwas intelligenter und leistungsfähiger?

Answer 1

Warum nicht mehrere Vektoren verwenden? Sie könnten im Wesentlichen einen anwachsenden 2-D-Vektor erzeugen, indem Sie einen Vektor von Vektoren haben, dann überladen Sie den [] -Operator, um zuerst zu prüfen, ob die Vektorgröße dieses Element enthalten könnte (wenn nicht, gibt sie zurück), und wenn möglich, prüfen Sie, ob dieses Element vorhanden ist ist kein konstruierter Wert (was immer Ihre Standard-Kachel sein mag). Dies würde nahezu O (1) Lookup wie in regulären Vektoren ermöglichen. Andernfalls können Sie eine Formel für Ihre maximale Entfernung zwischen Farbe und Zeile verwenden und eine O (1) Suche auf diese Weise mit einigen 2D- zu 1-D-Konvertierungen durchführen, wie in 2D-Arrays.

Das ist, was ich denke:

vector< vector<tile> > tiles; 

bool::Layer has_tile_at(unsigned short x, unsigned short y) { 

    if (tiles.size() <= x) { 
     return false; 

    } else if (tiles[x].size() > y) { 
     if (tiles[x][y] != tile()) { 

      return true; 
     } 
    } 

    return false; 
} 

Edit:

als ein anderer Benutzer darauf hingewiesen, auch Zeiger verwenden könnte und prüfen, ob Fliesen [x] [y] == nullptr; stattdessen!

Answer 2

Die zu verwendende Datenstruktur sollte hauptsächlich von den Anwendungsfällen abhängen: Wenn Sie hauptsächlich (x, y) lesen, dann benötigen Sie vielleicht eine Matrix (sei es über einen Vektor von Vektoren oder nur Array von Arrays) .

Wenn Sie indizierten Zugriff UND einfache Iteration über Kacheln benötigen, halten Sie die Daten möglicherweise in zwei Datenstrukturen. Sie sollten in der Lage sein, einfach eine 2D-Karte mit Zeigern auf Kacheln innerhalb von Vektor zu implementieren - anfangs leer, faul geladen auf (x, y) -Zugriff (erinnern Sie sich an Datensicherheit!).

zum Beispiel vor:

class Map 
{ 
public: 
    void addTile(std::shared_ptr<Tile> tile) 
    { 
    m_tiles.push_back(tile);    // should probably remove old elements at (x,y) from the vector 
    m_map[{tile->x, tile->y}] = tile; // overwrites whatever was stored in there! 
    } 

    std::shared_ptr<Tile> getTile(int x, int y) 
    { 
    return m_tilesMap[{x, y}];   // if no tile there, returns default ctor-ed shared_ptr: nullptr 
    } 

private: 
    std::vector<std::shared_ptr<Tile>> m_tiles; 

    using Index2D = std::pair<int, int>; 
    std::map<Index2D, std::shared_ptr<Tile>> m_tilesMap; 
}; 

(erweiterter Kommentar mit einem kurzen Codebeispiel: Daten werden auf dem Heap gehalten, während sowohl Vektor- als auch Kopien davon halten Karte - vielleicht für eine leichtere Entfernung verbessert werden könnte)