将细胞自动机状态简化为一组向量路径

Question

我正在开发一个 iOS 版本的生命游戏。该应用程序的核心已经工作，它是一个具有生命游戏所有规则的细胞自动机。它可以制造滑翔机、太空船，并完美地运行。如果你不知道生命游戏，请在 YouTube 上搜索。

因此，我想在这个版本中“平滑”每个单元格。所以，每个单元格不再是孤立的网格，所有活着的单元格将被绘制成连续的斑点。

我已经以离散的形式实现了这一点。我的意思是，我为每个单元格制定了一组规则，使得该单元格绘制一个选定的曲线/矩形形状，以使所有单元格都适合在一起。

如下图所示：

例如，右边的顶部单元格下面有一个活着的细胞，没有其他细胞，所以它有3个直边和一个弯曲的顶部。确定单元格形状的规则是在“cell”类中的逻辑。这产生了我想要的几何效果。但是，由于每个单元格都有不同的CGPath，所以无法进行动画处理。理想情况下，在这张图片中会有两个CGPaths。

问题就在这里。我正在寻找一种基于给定代的存活单元格来组合矢量路径的方法。我认为，这个过程将涉及到单元格输出坐标点，然后通过某个过程将其接收并创建路径。但是，这些点被取出的顺序将很重要。

例如：

在这里，1)代表一些“活着”的“细胞”集合。2)是我生成点的方式。基本上使用我用于从第一种技术创建曲线路径的相同逻辑。可能需要稍微修改，因为某些点不需要重叠单元格。3)将是理想的矢量形状。它们有两条矢量路径，因为一个单元格没有邻居。

因此，我正在思考的算法是如何迭代这些点，为彼此相邻的所有单元格集创建离散路径。我正在研究从左到右扫描与从上到下扫描的区别。或者总是选择距离当前点最近的仍然是“活着”单元格集的点。当它到达第一个点时，它将跳转到最近的不在那个“活着”的单元格集中的点。目前只是推测。

- Alexander Bollbach

Answer 1

针对每个存活细胞，创建相邻存活细胞的位掩码。例如，使用值为1、2、4和8的位表示北、东、南和西。您将得到一组16个平铺：如果你只想显示带有圆形轮廓的单元格，可以快速复制相应的平铺到画布或位图窗口中。这应该是相当快的，因为平铺已经被渲染了。

如果你真的需要轮廓作为曲线，请为每个平铺创建深红色线条的曲线。请注意，平铺0101和1010由两条曲线组成，平铺1111没有曲线，平铺0000是一个闭合曲线。

将当前单元格的曲线段偏移量移动到列表中。所有曲线（除了0000）都有松散的端点；这些端点总是在单元格边界交叉处。

现在你可以创建路径。创建一个查找表，可能是哈希表，包含所有端点。每个端点应该有两个相连的曲线段。现在从列表中选择一个曲线段。它的起点是曲线的起点。现在查找段的终点并进入下一个段。删除访问过的段并将它们添加到路径中。继续直到达到曲线的起点。将曲线添加到列表中。只要列表中仍有曲线段，就重复此过程。

您可能需要将没有邻居（0000）的单元格直接放入最终曲线列表中。您还必须将0101和1010单元格的两条线段视为单独的线段。

编辑：我已经在C语言中拼凑出了一个概念验证示例，它接受随机生成的细胞网格，并创建平滑渲染的PostScript文件。

命名不太一致，我很抱歉，但基本上有四种线段类型：闭合圆、尖峰（或鼻子）、四分之一圆弧和直壁。这些以顺时针方向渲染，因此封闭形状始终在曲线的右侧。

PS渲染中的stype路径字段由四分之一圆弧（NE、SE、SW、NW）、单元格大小的直线（N1, E1, S1, W1）和半个单元格大小的直线（N2, E2, S2, W2）组成。当然，您可以将它们呈现为直线序列和三次贝塞尔曲线，而不是使用PS命令。

