Something's wrong with my Game of Life algorithm, I just can't figure out

I'm not 100% sure exactly what you are doing and I don't know Python, but years ago I did write a game of life program. One common way of implementing wrapping for stuff like this is to use the modulus operator. For instance say you have a range of 0 to 10 by 0 to 10. You can use the formula:

(location + 10) mod 10

So say you are at (0,0) and you want to address (x-1,y-1) .... That's ((-1+10) mod 10) for each coordinate which gives you (9,9)
Now let's say you are at (9,9) and you want to address (Y+1,Y+1) ..... That's ((10+10) mod 10) for each coordinate which gives you (0,0)

So if you do that the wrapping part should be super simple.

Your algorithm is only iterating over the cells from index 1 through index GW/GH-1, exclusive. Don't you mean to be iterating over *every* cell?

Once you fix that issue, you will have an out-of-bounds issue unless you calculate the true array index of the adjacent cells. Pre-calculating the previous and next Y coordinates once per Y loop, and the previous and next X coordinates once per X loop, would be sufficient. For example (again, I barely know python)...

    for j in xrange(0, GH):
      # If you stick to strictly positive values, modulus works fine.
      jAfter  = (j + 1) % GH
      # Most languages have bad behaviour with negative numbers and the modulus operator,
      # so I use this construct to avoid that unnecessary testing.
      jBefore = GH-1 if j == 0 else j-1

      # and then when used, e.g. in the "kill cell" condition...
      cellmaps[curr][j][i] &= ~1
      alive_cells -= 1
      cellmaps[curr][jBefore][iBefore] -= 2
      cellmaps[curr][jBefore][i]       -= 2
      cellmaps[curr][jBefore][iAfter]  -= 2
      cellmaps[curr][j      ][iBefore] -= 2
      cellmaps[curr][j      ][iAfter]  -= 2
      cellmaps[curr][jAfter ][iBefore] -= 2
      cellmaps[curr][jAfter ][i]       -= 2
      cellmaps[curr][jAfter ][iAfter]  -= 2

Last of all; if you have two copies of the tile field in the array cellmaps, why are you deepcopying the current one before every iteration? Why aren't you just swapping the values of prev and curr?

3 hours ago, Gnollrunner said:

I'm not 100% sure exactly what you are doing

Essentially I'm working my way up the ladder, trying new things and seeing if I find something better than what I got, and also learning more stuff (with this I learned to manipulate bits, which I've been kind of avoiding for years). I'm not unhappy with what I already got (my actual project is in Love2d). It's pretty fast for what I was expecting, but I'm just testing more options.

The modulus stuff is certainly something to keep in mind. Maybe I'll try it with the first algorithm I wrote, which was a bit slower, to see if it makes a significant difference. I suppose it should. I do have a feeling the extra edges don't make it faster than that kind of calculations and checks.

1 hour ago, Wyrframe said:

Your algorithm is only iterating over the cells from index 1 through index GW/GH-1, exclusive. Don't you mean to be iterating over *every* cell?

No, because the outer edges are just mirrors of the inner edges of the opposite sides (and like I said, the other algorithm works fine with it - and this one works vertically, it just somehow doesn't horizontally). If the cellmap is 20x20, including the outer edges, at every iteration row 19 is copied over to row 0, and row 1 is copied to row 20, and the same for the sides. So when a cell gets lit up at row 1, it gets mirrored on row 20, or if it gets lit up at row 19 it gets mirrored on row 0.

I'm not supposed to actually iterate over those. And besides, it does indeed go out of range of the array too if I try.

1 hour ago, Wyrframe said:

Last of all; if you have two copies of the tile field in the array cellmaps, why are you deepcopying the current one before every iteration? Why aren't you just swapping the values of prev and curr?

Swapping them works for the other algorithm, but not for this one, because on this one I'm switching bits in the adjacent cells and they'd get altered on one array, but not the other. So after switching, all the neighbor information is on the other array (on the other algorithm I check for neighbors on the fly, without storing that info). Also after switching, doing -2 or +2 on neighbor cells, would give me the wrong results, because the other array had been changed, not this one. So if the neighbor cell is 2 on prev, it's still 0 on curr, and if I subtract 2 there it's goes negative instead of making it 0. That would break the check for non-zero cells (that skips all others, which is the strength of algorithm):

if cellmaps[prev][j][i] != 0:

An alternative might be to have 8 more lines to alter both arrays, perhaps. Not sure if that works, I haven't tried. Otherwise I really have to make a copy on this one (and a deepcopy too because python arrays are copied by reference by default, and a shallow copy (a = b[:]) doesn't work either, because the inner arrays would go by reference).

