有没有办法只用一个数组来编写康威的生命游戏

Question

我已经用 C 语言编写了一个实现康威生命游戏的程序。

这是我的代码

#include <stdio.h>

int main(int argc, char *argv[]) {
    char field[20][20] = {0}; //game field
    char cpy[20][20] = {0}; //copy of game field
    int gens;   //number of generations
    scanf("%d", &gens);//input by user
    while(1){   //runs till 'break;'
        char c;
        scanf(" %c", &c); //read next char
        if(c == 'a'){//break at char 'e'
            int i,j;
            scanf("%d %d",&i,&j);//scan coordinates
            field[j][i] = 1;    //setting cell to state alive
        }else{
            break;
        }
    }
    //calculate and print generations
    for(int i = 0; i <= gens; i++){
        printf("-- Generation: %d\n",i);
        //iterating over each cell
        for(int k = 0; k < 20;k++){
            for(int l = 0; l < 20; l++){
                //print current generation
                if(field[k][l] == 1){
                    printf("%c",'#');//alive
                }else{
                    printf("%c",'.');//dead
                }
                
                //counting neighbors of field[k][l]
                int neighbors = 0;
                for(int y = -1; y < 2; y++){
                    for(int x = -1; x < 2; x++){
                        if(!(x == 0 && y == 0)){
                            if( k + y < 20 &&
                                k + y >= 0  &&
                                l + x < 20 &&
                                l + x >= 0){
                                    if(field[k+y][l+x] == 1){
                                        neighbors++;
                                    }
                                }
                        }
                    }
                }
//rules
//Any live cell with two or three live neighbours survives.
//Any dead cell with three live neighbours becomes a live cell.
//All other live cells die in the next generation. Similarly, all other dead cells stay dead.
                if(field[k][l] == 1 &&
                   (neighbors == 2 || neighbors == 3)){
                    cpy[k][l] = 1;       
                }else if(field[k][l] == 0 &&
                   neighbors == 3){
                    cpy[k][l] = 1;       
                }else if(field[k][l] == 1){
                    cpy[k][l] = 0;
                }
                
            }
            printf("\n");
        }
        
        //setting gamefield to new generation
        for(int a = 0; a < 20; a++){
            for(int b = 0; b < 20; b++){
                field[a][b] = cpy[a][b];
            }
        }
    }
    return 0;
}

用户输入看起来像这样

第一个数字表示要模拟多少代。之后，用户可以通过输入字符 a，然后输入单元格的 x 和 y 坐标，将单个单元格设置为 1。判断输入结束，用户输入字符e.

如您所见，我的代码中有 2 个数组，一个代表当前一代，第二个代表下一代。

只是因为我感兴趣，有没有一种方法可以实现整个事情，这样你只需要一个数组？

Answer 1

而不是比较原始字段，例如field[k][l] == 1 你可以这样检查：(field[k][l] & 1) == 1。现在你只检查每个字段的一位。

那么您可以 field[k][l] |= (1 << 1) a.k.a，而不是像您 (cpy[k][l] = 1) 那样在副本中设置值。设置第二位，同时将其与第一位的值合并。

最后，您将再次遍历所有字段，并执行 field[k][l] >>= 1。所有第二位都右移，所有第一位都被遗忘。

//setting gamefield to new generation
for(int a = 0; a < 20; a++){
    for(int b = 0; b < 20; b++){
        field[a][b] >>= 1;
    }
}

Answer 2

邻居的计数可以合并：每个单元将其 4 个上游邻居的计数加上 4 个下游邻居的计数 - 当您计算下行邻居时，您添加它们的邻居计数。

  --->

|  u u u
|  u * d
|  d d d 
v

所以只需要一个数组，但是第二个字段：

struct onecell {
    int alive;
    int neibs;
} **cells;

函数：

void do_row(struct onecell *row, struct onecell *rlow) {

    int j;
    int nbs;
    struct onecell *c, *n1;

    for (j = 1; j <= COLSDISP; j++) {

        c  =  &row[ j ]; 
        n1 =  &row[j+1];        // same row, to the right

        nbs = c->neibs + n1->alive;                                   // add the 4 neighbors to the right and below
        nbs += rlow[ j ].alive + rlow[j+1].alive + rlow[j-1].alive;

        if (c->alive) {

            n1->neibs++;                // tell downstream that we are alive  
            rlow[ j ].neibs++; 
            rlow[j+1].neibs++;
            rlow[j-1].neibs++;

            if (nbs < 2 || nbs > 3)
                c->alive = 0;

        } else
            if (nbs == 3)
                c->alive = 1;

        c->neibs = 0;                    // reset
    }
}

边界行必须单独处理；多线程看起来像这样：

while (loops++ < 1000) {

        for (i = CHUNK; i <= ROWSDISP; i += CHUNK)
             prepare_bottomrow(cells[i], cells[i+1]);

        #pragma omp parallel for num_threads(THREADS)

        for (i = 1; i <= ROWSDISP; i++)
            if (i % CHUNK != 0)
                do_row(cells[i], cells[i+1]);
            else
                do_bottomrow(cells[i]);

        // print_matrix();
        // usleep(40000); 

    }

...bottomrow() 完成了 do_row() 的一半工作； prepare_bottomrow()在parallel之外，因为它跨了一个CHUNK。但即使没有 omp parallel 也会有最后一排。

行、线程和块大小必须是可整除的，例如200 行，4 个线程和 CHUNK=50.

这个算法很快。 rlow[j].neibs 和 rlow[j].alive 并排。

有没有办法只用一个数组来编写康威的生命游戏

Is there a way to program Conway's Game of Life with only one array

c

conways-game-of-life