每个段还存储单元格起始和结束角的位置，包括NE、SE、SW和NW枚举。

除单元格外，还有一个段列表和一个角网格，用于存储哪些段连接到一个角。一个角只能有没有或两个相连的段。

此示例在编译时具有固定的大小，以使C程序员的生活更轻松。

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

#define N 24

#define die(...) exit((fprintf(stderr, __VA_ARGS__), 1))

enum {NW, NE, SE, SW, NCORNER};

static const int dx[NCORNER] = {0, 1, 1, 0};
static const int dy[NCORNER] = {0, 0, 1, 1};

struct stype {
    const char *name;
    int start;
    int end;
    const char *path;
};

#define STYPE(X)                            \
    X(None,      -1, -1, "")                \
    X(WallN,     NW, NE, "E1")              \
    X(WallE,     NE, SE, "S1")              \
    X(WallS,     SE, SW, "W1")              \
    X(WallW,     SW, NW, "N1")              \
    X(QuarterNE, SE, NW, "W2 SW N2")        \
    X(QuarterSE, SW, NE, "N2 NW E2")        \
    X(QuarterSW, NW, SE, "E2 NE S2")        \
    X(QuarterNW, NE, SW, "S2 SE W2")        \
    X(SpikeN,    NE, NW, "S2 SE SW N2")     \
    X(SpikeE,    SE, NE, "W2 SW NW E2")     \
    X(SpikeS,    SW, SE, "N2 NW NE S2")     \
    X(SpikeW,    NW, SW, "E2 NE SE W2")     \
    X(Circle,    NW, NW, "MM")

#define STYPE_STRUCT(Name, S1, S2, P) {#Name, S1, S2, P},
#define STYPE_ENUM(Name, S1, S2, P) Name,

enum {STYPE(STYPE_ENUM) MAX_STYPE};
static const struct stype stype[MAX_STYPE] = { STYPE(STYPE_STRUCT)};

int ctype[16][3] = {
  /*  0 */  {Circle,            None},
  /*  1 */  {SpikeN,            None},
  /*  2 */  {SpikeE,            None},
  /*  3 */  {QuarterNE,         None},
  /*  4 */  {SpikeS,            None},
  /*  5 */  {WallW, WallE,      None},
  /*  6 */  {QuarterSE,         None},
  /*  7 */  {WallW,             None},
  /*  8 */  {SpikeW,            None},
  /*  9 */  {QuarterNW,         None},
  /* 10 */  {WallN, WallS,      None},
  /* 11 */  {WallS,             None},
  /* 12 */  {QuarterSW,         None},
  /* 13 */  {WallE,             None},
  /* 14 */  {WallN,             None},
  /* 15 */  {                   None},
};

struct seg {
    int type;
    int x;
    int y;
};

struct pt {
    int seg1;
    int seg2;
};

int alive(int cell[N][N], int x, int y)
{
    if (x < 0 || x >= N) return 0;
    if (y < 0 || y >= N) return 0;
    return cell[y][x];
}

void addpt(struct pt *pt, int seg)
{
    if (pt->seg1 < 0) {
        pt->seg1 = seg;
    } else if (pt->seg2 < 0) {
        pt->seg2 = seg;
    } else {
        die("Too many segments for point.\n");
    }
}

