データ構造2D/3Dタイル配列C++

Question

新しいゲームのレベルエディタをプログラミングしています。問題は、私は自分のデータを格納するためにどのような構造を使うべきかわからないということです。

タイルベースのマップエンジンで、x座標とy座標とその位置のタイルのIDを使用します。

私は複数のレイヤーを持っています、マップはサイズ変更可能ですので、配列は私にいくつかの問題を引き起こす可能性があります。そのため、そのケースのstd :: vectorを選択しました。 多くの過負荷を防ぐために、タイルを追加するだけです。誰かがそれを配置したときにタイルが追加されます。タイルがなくなるとベクトルサイズがゼロになり、タイルが増えれば増えます。

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

そして、私のベクトル：

std::vector<tile> tiles; 

事は、私がそのx軸とy位置のタイルがすでにありますかどうかを確認する必要が新しいタイルを追加する前に、あります。

// 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; 
} 

私の問題は、すべての配置のタイルのため、私が先頭に高速ですが、いくつかのタイルが置かれた後、実際にお尻の痛みを取得し、全体のベクトル、ループスルーしなければならないこと、です。

これまでの私のアプローチは大丈夫だと思いますか、それとももっとスマートでパフォーマンスの高いものがありますか？

Answer 1

なぜ複数のベクターを使用しないのですか？基本的に、ベクトルのベクトルを持つことによって成長可能な2-Dベクトルを作成し、[]演算子をオーバーロードして、ベクトルサイズにその要素が含まれているかどうかをチェックし、できればその要素あなたのデフォルトの "タイル"が何であっても構いません。これにより、通常のベクトルのようにほぼO（1）ルックアップが可能になります。それ以外の場合は、最大col /行の距離に数式を使用して、2次元配列などの2次元から1次元への変換でO（1）ルックアップを行うことができます。

これは私が考えているものです：

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; 
} 

編集：

[X] [Y] == nullptr別のユーザーが指摘したように、あなたはまた、ポインタを使用することができますし、タイルかどうかをチェック。代わりに！

Answer 2

ほとんどの場合、（x、y）の読み込みを行う場合、おそらく行列が必要です（ベクトルのベクトルまたは配列の配列を使用する必要があります） 。

タイル上のインデックス付きアクセスと簡単な反復が必要な場合は、おそらく2つのデータ構造内にデータを保持します。ベクトル内のタイルへのポインタを持つ2次元マップを簡単に実装することができるはずです。最初は空の、遅延ロードされた（x、y）アクセスです（データの安全性について覚えておいてください）。

例えば検討：

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; 
}; 

（簡単なコードの例に拡張コメント：ベクトルとマップの両方がそれのコピーを保持しながらデータが、ヒープ上に保持されている - 多分より容易に除去するために改善することができる）

を