如何存储允许O(1)随机访问的3d地图？(C++)

Question

我目前正在为“我的世界”制作一个C++客户机/机器人，我想知道是否有一种方法可以使用允许使用STL或Qt库的有效随机访问的数据结构来存储世界地图。

世界总是256高，但在x和z坐标上可以是无限大的。它被发送到包含16x256x16块的数据包中。现在，我正在将16x256x16段中的块存储到数组中，因为大小永远不会改变，我将这些部分存储到一个stl映射中，使用x和z作为键。

问题是，我目前正在研究人工智能，我需要访问地图很多，所以我想知道是否有更好的，我可以存储它，以提高访问效率。我不关心添加或删除元素的效率。它也不需要被分类。

Answer 1

如果您想使用STL std::unordered_map，这将给您提供O(1)

Answer 2

如果采用Qt方式，您可以使用QHash作为std::unordered_map的替代方案，使用稍微方便一些的API。此外，如果在给定的coord中可能有多个对象，则为QMultiHash。

您可以编写QHasht<Coord3d, Data>和uint qHash(Coord3d)函数，这是QHash所需要的。

struct Coord3d {
  uint x, y, z;
};

uint qHash(Coord3d & c) {
  uint h = 0;
  uchar * p = (uchar*)&c;
  for (uint i = 0; i < sizeof(Coord3d); ++i)
    h = 31 * h + p[i];
  return h;
}

另外，如果您必须遍历相邻的块，则可能需要额外的内存来保存指向所有相邻块的指针，这样您就不必查找它们。您可以轻松地使用每个块的相邻块指针实现自己的查找。它可能比hashmap更有利于人工智能，并且对于路径查找这样的典型任务也会更快。