Game of Life combined from several grids

[ragnarokas]

I am experimenting with various implementations of Game of Life algorithms.
Currently I want to implement it in such way:
- using int and storing 8x8 grid values in it;
- putting these ints in the array, for example, 100 of ints (10x10) each representing 8x8 smaller grids.

I cannot find any good example how to check the boundaries between the grids, i.e. how to implement the search of live neighbor cells in such grid of the grids.

Any ideas or hints would be appreciated.

[kigar64551]

As far as I remember, in Conway’s "Game of Life" each cell can only be "alive" or "dead".
https://www.youtube.com/watch?v=R9Plq-D1gEk

Means that you need exactly one bit of storage for each cell, right?

Hence you could use one 64-bit word, e.g. unit64_t from <stdint.h>, to store a grid of 8×8 = 64 cells.

(an int, which is usually 32-Bit in size, won't be sufficient for 8×8 cells)


Of course, you need to decide how to arrange the 64 cells (bits) within the 64-Bit word.

Order could be "row-major" or "column-major":
https://en.wikipedia.org/wiki/Row-_and_column-major_order

If you want a larger grid than 8×8, you need multiple 64-Bit words, i.e. an array of unit64_t, each of which represents a 8×8 sub-grid. Again, you need to decide how to arrange them.


Once you have decided how to arrange the individual cells within a single 64-Bit word and how to arrange the 8x8 sub-grids within the array of 64-Bit words, it should be relatively straight-forward to write a function that gets or sets the "bit" for a specific cell, by its x and y index (position) in the "global" (overall) grid.

This function would first have to find the right 64-Bit word within the array of 64-Bit words, and then it would have to get/set the right bit in that 64-Bit word, by using some bit-shift + bitwise "and"/"or" operations.

Given such a function, implementing the "Game of Life" update algorithm will then be possible without having to bother about how the data is actually stored internally.


Maybe you want to draw a little picture (sketch) first, in order to illustrate the desired arrangement.

[AbstractionAnon]

No need to write your own bit access routines.
std::bitset provides that functionality.

[ragnarokas]

Thank you.
I am using bitset standard library.
I have implemented a working 8x8 grid in one int64 (0-7 for rows and cols).

And now I am exactly thinking about how the live neighbour search should work at the edges. For example, let's take my global grid is the array of [int1, int2, int3, int4, int5, int6, int7, int8, int9], which makes 3x3 global grid. And lets take i need to search the live cells for cell x=0,y=0 which is on int1. I need to check for -1, -1 which indicates that i need to check int9 grid's coordinates 7,7.
So suppose:

Pseudocode for local grid:
Int countLive( int row, int col)
{
for (int i = -1; i <2; i++)
   for (int j=-1; j<2; j++)
    [Ensure that search does not go over array edges.
     Here exactly I need to jump over other int64 if search goes over 
      edges]
    Count += field[row+i][col+j]
}

[kigar64551]

I am using bitset standard library.

If you are using std::bitset then, IMO, there is no reason to use 8×8 sub-grids anyway. Just use a single std::bitset large enough to hold the complete 100×100 (or whatever size you want) grid.

For an N×M grid, you simply need one std::bitset with a size of N*M bits. The index in the std::bitset of each cell can then be easily computed from the cell's (x,y) position in the grid.

Again, the order is up to you, but the indexing could be "row-major" or "column-major":
https://en.wikipedia.org/wiki/Row-_and_column-major_order


Anyway, regardless which method you decide to use, I suggest you first write these functions:

// Set value of cell at (x,y)
void setCellAt(unsigned int x, unsigned int y, bool value)
{
    /* your code here */
}

// Get current value of cell at (x,y)
bool getCellAt(unsigned int x, unsigned int y)
{
    /* your code here */
}

Once you have those functions, implementing the "Game of Life" algorithm will be simple and clean, because then you don't have to worry about how the data of the cells is actually stored/organized...

[lastchance]

You could just flatten to a vector<bool>

http://cplusplus.com/forum/beginner/226023/#msg1033900

[kigar64551]

You could just flatten to a vector<bool>

This probably would use one byte of storage per "bit" (bool) value.

The advantage of std::bitset is that it stores chunks of 8 bits in a single byte (char), but all the required bit-manipulation "magic" happens internally, so that you can access a "bit" by its index, just like std::vector.

[Ganado]

std::vector<bool> is actually specialized to do packed storage. (But is considered to be a design flaw by some because it breaks the normal std::vector<T> interface)

[ragnarokas]

Thank you very much for your input.
I forgot to underline, that this is specific task which should be implemented as described.
I have successfully implemented GOL with one grid and 2dvector<bool>, so was just confused what to do with several grids made of 8x8 (64 bit int).

I will try to set up the global common coordinates for all of them, and check them as "pages".

[ragnarokas]

... and it seems its not very easy task, at least for me.
I am trying to implement these global coordinates. Generally if I have only one 8x8 grid;

int x = 1; // number of rows of grids;
int y = 1; //number of cols of grids;

  for (int i = 0; i < 8 * x; i++)
  {
    for (int j = 0; j < 8 * y; j++)
    {
      int position = (j + 8 * i);
      std::cout<<std::setw(2) << std::setfill('0')<<position<<" ";
    }
    std::cout<<std::endl;
  }

The Result:

00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

So now I tried to find the mathematical expression which would give me the following result, for example, if x = 2 and y = 3, meaning that I have in total 6 grids. With no success. Could maybe someone advise?

						
00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15 08 09 10 11 12 13 14 15 08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23 16 17 18 19 20 21 22 23 16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31 24 25 26 27 28 29 30 31 24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39 32 33 34 35 36 37 38 39 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 40 41 42 43 44 45 46 47 40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55 48 49 50 51 52 53 54 55 48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63 56 57 58 59 60 61 62 63 56 57 58 59 60 61 62 63
00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15 08 09 10 11 12 13 14 15 08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23 16 17 18 19 20 21 22 23 16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31 24 25 26 27 28 29 30 31 24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39 32 33 34 35 36 37 38 39 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 40 41 42 43 44 45 46 47 40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55 48 49 50 51 52 53 54 55 48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63 56 57 58 59 60 61 62 63 56 57 58 59 60 61 62 63

[kigar64551]

Not quite sure what you are trying to do.

But assuming the N×M gird is represented by the array grid, which is of type unit64_t[] and which has a size of (N/8)*(M/8) – we assume N and M are multiples of 8, for simplicity! – so that each element (64-Bit word) of the array can represent a 8×8 sub-grid, then we can get the value of the cell at position (x,y) via this function:

#define N 256                     /* net number of cells in 'x' dimension */
#define M 256                     /* net number of cells in 'y' dimension */

#define BLOCK_SIZE 8              /* size of a sub-grid in each dimension */

#define BLOCKS_N (N / BLOCK_SIZE) /* number of sub-grids in 'x' dimension */
#define BLOCKS_M (M / BLOCK_SIZE) /* number of sub-grids in 'y' dimension */

static_assert(N % BLOCK_SIZE == 0, "N must must be multiple of block size");
static_assert(M % BLOCK_SIZE == 0, "M must must be multiple of block size");
static_assert(BLOCK_SIZE * BLOCK_SIZE < 8 * sizeof(uint64_t), "too large!");

static uint64_t grid[BLOCKS_N * BLOCKS_M];

bool get_cell_at(const size_t x, const size_t y)
{
    // Select the sub-grid in which the requested cell lies
    const size_t subgrid_pos_x = x / BLOCK_SIZE;
    const size_t subgrid_pos_y = y / BLOCK_SIZE;

    // Compute sub-grid index in grid array
    const size_t subgrid_index = (BLOCKS_N * subgrid_pos_y) + subgrid_pos_x;

    // Compute cell offset *within* the sub-grid (64-Bit word)
    const size_t cell_offset_x = x % BLOCK_SIZE;
    const size_t cell_offset_y = y % BLOCK_SIZE;

    // Compute cell index (bit position) in the 64-Bit word
    const size_t cell_index = (BLOCK_SIZE * cell_offset_y) + cell_offset_x;

    // Return cell value
    return (grid[subgrid_index] >> cell_index) & 0x1;
}

Now, in order to dump the current value of every cell in the grid, we only need:

for (size_t x = 0; x < N; ++x)
{
    for (size_t y = 0; y < M; ++y)
    {
        std::cout << (get_cell_at(x, y) ? '1' : '0');
    }
    std::cout << std::endl;
}

[ragnarokas]

Thank you very much. Thats exactly what I was looking for. I was close, but went into some sort of complicated way and got lost.

Just in your line 13 I believe should be N/8, not N.

And as I am doing row major order, I switched line 13 and line 20 to:

const size_t subgrid_index = (N/8 * subgrid_pos_x) + subgrid_pos_y;
const size_t cell_index = (8 * cell_offset_x) + cell_offset_y;

Anyway you helped me greatly, I tried to invent some sort of complicated formula with no success, instead of separating actions as in your function, thanks!

[kigar64551]

Just in your line 13 I believe should be N/8, not N.

D'oh. You are right!

It would probably make sense to have a separate define for number of sub-grids in x/y dimension.

(Slightly updated sample code)

I tried to invent some sort of complicated formula with no success, instead of separating actions as in your function

The get_cell_at() function was written for readability. If you just want to loop over all cells once, this could certainly be "optimized" to avoid some redundant calculations, by merging the calculations into the loops; but at the cost of readability. And the compiler may do these sort of optimizations anyway...