I spent an afternoon hitting my head on that until I realized why I really had to make a copy of the array.

Despite that, though, that algorithm still seems slightly faster than the others I tried.

'k, I'm understanding now what swap_borders() is supposed to be doing. I don't think it has that effect, though. What you effectively have is a 2-cell wide semi-inert border at all four sides that you're trying to use to "pass" neighbourhood information from one side of the board to the other. By doing it like that you're causing an artificial 1-cycle lag in information propogation from one side of the board to the other, whereas true wraparound does not have that problem. If you're seeing it work in one axis, my best guess is that it is doing so as an artefact or a misinterpretation of your test data.

Try setting up a figure-8 or any other N oscillator centered on a supposedly wrapping boundary.

32 minutes ago, Master thief said:

Essentially I'm working my way up the ladder, trying new things and seeing if I find something better than what I got, and also learning more stuff (with this I learned to manipulate bits, which I've been kind of avoiding for years). I'm not unhappy with what I already got (my

Well I'm just saying, the game of life isn't so complex in it's basic form. You just loop though one matrix one cell at a time, check the 8 cells around it and write to a second matrix. Then you do the same thing again back to other way. It's super simple. You have a comment "// inform neighbors this cell is dead", As far as I know you don't need to do that. Each cell just lives, dies or is born on it's own based on it's neighbors. Perhaps you are doing something beyond the basic game of life algorithm.....In any case whatever you are doing, for wrapping using a mod function is almost always the easiest way.

5 minutes ago, Gnollrunner said:

You have a comment "// inform neighbors this cell is dead", As far as I know you don't need to do that

He's deliberately trying two algorithms; "gen_sum()" is the traditional count-and-test that you're used to; "gen_bits()" is a different one which actively updates a cell's neighbour's "neighbour" counts each time a cell dies or is reborn.

14 hours ago, Wyrframe said:

What you effectively have is a 2-cell wide semi-inert border at all four sides that you're trying to use to "pass" neighbourhood information from one side of the board to the other. By doing it like that you're causing an artificial 1-cycle lag in information propogation from one side of the board to the other,

The SUM (gen_sum()) algorithm with debug mode off (which hides the outer borders):

It didn't work at first, but only because I had forgotten to call swap_borders() at the beginning.

I overlooked that you mentioned trying a figure-8 before I made that gif, but I also tried that one now and it worked as well.

14 hours ago, Gnollrunner said:

Well I'm just saying, the game of life isn't so complex in it's basic form. You just loop though one matrix one cell at a time, check the 8 cells around it and write to a second matrix. Then you do the same thing again back to other way. It's super simple. You have a comment "// inform neighbors this cell is dead", As far as I know you don't need to do that. Each cell just lives, dies or is born on it's own based on it's neighbors. Perhaps you are doing something beyond the basic game of life algorithm.....In any case whatever you are doing, for wrapping using a mod function is almost always the easiest way.

The problems begin when you go a step further and want to have a bigger array. And yes, I am beyond the basic implementation. First time I implemented this game was back in 2014 or so. I use it as test projects to learn new languages and frameworks, but there's also a lot to learn from it. But I reached a point where I need faster algorithms so I can have better frame rates in a BIG grid of cells (I'm using python scripts just for testing algorithms, and this one in particular is a simplified version of another one where I'm also timing them).

I could move on, and try to implement another algorithm, but I'd like to understand why this one isn't behaving like I want. On one hand because it's probably a dumb mistake on my part and I want to be aware of it, on the other hand, because I may even want to use this algorithm, as it seems like it's already fast enough for what I want. I'm not sure I need to go even further and implement Hashlife.

14 hours ago, Gnollrunner said:

You have a comment "// inform neighbors this cell is dead", As far as I know you don't need to do that. Each cell just lives, dies or is born on it's own based on it's neighbors.

What I'm doing is to avoid having to loop through all the neighbors every time, and also to avoid having to check every single cell in the cellmap. I'm storing each cells neighbor count in them, so that then I can skip a whole bunch of cells. In the gen_bits() function you can see I have:

if cellmaps[prev][j][i] != 0:
	#... do all the cell code thing

Every cell that is 0 is skipped, as it's dead and has no living neighbors. If it's dead but has living neighbors, then it's value won't be 0 and so it won't be skipped.

This is what's happening in the cells:

In the cell binary representation I have '0000' (0) if the cell is dead, 
or '0001' (1) if it's alive. By adding and subtracting 2 it helps count 
neighbors, because when I do "n = cellmaps[prev][j][i] >> 1" I'm shifting 
all the bits to the right, removing the one on the right, and I'm left with 
the neighbor count:

       dead cell                         living cell
