数据结构二维/三维瓦片阵列C

Question

我正在为一款新游戏编写关卡编辑器。问题是，我不确定用什么结构来存储数据。

它是一个基于平铺的地图引擎，使用x和y坐标以及该位置的平铺id。

我有多层，地图是可调整大小的，所以数组可能会给我带来一些麻烦，这就是为什么我选择了d::向量。为了防止大量过载，我只在有人放置瓷砖时添加一个瓷砖，所以如果没有瓷砖，矢量大小为零，并且放置的瓷砖越多，矢量大小就越大。

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

为什么不使用多个向量？基本上，你可以通过向量向量来创建一个可增长的二维向量，然后重载[]操作符，首先检查向量大小是否可以包含该元素（如果不能，则返回false），如果可以，则检查该元素是否不是构造值（无论默认的“tile”是什么）。这将允许几乎O（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;
}

编辑：

正如另一位用户指出的，您还可以使用指针并检查tiles[x][y]==nullptr；相反

Answer 2

要使用的数据结构主要取决于用例：如果您主要进行（x，y）读取，那么可能需要一个矩阵（通过向量向量，或者只是数组数组）。

如果需要索引访问和简单的分片迭代，可以将数据保存在两个数据结构中。你应该能够很容易地实现一个2d地图，带有指向vector中分片的指针——最初是空的，在（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;
};

（带有简短代码示例的扩展注释：数据保留在堆中，而向量和映射都保留其副本-也许可以改进以更容易删除）