I've been trying different algorithms, and just yesterday I adapted one from the Graphics Programmer's Black Book (the chapter 17), and it works... but doesn't wrap around the edges like the other algorithms do. 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.

I've been trying for hours to figure out why it isn't wrapping around but I got nowhere so far. Meanwhile I also burned out.

If someone else could take a look and see if they could figure out what's wrong, I'd appreciate it a lot. A fresh pair of eyes might see better than mine. I don't know if I should paste the code right here, as it's a little long (some 200 lines), so meanwhile it's in this repo right here. It's a simple console app, works on the windows console (don't know about the linux terminal).

There's two generation algorithms there for comparison, and you can easily switch using the algo variable. The SUM works fine, the BITS is the one that doesn't. Not sure what else to say. I tried commenting the code for clarity. 

Well, if someone has 5 minutes to spare, I'll greatly appreciate it. Thanks in advance.

----------

EDIT: A specific symptom that I noticed (that I didn't think to mention earlier) is that when using the BITS algorithm (which uses bit manipulation, hence the name of the flag), the cells on the outter edges don't seem to be affected by this part of the code that kills a cell or the equivalent part to revive a cell (specifically the "[i-1]" and "[i+1]" lines, which should affect the cells to the sides of the cell being considered):

# if it's alive 
if cellmaps[prev][j][i] & 0x01:
	# kill it if it doesn't have 2 or 3 neighbors
	if (n != 2) and (n != 3):
		cellmaps[curr][j][i] &= ~0x01
		alive_cells -= 1
		# inform neighbors this cell is dead
		cellmaps[curr][ j-1 ][ i-1 ] -= 2
		cellmaps[curr][ j-1 ][ i   ] -= 2
		cellmaps[curr][ j-1 ][ i+1 ] -= 2
		cellmaps[curr][ j   ][ i-1 ] -= 2
		cellmaps[curr][ j   ][ i+1 ] -= 2
		cellmaps[curr][ j+1 ][ i-1 ] -= 2
		cellmaps[curr][ j+1 ][ i   ] -= 2
		cellmaps[curr][ j+1 ][ i+1 ] -= 2

The actual effect is that the leftmost and rightmost edges are always clear (actually, as depicted, the ones on the opposite side to where the actual glider is, are affected, but not the ones next to the glider).

  when a glider approaches the edge, for exampple,
  this edge should have 1 cell       And the opposite side should
       v           like this         not be like this, but this
       V              v                     V               V
     | . . . .      | . . . .           . . . .|        . . . .|
     | . . # .      | . . # .           . . . .|        . . . .|
     | . # . .      | # # . .           . . . #|        . . # #|
     | . # # .      | . # # .           . . . #|        . . . #|
     | . . . .      | . . . .           . . . .|        . . . .|
     | . . . .      | . . . .           . . . .|        . . . .|

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 `deepcopy`ing 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 `deepcopy`ing 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.

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)