0000 (0)  >>  0000  (0)            0001 (1)  >>  0000  (0)    
0010 (2)  >>  0001  (1)            0011 (3)  >>  0001  (1)     
0100 (4)  >>  0010  (2)            0101 (5)  >>  0010  (2)   
0110 (6)  >>  0011  (3)            0111 (7)  >>  0011  (3)             
1000 (8)  >>  0100  (4)            1001 (9)  >>  0100  (4)

There is some discussion of making fast implementations of GOL here:

https://devtalk.nvidia.com/default/topic/453819/cuda-programming-and-performance/the-game-of-life-in-cuda/

Aside from using the GPU, my inclinations would be to use bitwise operations and lookup tables.

Myself I'm not sure using python to try and come up with a fast algorithm is really appropriate ... google suggests it doesn't compile down to fast native code, only bytecode, and at this level your timings are going to be confounded by python itself rather than the algorithm.

To really work on optimization I think you need it compiled natively and profiled. I suspect that these algorithms are so simple that with a half decent implementation, the memory access patterns will be the bottleneck.

On the other hand if it's just for learning python why not play with variations on the game, and forget the optimal approach and go for simple, that way it's easier to code and not have bugs due to your 'optimizations'.

For what it's worth here's a quick and dirty C++ console version I did. I used your data. It seems to work OK. It uses what you guys are calling gen_sum. I added some code for saving sums as you walk down the rows. I decided to just use the mod for wrapping on the rows (and not the columns) so it doesn't have to do it in the inner loop. Also I used characters directly just to make it easy to output on the console.

Edit: Found a minor bug but it should be fixed now

#include "stdafx.h"

#include "string.h"
#include "assert.h"
#include <iostream>
#include <string>
#include <sstream>

/**
 ********************************************************************************
 ** CGOLGame - Game of Life 
 ********************************************************************************
 **/

#define LIVE_CHAR '#'
#define DEAD_CHAR '.'

class CGOLGame
{

   class CBoard 
   {

   public:

      CBoard(int iRows, int iCols)
      {
         m_iRows = iRows;
         m_aBoard = new char *[iRows];
         for(int i=0; i<iRows; ++i) {
            // Make one more column so we can zero terminate just to make output easy. 
            char *pRow = new char[iCols+1];
            pRow[iCols] = 0;
            m_aBoard[i] = pRow;
         }
      }

      CBoard(int iRows, int iCols, char *szData)
      {
         m_iRows = iRows;
         m_aBoard = new char *[iRows];
         for(int i=0; i<iRows; ++i) {
            // Make one more column so we can zero terminate just to make output easy. 
            char *pRow = new char[iCols+1];
            strncpy_s(pRow,iCols+1,szData,iCols);
            pRow[iCols] = 0;
            szData += iCols;
            m_aBoard[i] = pRow;
         }
      }

      ~CBoard()
      {
         for (int i = 0; i < m_iRows; ++i) {
            delete[] m_aBoard[i];
         }
         delete[] m_aBoard; 
      }

      void Write(std::ostream &oStr)
      {
         for(int i=0; i<m_iRows; ++i) {
            oStr << m_aBoard[i] << std::endl;
         }
      }

      char *GetRow(int iRow) { return m_aBoard[iRow]; }

   private:

      char **m_aBoard;
      int m_iRows; 
   };

public:

   CGOLGame(int iRows, char *szData)
   {
      m_iStep = 0;

      int iLen = strlen(szData);

      assert(iLen % iRows == 0);
      
      m_iRows = iRows;
      m_iCols = iLen / iRows;

      m_iSize = m_iRows * m_iCols;

      m_aBoards[0] = new CBoard(m_iRows,m_iCols,szData);
      m_aBoards[1] = new CBoard(m_iRows,m_iCols);
   }

   ~CGOLGame()
   {
      delete m_aBoards[0];
      delete m_aBoards[1];
   }

