c - 生命游戏 - 结构单元的二维数组，最好的结构方式是什么？

Question

在我的生命游戏实现中，我创建了一个棋盘，它是结构单元数组的数组:

struct cell **board;

我的结构单元看起来像这样:

struct cell{
    int pop;    //0 if dead, 1 if alive.
    int x;      //x coordinate
    int y;      //y coordinate
};

这意味着如果我想更改单元格的 pop 字段，我会这样做:

board[x][y].pop = 1;

有更好的方法吗？什么是“最佳实践”？

Answer 1

这取决于您希望细胞描述什么。

例如，如果您正在努力实现内存高效的实现，则可以使用

#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define  ULONG_BITS  (CHAR_BIT * sizeof (unsigned long))

typedef struct {
    int            rows;
    int            cols;
    size_t         rowstride;
    unsigned long  data[];
} board;

static inline int get_cell(board *b, int row, int col, int alive)
{
    /* Periodic boundaries! */
    if (row < 0)
        row = (b->rows - ((-row) % b->rows)) % b->rows;
    else
        row = row % b->rows;
    if (col < 0)
        col = (b->cols - ((-col) % b->cols)) % b->cols;
    else
        col = col % b->cols;

    {
        const size_t  w = (size_t)col / ULONG_BITS;
        const size_t  b = (size_t)col % ULONG_BITS;

        /* (!!x) == 0 if x == 0,
           (!!x) == 1 if x != 0. */
        return !!(b->word[w + (size_t)row * b->rowstride] & (1ul << b));
    }
}

static inline void set_cell(board *b, int row, int col, int alive)
{
    /* Periodic boundaries! */
    if (row < 0)
        row = (b->rows - ((-row) % b->rows)) % b->rows;
    else
        row = row % b->rows;
    if (col < 0)
        col = (b->cols - ((-col) % b->cols)) % b->cols;
    else
        col = col % b->cols;

    {
        const size_t  w = (size_t)col / ULONG_BITS;
        const size_t  b = (size_t)col % ULONG_BITS;

        if (alive)
            b->word[w + (size_t)row * b->rowstride] |= 1ul << b;
        else
            b->word[w + (size_t)row * b->rowstride] &= ~(1ul << b);
    }
}

static board *new_board(int rows, int cols)
{
    board *b;

    /* rowsize = ceil( (double)cols / ULONG_BITS ) */
    size_t  rowsize = (size_t)cols / ULONG_BITS + !!(cols % ULONG_BITS);
    size_t  words = rowsize * (size_t)rows;
    size_t  bytes = words * sizeof (unsigned long);

    if (rows < 1 || cols < 1)
        return NULL;

    /* Overflow check. */
    if (bytes / words != sizeof (unsigned long) ||
        words / (size_t)rows != rowsize ||
        rowsize * ULONG_BITS <= (size_t)cols)
        return NULL;

    b = malloc(sizeof (board) + bytes);
    if (!b)
        return NULL;

    b->rows = rows;
    b->cols = cols;
    b->rowstride = rowsize;
    memset(b->data, 0, bytes);

    return b;
}

使用unsigned long“字”来保存位是很常见的，因为大多数当前的C实现都使用unsigned long作为最大的 native (处理器寄存器范围)无符号整数类型。

您还可以创建一个高效的函数来计算存活邻居的数量。您需要分别处理单元格本身是 unsigned long 中最左边或最右边的情况，但在大多数情况下，您只需要三个字查找和位掩码，然后是 popcount(或六次移位和八次加法) .

本质上，您将使用两个板，每次都在另一个板上计算下一代(类似乒乓球)。 (您不能使用单个板，因为那样您就会混合当前和下一代。不过，您可以使用仅三行数据的滑动缓存。)

但是，如果您希望对每个单元格使用无符号字符，以便最低位显示当前状态，较高位显示以前的状态(例如，如果您想用不同的颜色为最近死亡的单元格着色) ，你可以使用

#include <stdlib.h>
#include <string.h>

typedef struct {
    int            rows;
    int            cols;
    size_t         rowstride;
    unsigned char  data[];
} board;

static void generation_shift(board *b)
{
    unsigned char *const q = b->data + b->rows * rowstride;
    unsigned char       *p = b->data;

    while (p < q)
        *(p++) <<= 1;
}

static inline int old_neighbors(board *b, int row, int col)
{
    if (row > 0 && row < b->rows - 1 &&
        col > 0 && col < b->cols - 1) {
        const size_t               r = b->rowstride;
        const unsigned char *const p = b->data + row*b->rowstride + col;
        return ( (p[-r-1] & 2) + (p[-r] & 2) + (p[-r+1] & 2) +
                 (p[-1] & 2)                 + (p[1] & 2) +
                 (p[r-1] & 2)  + (p[r] & 2)  + (p[r+1] & 2) ) >> 1;
    }

    if (row < 0)
        row = (b->rows - ((-row) % b->rows)) % b->rows;
    else
        row = row % b->rows;
    if (col < 0)
        col = (b->cols - ((-col) % b->cols)) % b->cols;
    else
        col = col % b->cols;

    {
        const size_t  prevrow = ((row + b->rows - 1) % b->rows) * b->rowstride;
        const size_t  currrow = row * b->rowstride;
        const size_t  nextrow = ((row + 1) % b->rows) * b->rowstride;
        const size_t  prevcol = (col + b->cols - 1) % b->cols;
        const size_t  currcol = col;
        const size_t  nextcol = (col + 1) % b->cols;
        const unsigned char *const p = b->data;

        return ( (p[prevrow+prevcol] & 2) +
                 (p[prevrow+currcol] & 2) +
                 (p[prevrow+nextcol] & 2) +
                 (p[currrow+prevcol] & 2) +
                 (p[currrow+nextcol] & 2) +
                 (p[nextrow+prevcol] & 2) +
                 (p[nextrow+currcol] & 2) +
                 (p[nextrow+nextcol] & 2) ) >> 1;
    }  
}

这样做的好处是，每个单元实际上描述了当前一代以及至少前七代的状态(模拟开始时除外)。

一个有趣的选择是使用存储在unsigned long“words”中的位图，但在奇数代上，对上一代使用奇数位，对下一代使用偶数位；甚至几代人，反之亦然。这样，您就不需要代转换，尽管您需要根据代是奇数还是偶数使用不同的函数。