How to create Iterate-Through-Edges feature for a game of life program?

kennyLiao

@quark

Hi everyone, I am trying to build a game of life application with many useful features . For latest detail, please check the latest branch. (there are too many keys to operate, so I made a video for a non-programmer friend to try)

While reading @quark's website, I noticed the game of life app can moving over edge and appear from the other side. I thought it should not be very hard to write but I was wrong and it is driving me crazy.

I guess the tricky part is handing when xx == -1 and xx == (width-1)/cellSize and yy == -1 and yy == (width-1)/cellSize and xx yy being neighbour cell's coordinates. Below is the iteration function I tried to create going through-edges feature.

Could you help me with this feature? Thanks!

In the latest branch, there are two iteration functions one named iteration()(the driving me crazy one, below) and iterationOld()(the working one but without going through-edges feature) :

This iteration() appears with no error, but it disabled previously working program.

    //(here are some of the global variables)
    // cell is a rect with width and height both 5 pixels
    int cellSize = 5;

    // canvas is carved into a grid named cells and cellsBuffer (for memory)
    int[][] cells; 
    int[][] cellsBuffer;

    // canvas's width and height deliberately set as 601 which helps me display a selecting red square when it aligns with edges
    int width =  601;
    int height =601; 


        void iteration() { 


         // save cells to cellsBuffer before every iteration
         for (int x=0; x<(width-1)/cellSize; x++) {
           for (int y=0; y<(height-1)/cellSize; y++) {
             cellsBuffer[x][y] = cells[x][y];
           }
         }

         // for every cell
         for (int x=0; x<(width-1)/cellSize; x++) {
           for (int y=0; y<(height-1)/cellSize; y++) {

             // number of its neighbours set 0 at first
             int neighbours = 0; 

             // loop around each cell to count up its living neighbours
             for (int xx=x-1; xx<=x+1; xx++) { //<>// //<>//

               if (xx == (width-1)/cellSize) {
                 xx = 0;
               }

               if (xx == -1) {
                 xx = (width-1)/cellSize-1;
               }

               for (int yy=y-1; yy<=y+1; yy++) {  

                 if (yy == -1) {
                   yy = (height-1)/cellSize-1;
                 }
                 if (yy == (height-1)/cellSize) {
                   yy = 0;
                 }

                   if (!((xx==x)&&(yy==y))) { 
                     // if a neighbour's value is 1, set count it as 1
                     if (cellsBuffer[xx][yy]==1) { 
                       neighbours ++; //<>// //<>//
                     }
                   }
                 //}
               }
             }



             // ***** apply rules to each cell

             // if it is alive, but living neighbours are less than 2 or more than 3, make it dead
             if (cellsBuffer[x][y]==1) { 
               if (neighbours < 2 || neighbours > 3) { 
                 cells[x][y] = 0;
               } else {
                 // nothing changes
               }
             } else { // if it is dead 

               // but if its living neighbour are exactly 3, then make it alive
               if (neighbours == 3 ) { 
                 cells[x][y] = 1;
               } else {
                 // nothing changes
               }
             }
           }
         }
        }

quark

The first thing I would do is simplify the limits used in the for loops. When iterating over arrays it is ALWAYS best to use the length of the array for its limits so..

// Create an array
int[][] array = new int[nx][ny];
// Doesn't matter what the values of nx and ny because we can always
// get them with
nx = array.length;
ny = array[0].length;
//  this assumes that nx and ny are both > 0 which is reasonable in this case

So the next problem is how to wrap round the edges easily. We want to avoid as many if statements inside the double loop as possible. There are two ways to deal with this.

1) Do all the cells except the edges, then do each edge in turn as a special case.

2) Assume that all the cells might be on the edge so that you use the same code for every cell.

For large arrays (1) is probably more efficient but I prefer (2) because it produces cleaner code and you are unlikely to notice any difference in speed compared with (1).

Consider a single dimension array of size 5 so the array indexes are

0 1 2 3 4

If every cell (idx) is dependent on the one in front (idx-1) and the one behind (idx + 1) then

cell 3 depends on cells 2 & 4

which is ok but

cell 0 depends on cells -1 & 1
cell 4 depends on cells 3 & 5

Which is no good because we want wrap-around i.e.

cell 0 depends on cells 4 & 1
cell 4 depends on cells 3 & 0

The solution is to use the % operator which gives the remainder after a division.

Cell in front = (idx - 1 + array_length) % array_length
Cell behind = (idx + 1 + array_length) % array_length

so we applying this to our array we have

Cell   In front   Behind
0         4         1
1         0         2
2         1         3
3         2         4
4         3         0

Putting it altogether with your code we get

//(here are some of the global variables)
// cell is a rect with width and height both 5 pixels
int cellSize = 5;

// canvas is carved into a grid named cells and cellsBuffer (for memory)
int[][] cells; 
int[][] cellsBuffer;

// canvas's width and height deliberately set as 601 which helps me display a selecting red square when it aligns with edges
int width =  601;
int height = 601; 


void iteration() { 
  // Get the dimensions of the array
  int xSize = cellsBuffer.length;
  int ySize = cellsBuffer[0].length;

  // save cells to cellsBuffer before every iteration
  for (int x = 0; x < xSize; x++) {
    for (int y = 0; y < ySize; y++) {
      cellsBuffer[x][y] = cells[x][y];
    }
  }

  // for every cell
  for (int x = 0; x < xSize; x++) {
    for (int y = 0; y < ySize; y++) {

      // number of its neighbours set 0 at first
      int neighbours = 0; 

      // loop around each cell to count up its living neighbours
      for (int dx = -1; dx <= 1; dx++) { 
        int px = (x + dx + xSize) % xSize;
        for (int dy = -1; dy <= 1; dy++) {
          int py = (y + dy + ySize) % ySize;
          if (dx != 0 || dy !=0) {
            // if a neighbour's value is 1, set count it as 1
            if (cellsBuffer[px][py]==1) { 
              neighbours ++;
            }
          }
        } // end dy loop
      }// end dx loop

      // ***** apply rules to each cell

      // if it is alive, but living neighbours are less than 2 or more than 3, make it dead
      if (cellsBuffer[x][y]==1) { 
        if (neighbours < 2 || neighbours > 3) { 
          cells[x][y] = 0;
        } else {
          // nothing changes
        }
      } else { // if it is dead 
        // but if its living neighbour are exactly 3, then make it alive
        if (neighbours == 3 ) { 
          cells[x][y] = 1;
        } else {
          // nothing changes
        }
      }
    } // end y loop
  }// end x loop
}

kennyLiao

@quark You are amazing! Thank you so much for this step-by-step newbie friendly explanation! I will study it carefully and sink it in