   void Go(CBoard *pDest, CBoard *pSrc)
   {
      static const char aPick[2][10] = {
         { DEAD_CHAR, DEAD_CHAR, DEAD_CHAR, LIVE_CHAR, DEAD_CHAR, DEAD_CHAR, DEAD_CHAR, DEAD_CHAR, DEAD_CHAR, DEAD_CHAR },
         { DEAD_CHAR, DEAD_CHAR, DEAD_CHAR, LIVE_CHAR, LIVE_CHAR, DEAD_CHAR, DEAD_CHAR, DEAD_CHAR, DEAD_CHAR, DEAD_CHAR }
      };
      for (int i = 0; i < m_iRows; ++i) {
         int j;
         // Get our three input rows
         char *aAbove = pSrc->GetRow(RowAddr(i-1));
         char *aThis  = pSrc->GetRow(i);
         char *aBelow = pSrc->GetRow(RowAddr(i+1));
         // Get our output row
         char *bOut = pDest->GetRow(i);
         int iLastCol = m_iCols - 1;
         // Set up starting left and mid counts
         int iLftCount = (aAbove[iLastCol] != DEAD_CHAR) + (aThis[iLastCol] != DEAD_CHAR) + (aBelow[iLastCol] != DEAD_CHAR);
         int iMidCount = (aAbove[0]        != DEAD_CHAR) + (aThis[0]        != DEAD_CHAR) + (aBelow[0]        != DEAD_CHAR);
         // Loop until one before the last column
         for (j=0; j < iLastCol; ++j) {
            int iNextCol = j+1;
            // Calculate right col sums
            int iRgtCount = (aAbove[iNextCol] != DEAD_CHAR) + (aThis[iNextCol] != DEAD_CHAR) + (aBelow[iNextCol] != DEAD_CHAR);
            int iLive = (aThis[j] != DEAD_CHAR);
            // Lookup output by GOL rules. Note live table is shifted one since iMidCount includes the cell we are on
            bOut[j] = aPick[iLive][iLftCount + iMidCount + iRgtCount];
            // shift mid to left and right to mid
            iLftCount = iMidCount;
            iMidCount = iRgtCount;
         }
         // Do last column
         int iRgtCount = (aAbove[0] != DEAD_CHAR) + (aThis[0] != DEAD_CHAR) + (aBelow[0] != DEAD_CHAR);
         bOut[j] = aPick[aThis[j] != DEAD_CHAR][iLftCount + iMidCount + iRgtCount];
      }
   }

   void Itterate()
   {
      Go(m_aBoards[!m_iStep],m_aBoards[m_iStep]);
      m_iStep = !m_iStep;
   }

   void Write(std::ostream &oStr)
   {
      m_aBoards[m_iStep]->Write(oStr);

   }

   int RowAddr(int iRow) { return (iRow + m_iRows) % m_iRows; }

private:

   int m_iStep;

   int m_iRows;
   int m_iCols;
   int m_iSize;

   CBoard *m_aBoards[2];

};

/**
 ********************************************************************************
 ** main - entry point
 ********************************************************************************
 **/

int main()
{

   char szData[] =
      "..................."
      "..................."
      "..#................"
      "..#.#.............."
      "..##....##........."
      "........#.#........"
      "........#.........."
      "..................."
      "..................."
      "..................."
      "..................."
      "..................."
      "..........#........"
      "........#.#........"
      ".........##....##.."
      "..............#.#.."
      "................#.."
      "..................."
      "...................";

   CGOLGame clGame(19,szData);
   std::string str;

   do {
      clGame.Write(std::cout);
      clGame.Itterate();
      std::getline(std::cin, str);
   } while (str.length() == 0);

   return 0;

}

On 6/25/2018 at 10:09 AM, Master thief said:

. It does vertically, but not horizontally. I'm doing the wrapping by using an extra outer border of cells all around, that each gets a copy of the opposite inner border.

The problem is the nature of wrapping. By using two rows, one one the left and one on the right, you created a extra row that shouldn't exist.

Think of wrapping as a bridge and think if your grid wrapped around a cylinder. The part where the two points meet has to be the same line:

So you are only supposed to copy one row horizontal and one vertical. So that you don't impact data.

2 hours ago, Scouting Ninja said:

The problem is the nature of wrapping. By using two rows, one one the left and one on the right, you created a extra row that shouldn't exist.

I'm following the original implementation (I'm currently double checking it to see if I made any mistakes in relation to it), but as far as I can tell, if you only use one extra row and one extra column, you only get wrapping in one direction in each axis. At least in the way I'm doing the swapping, that how it seems to me. I'm copying the inner rows to the opposite outer ones .

The guy on the top-left, is being mirrored on the right side
and the guy on the bottom-right is right at the corner, is 
being mirrored to the left, but also at the top row on both sides.

    0  ,  ,  ,  ,  ,  ,  ,  ,  0  0  ,
    ,  .  .  .  .  .  .  .  .  .  .  ,
    ,  O  .  .  .  .  .  .  .  .  .  0
    ,  O  .  O  .  .  .  .  .  .  .  0
    ,  O  O  .  .  .  .  .  .  .  .  0
    ,  .  .  .  .  .  .  .  .  .  .  ,
    ,  .  .  .  .  .  .  .  .  .  .  ,
    ,  .  .  .  .  .  .  .  .  .  .  ,
    ,  .  .  .  .  .  .  .  .  .  .  ,
    ,  0  .  .  .  .  .  .  .  O  .  O  <- even though this outer row
    0  .  .  .  .  .  .  .  .  O  O  ,     isn't the one being copied
    ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,     over to the other side...
       ^
       ^
      ...the cell here at the bottom came alive because in the previous
