可以沿任意方向延伸的二维物体网格 C++

Question

创建可以在任何方向动态延伸的二维对象网格，而不在凹形形状的空白部分分配内存的最佳方法是什么？

我正在考虑让该类包含指向相邻对象（一个代表北、东、南和西）的数据成员，但这似乎不是最好的方法，而且它也缺乏指某个具有绝对值的平方（即(6,-5)）。
如果问题看起来令人困惑，请询问，我会尽力更好地解释问题。

Answer 1

只是在这里提出一个想法：

采用一个键/值容器，例如 std::map 或自平衡二叉搜索树或类似的容器。

使用 64 位整数作为密钥。使用高 32 位作为 X 坐标，低 32 位作为 Y 坐标。因此，要找到点 (x, y)，您需要查找 (((uint64_t)x) << 32) | y。

Answer 2

也许存储 std::deque 的 std::deque，其中每个内部 dequeue 对应于网格中的一行。然后，您可以存储用于每行的第一个 x 坐标。双端队列可以从前面或后面有效地增长。

请注意，它不能很好地处理间隙/孔。

查找示例：

如果您想要 (4, 2) 处的元素，您将查看起始 y 坐标。假设是-3。然后，rows[0] 将对应于 y = -3，rows[5] 将对应于 y = 2。

假设 rows[5] 的起始 x 坐标为 2。则 rows[5].cols[0] 将表示无论 (2, 2) 处是什么。我们希望 (4, 2) 处的对象有 rows[5].cols[2]。

Answer 3

我建议

const int region_size = 16; //powers of two only!  4, 8, 16, 32, 64, etc
const int region_minor = region_size-1;
const int region_major = ~region_minor;
typedef std::array<region_size, std::array<region_size, point> > region; //a 16 by 16 region
std::map<std::pair<int, int>, region> world;

point& getPoint(int x, int y) {
    std::pair<int,int> major_coords(x®ion_major, y®ion_major);
    region &r = world[major_coords]; //get region
    return r[x®ion_minor,y®ion_minor]; //return the point in this region
}
//This creates points/regions as they're needed as well.

这允许在所有维度（包括负数，这对于数组来说很难做到）和间隙上无限扩展。根据您正在做的事情，您通常希望一次触摸一个区域中的多个点，如果您有一张点图，那么这会在内存和时间上产生大量额外开销。如果您制作小区域的地图，则会使用更少的内存和时间。

Answer 4

两级结构怎么样：一个带有指向其他矩阵的指针的矩阵，您可以在需要时分配较小的矩阵。以下是 1000x1000 块的示例，每个块的大小为 100x100。矩阵被线性化以简化内存分配。如果您想要更好的粒度，您可以将其设为矩阵矩阵的矩阵。

#define N 100
#define M 1000
using namespace std;
int *mat[M*M];

void set(int x,int y,int value)
{ int hx=x/N;
  int hy=y/N;
  int lx=x%N;
  int ly=y%N;

  if(mat[hx+hy*N]==NULL)
  { mat[hx+hy*N]=new int[N*N];
  }
  mat[hx+hy*N][lx+ly*N]=value; 
}

int get(int x,int y)
{ int hx=x/N;
  int hy=y/N;
  int lx=x%N;
  int ly=y%N;
  if(mat[hx+hy*N]==NULL)
  { return -1;
  }
  return mat[hx+hy*N][lx+ly*N]; 
}

使 N、M 值为 2^k，您可以通过用位移位替换它们来避免昂贵的除法和模运算：x/ 128 是 x>>7，x*128 是 x<<7 和 x%128< /代码>是x&0x7F。 （不确定编译器是否会在内部使用 x>>7 优化 x/128）