Уменьшение состояния сотовых автоматов до набора векторных путей

Question

Я работаю над версией iOS Game Of Life. Ядро приложения работает в том, что это рабочий сотовый автомат со всеми правилами игры жизни. Он может сделать планеры, космические корабли и функционировать как таковые. Если вы не знаете об Game of Life, вы его запустите.

Итак, что я пытаюсь сделать с этой версией, является «гладкой» из каждой ячейки. Таким образом, вместо того, чтобы каждая ячейка была изолированной сеткой, все живые клетки будут срисовываться вместе как непрерывная капля.

Я получил это, чтобы работать уже в дискретной форме. Я имею в виду, что у меня есть набор правил для каждой ячейки, где ячейка рисует выбранную кривую/прямоугольную форму, так что все ячейки подходят друг к другу.

Который выглядит следующим образом:

Например, верхняя ячейка на правом сгустка имеет одну живую клетку под ней и знают другие, так что получает 3 прямые стороны и изогнутую верхнюю. Правила определения формы ячейки - это логика, которая находится в классе «клеток». Это дает желаемый геометрический эффект, который я хочу. Однако, поскольку для каждой ячейки существует другая CGPath, она не является анимируемой. В идеале на этой картине было бы два CGPaths.

В этом проблема. Теперь я работаю над созданием векторного пути, основанного на живой ячейке в данном поколении. Я считаю, что этот процесс будет включать выходные координатные точки ячейки, которые затем обрабатываются некоторым процессом для создания путей. Однако порядок, в котором эти пункты принимаются, будет иметь важное значение.

Например:

В этом 1) представляет собой некоторый набор "живых", "клетки". 2) - это то, как я буду генерировать точки. В принципе, используя ту же логику, я использую для создания изогнутых путей из первого метода. Возможно, это немного изменится, поскольку некоторые точки не нужны, поскольку они перекрывают ячейки. 3) были бы идеальными векторными формами. Это два векторных пути, потому что у клетки нет соседей.

Таким образом, алгоритм, о котором я пытаюсь думать, состоит в том, как перебирать эти точки, чтобы создать дискретный путь для всех наборов сотов, смежных друг с другом. Я просматриваю сканирование слева направо и сверху вниз. Или всегда выбирайте точку, которая ближе всего к текущей точке, все еще являясь частью набора живых клеток. Когда он достигнет первой точки, он перейдет к ближайшей точке, которая не находится в этом наборе живых клеток. Просто теоретизирует на этом этапе.

Answer 1

Для каждой живой ячейки создайте битовую маску соседних живых ячеек. Скажем, вы используете биты со значениями 1, 2, 4 и 8 для севера, востока, юга и запада. Вы получаете набор из 16 плиток:

Если вы просто хотите, чтобы отобразить клетки с округлым контуром, вы можете быстро скопировать соответствующую плитку на холст или окно растрового. Это должно быть достаточно быстро, потому что плитки уже визуализированы.

Если вам действительно нужен контур в виде кривой, создайте темные красные линии как кривые для каждой плитки. Обратите внимание, что плитки 0101 и 1010 состоят из двух кривых, плитка 1111 не имеет кривой, а плитка 0000 - замкнутая кривая.

Переместить сегменты кривой со смещением текущей ячейки в список. Все кривые (кроме 0000) имеют свободные концы; эти концы всегда лежат на пересечениях границ ячейки.

Теперь вы можете создавать дорожки. Создайте справочную таблицу, возможно хэш, всех конечных точек. Каждая конечная точка должна иметь два связанных сегмента кривой. Теперь выберите сегмент кривой из списка. Отправной точкой является исходная точка кривой. Теперь найдите конечную точку сегмента и перейдите к следующему сегменту. Удалите посещенные сегменты и добавьте их в путь. Продолжайте, пока не достигнете начальной точки кривой . Добавьте кривую в список. Повторите, пока в списке еще есть сегменты кривой.

Вы должны, вероятно, поместить ячейки без соседей (0000) в конечный список кривой сразу. Вы также должны обрабатывать два сегмента линии 0101 и 1010 в качестве отдельных сегментов.

Редактировать: Я собрал пример доказательной концепции в C, который принимает случайно сгенерированную сетку ячеек и создает файл PostScript гладкого рендеринга.

Номенклатура немного несовместима, я боюсь, но есть в основном четыре сегмента: замкнутые круги, шипы (или носы), четверть кругов и прямые стены. Они отображаются по часовой стрелке, так что закрытая форма всегда находится справа от кривой.

ПС рендеринга – path поле 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; 
}