iteration the map was like this:

    ,  .  .  .  .  .  .  .  .  .  .  ,
    0  .  .  .  .  .  .  .  .  .  O  ,
    0  x  .  .  .  .  .  .  O  .  O  ,
    0  .  .  .  .  .  .  .  .  O  O  ,
    ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,

That cell marked as 'x' was dead, and but counted 3 living neighbors.

As I said before, though, this works perfectly with one of the algorithms.

3 minutes ago, Master thief said:

you only get wrapping in one direction in each axis.

This is correct. Computers flow from left to right and from up to down; the same way most people read. As long as your cells follow this same order then the wrapping should work.

So cell order should be:

1 2 3
4 5 6
7 8 9
  
//The extra wrapping should be
  
$ # # #
* 1 2 3
* 4 5 6
* 7 8 9

The # row copies the last (789) row and doesn't solve any data itself; it is just a "bridge" of the data. The * row copies (123) and is just a bridge.

Data that moves past 369 and 789 disappears but a clone in the other two rows allows the first rows to react to it before it diapears. The bridge cells don't follow the rules, instead they only copy the data from the other rows.

The $ block is special, because for proper wrapping it has to be the 9 cell, so your grid should work like this:

9 7 8 9
3 1 2 3
6 4 5 6
9 7 8 9

//We can keep tiling it to see if it works:
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8 
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 
6 4 5 6 4 5 6 4 5 6 4 5 6 4 5
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
6 4 5 6 4 5 6 4 5 6 4 5 6 4 5
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
6 4 5 6 4 5 6 4 5 6 4 5 6 4 5
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8

There you go a "infinite" grid.

I can see how that can work, but it seems like it sends information only in one direction and that it requires having to check for boundaries. If a cell is at 6 it'll have to account for that when counting living neighbors. Or if I'm storing neighbor counts in the bits, 3 and 6 will have to communicate both ways, but that implies more conditional branches. I may be missing something, but it doesn't seem ideal for this game in particular. Well, the intention behind the implementation on the book was to avoid having all those checks, to make the game faster.

12 minutes ago, Master thief said:

Well, the intention behind the implementation on the book was to avoid having all those checks, to make the game faster.

The only way I can think of doing this without using bridges and stored data is to actually wrap them. There are a lot of different ways to wrap things but using 3D space is the easiest that I can think of.

Wrap them into a cube, then do the calculations, unwrap for 2D display.

Well, for now I'd like to understand why this one isn't working in one axis...

4 hours ago, Master thief said:

that how it seems to me. I'm copying the inner rows to the opposite outer ones

That was what I explained above. The rule of wrapping tells us that we need to remove as many lines as bridges to get the visual result.

This means that because you use 2 bridges we can remove any 2 duplicate rows to get the visual grid.

Now we see why you get the results you do:

See, I removed 2 rows to represent the 2 bridges. Then I tiled the now smaller grid and we see that it is indeed a wrapping tile set. This is why your code is working as it is.

It doesn't matter where the bridges are removed from, only that they are removed:

In the above code that you showed, it looks like it is working perfectly.

I don't think swapping rows does you any good with the gen_bits() algorithm. After swapping (e.g.) the borders, what change does that have on the neighbour-adjacency data of the border-adjacent simulation cells?

Answer: it does nothing. You'd need to subtract the virtually-living border cells from the border-adjacent cells' neighbour counts, then swap borders, then re-add the newly arrived virtually-living border cells to the border-adjacent cell's counts.

17 hours ago, lawnjelly said:

Aside from using the GPU

The GPU has been pretty much the ideal way to implement life for over a decade

19 hours ago, Master thief said:

What I'm doing is to avoid having to loop through all the neighbors every time, and also to avoid having to check every single cell in the cellmap. I'm storing each cells neighbor count in them, so that then I can skip a whole bunch of cells.

Your second algorithm isn't really achieving that. Both algorithms are O(N), the worst-case constant factor isn't noticeably lower in the second algorithm.

If your goal is to just to shave down the constant factor, you'll find greater performance wins by using raw arrays (array or numpy), and then optimising the grid traversal to minimise cache misses.

If you want to reduce the algorithmic complexity, you pretty much have to abandon the 2D array and use a sparse representation (probably something tricky, like RLE-compressing the empty space).