1
\$\begingroup\$

I want to write a function which will return all possible/valid 'X' moves around my Target cell depending on it position inside the following two dimensional array.

X X X
X T X
X X X

But my 2 concerns are:

  1. the performance because my "game field" will be 1000x1000 cells and each cell must be checked in the game turn. So creating 1,000,000 vectors (in one turn) is a bad idea? Maybe I should use a different data structure for it?

  2. logic inside the function is not too complicated?

    enum dir {topL, top, topR, l, r, botL, bot, botR};
    
    std::vector<dir> neighborhood(int x, int y, int size)
    {
        std::vector<dir> direction;
        direction.clear();
    
        if(x < size -1){direction.push_back(bot);}
        if(y < size -1){direction.push_back(r);}
        if(x < size -1 && y < size -1){direction.push_back(botR);}
        if(x > 0){direction.push_back(top);}
        if(y > 0){direction.push_back(l);}
        if(x < size -1 && y != 0){direction.push_back(botL);}
        if(x > 0 && y < size -1){direction.push_back(topR);}
        if(x > 0 && y > 0){direction.push_back(topL);}
        return direction;
    }
    
\$\endgroup\$
  • \$\begingroup\$ Can you explain your question a little bit more detailed? Why would you create 1mio vectors, when you just want to return all adjacent positions? Why would you even check the neighbor positions for EACH cell, EACH game cycle? What's the intend of this? \$\endgroup\$ – DNKpp Dec 29 '17 at 12:07
  • \$\begingroup\$ Hi, each cell can do action depends on it surroundings. Its similar like in the Game of live. So my function return possible moves for each cell and protect it to not do action out of bounds of the game field array. When the game start in the each turn every cell do action in their surroundings. for example i must to be sure that cell (0,0) can go only to the right, the bottom or the bottom right, so i decide to return vector of the possible moves for the each cell. But it looks like its not good idea to create temporary vector for each cell in each turn. \$\endgroup\$ – P.Doe Dec 29 '17 at 13:27
  • \$\begingroup\$ One possible improvement is, to store the possible directions in an unsigned integer (with bit operations) instead of more heavy std::vector (which requires heap allocation). Take this as an example. pastebin.com/J9VxV7SZ Here you get the same informations, with less performance issues. Hope it helps. \$\endgroup\$ – DNKpp Dec 29 '17 at 13:45
  • \$\begingroup\$ What you need to do is create a neighbor array that you can apply for all cells. neighbors={-1000-1,-1000,-1000+1,-1,1,1000-1,1000,1000+1}. These are the memory offsets that represents all neigbors. Access neigbors as cellIndex+neighbors[i]. To avoid reading out of bounds for cells on the edge of the playing field, simply add a border to your field—define the array to be 1002x1002, where you never use the cells on the edges. Fill those with suitable bounday conditions and never access them except as part of the neighborhood of a cell in the play field. \$\endgroup\$ – Cris Luengo Jan 1 '18 at 19:53
  • \$\begingroup\$ Hey @CrisLuengo please do not answer questions in the comments. Instead write an answer. Thanks! \$\endgroup\$ – Vogel612 Apr 20 '18 at 8:25
3
\$\begingroup\$

You can use 8 bit memory (char in c/c++) to precompute possible direction of movement for each of the cells and use bitwise operation to improve performance:

//bit1: top direction, bit2: topright directon, bit3: rigth, and so on....
std::array<char, 1000000> c;    //array, this will be our playground
c.assign(255);                  //to set all ones in all cells
c[0] = c[0] & 0x38;             //top left cell representing 00111000
c[999] = c[999] & 0xE;          //top right cell
c[900000] = c[900000] & 0xE0;   //bottom left cell
c[999999] = c[999999] & 0x83;   //bottom right cell

for(int i=1; i<999; i++)               //all top edge cells except corners
   c[i] &= 0x3E;
for(int i=1999; i<999999; i += 1000)   //all right edge cells except corners
   c[i] &= 0x8F
for(int i=9999000; i<999999; i ++)     //all bottom edge cells except corners
   c[i] &= 0xE3
for(int i=1000; i<999000; i += 1000)   //all left edge cells except corners
   c[i] &= 0xF8

then you can use these hex values to quickly determine if your cell is at corners, edges or in the middle example:

  if(! c[i] ^ 0x38){
       //this cell is left corner
    }

Because bitwise operators are very fast, you will see great improvement in performance.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.