Структура данных 2d/3d массив плиток C++

Question

Я программирую редактор уровней для новой игры. Проблема в том, что я не уверен, какую структуру использовать для хранения моих данных.

Это движок карты на основе плитки с использованием координат x и y и идентификатор для плитки в этом положении.

У меня есть несколько слоев, карта может быть изменена, поэтому массив может вызвать у меня некоторые проблемы, поэтому я выбрал для этого случая std :: vector. Чтобы предотвратить большую перегрузку, я добавляю только плитку, когда кто-то ее помещает, поэтому размер вектора равен нулю, если нет фрагментов и увеличивается количество размещенных фрагментов.

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

И мой вектор:

std::vector<tile> tiles; 

Дело в том, прежде чем добавить новую плитку мне нужно проверить, если уже есть плитка на этой х- и у-положении.

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

Почему бы не использовать несколько векторов? Вы могли бы по существу создать растущий двумерный вектор с помощью вектора векторов, а затем перегрузить оператор [], чтобы сначала проверить, может ли векторный размер содержать этот элемент (возвращать false, если нет), и если это возможно, проверьте, является ли этот элемент не является сконструированной величиной (независимо от вашей «плитки» по умолчанию). Это позволило бы найти почти O (1), как в обычных векторах. В противном случае вы можете использовать формулу для максимального расстояния между столбцами/рядами и выполнять поиск O (1) таким образом с некоторыми преобразованиями 2-D-1-D, например, в 2-D массивах.

Это то, что я имею в виду:

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:

Как другой пользователь указал, вы можете также использовать указатели и если проверить плитки [х] [у] == nullptr; вместо!

Answer 2

Структура данных, которая должна использоваться, должна зависеть в основном от прецедентов: если вы делаете в основном (x, y), то, возможно, вам нужна матрица (будь то вектор векторов или просто массив массивов) ,

Если вам нужен индексный доступ и простая итерация поверх плиток, возможно, данные хранятся в двух структурах данных. Вы должны иметь возможность легко реализовать 2d-карту с указателями на плитки в векторном - изначально пустым, лениво загруженным (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; 
}; 

(дополнительный комментарий с кратким примером кода: данные хранятся в куче, в то время как вектор и карта держать его копии - возможно, можно было бы улучшить для более легкого удаления)