int main(void)
{
    int cell[N][N];
    int count = 0;
    int i, x, y;

    for (y = 0; y < N; y++) {
        for (x = 0; x < N; x++) {
            int r = 1 + abs(N/2 - x) + abs(N/2 - y);

            cell[y][x] = (rand() / 4 < RAND_MAX / r);
            if (cell[y][x]) count++;
        }
    }

    /* Create line segments */

    struct seg seg[2 * count];
    int nseg = 0;

    for (y = 0; y < N; y++) {
        for (x = 0; x < N; x++) {
            int ix = 0;

            if (cell[y][x] == 0) continue;         

            if (alive(cell, x, y - 1)) ix |= 1;
            if (alive(cell, x + 1, y)) ix |= 2;
            if (alive(cell, x, y + 1)) ix |= 4;
            if (alive(cell, x - 1, y)) ix |= 8;

            int *p = ctype[ix];

            while (*p != None) {
                if (nseg >= 2 * count) die("Segment overflow\n");

                seg[nseg].x = x;
                seg[nseg].y = y;
                seg[nseg].type = *p++;
                nseg++;
            }
        }
    }

    /* determine start and end points of segments */

    struct pt pt[N + 1][N + 1];
    memset(pt, -1, sizeof(pt));

    for (i = 0; i < nseg; i++) {
        int tp = seg[i].type;
        int s = stype[tp].start;
        int e = stype[tp].end;

        x = seg[i].x;
        y = seg[i].y;

        addpt(&pt[y + dy[s]][x + dx[s]], i);
        addpt(&pt[y + dy[e]][x + dx[e]], i);
    }

    /* set up PostScript header */

    puts("%!PS-Adobe 3.0");

    puts("/A 10 def");
    puts("/A2 A 2 mul def");
    puts("/C { rcurveto } def");
    puts("/L { rlineto } def");
    puts("/START { newpath exch A2 mul exch A2 mul moveto } bind def");
    puts("/END { closepath stroke } bind def");
    puts("/MM { A 0 rmoveto NE SE SW NW } bind def");
    puts("/NW { 0 A neg 0 A neg A A neg C } bind def");
    puts("/NE { A 0 A 0 A A C } bind def");
    puts("/SE { 0 A 0 A A neg A C } bind def");
    puts("/SW { A neg 0 A neg 0 A neg A neg C } bind def");
    puts("/N1 { 0 A2 neg L } bind def");
    puts("/E1 { A2 0 L } bind def");
    puts("/S1 { 0 A2 L } bind def");
    puts("/W1 { A2 neg 0 L } bind def");
    puts("/N2 { 0 A neg L } bind def");
    puts("/E2 { A 0 L } bind def");
    puts("/S2 { 0 A L } bind def");
    puts("/W2 { A neg 0 L } bind def");

    puts("57 180 translate");

    /* walk segments */

    for (i = 0; i < nseg; i++) {
        struct seg *s = seg + i;

        if (s->type == None) continue;

        int x0 = s->x + dx[stype[s->type].start];
        int y0 = s->y + dy[stype[s->type].start];
        int j = i;

        x = s->x + dx[stype[s->type].end];
        y = s->y + dy[stype[s->type].end];

        printf("%d %d START", x0, y0);

        for (;;) {
            printf(" %s", stype[s->type].path);

            s->type = None;
            if (x == x0 && y == y0) break;

            if (pt[y][x].seg1 == j) {
                j = pt[y][x].seg2;
            } else {
                j = pt[y][x].seg1;
            }

            s = seg + j;
            x = s->x + dx[stype[s->type].end];
            y = s->y + dy[stype[s->type].end];
        }      

        puts(" END");        
    }

    puts("showpage");       

    return 0;
}

- M Oehm

---

这对我来说完全超出了我的理解范围。也许我的问题暴露出我在编程方面的经验不足。如果您有时间，私下里与您跟进这个问题会非常有帮助。 - Alexander Bollbach

我已经更新了答案并提供了一个C语言的例子。今天（欧洲中部时间）我不方便讨论，但也许明天可以。 - M Oehm

好的，我想明天在这里查看我的通知。无论你喜欢怎样交流都可以。再次感谢您的回复。 - Alexander Bollbach

@AlexanderBollbach：如果你想要开一个私人聊天室或者其他什么的，我现在会在这附近一段时间。 - M Oehm

请原谅我始终的无知，但是在这里如何开始聊天呢？ - Alexander Bollbach