Two-dimensional grid of objects that can spread in any direction C ++

Question

What is the best way to create a two-dimensional grid of objects that can dynamically expand in any direction without allocating memory in empty parts of concave shapes?

I was thinking that the class contains data members pointing to neighboring objects (one for North, East, South and West), but it doesn't seem like it would be the best method, and it also lacks the ability to refer to a specific square with absolute value (i.e. (6, -5)).
If the question seems confusing, ask and I will try to better explain the problem.

Answer 1

Just drop the idea here:

Take a key / value container, say std::map , or a self-balancing binary search tree or the like.

Use the integer 64 bits as the key. Use the high 32 bits as the X coordinate, and the lower 32 bits as the Y coordinates. Thus, to find the point (x, y) , you look up (((uint64_t)x) << 32) | y (((uint64_t)x) << 32) | y .

Answer 2

Perhaps save std :: deque from std :: deque, where each deqeue interval corresponds to a line in the grid. Then you can save the first x coordinate, which is used for each individual line. Deques can grow effectively in the front or back.

Please note that it will not handle gaps / holes well.

Search example:

If you need an element in (4, 2), you should look at the initial y coordinate. Let it be -3. Then the lines [0] will correspond to y = -3, and the lines [5] will correspond to y = 2.

Suppose that lines [5] have an origin x. Then the lines [5] .cols [0] will represent anything with (2, 2). We need the lines [5] .cols [2] for the object in (4, 2).

Answer 3

I would recommend

 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&region_major, y&region_major); region &r = world[major_coords]; //get region return r[x&region_minor,y&region_minor]; //return the point in this region } //This creates points/regions as they're needed as well. 

This allows infinite expansion in all dimensions (including negative, which is difficult to do with arrays) and spaces. Depending on what you are doing, you usually want to touch several points in the area at the same time, and if you have a map of points, this will be an extra overhead both in memory and in time. If you create a map of small regions, it uses less memory and time.

Answer 4

What about the structure of two levels: matrices with pointers to other matrices, you select smaller matrices when you need them. Here is an example for 1000x1000 tiles, each 100x100 in size. Matrices are linearized to simplify memory allocation. You can make it a matrix of matrix matrices if you want to have even better granularity.

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

By executing N , M 2^k , you can avoid costly division operations modulo by replacing them with bit shifts: x/128 - x>>7 , x*128 - x<<7 and x%128 x&0x7F . (not sure if the compiler will optimize x/128 with x>>7 internally)