ライフゲーム #30

Graphviz

ずいぶん長い間この話題を続けてきたのでこのあたりで一旦休む。さもないといつまでも続けられそうだ。
とりあえず便宜のため散らばっている関連するgvprプログラムをひとまとめにしておく。
以下のコードでは今までの記事のものから変更しているものもあるが基本的に変わっていない。
ただし、set_gen0.gのはみだし警告のバグは取った（え？
詳細は下のset_gen0.gの項に。
今後この話題関連のコードを追加していくとすれば以前述べたように、
パターンの作成をグラフィカルに行うとか、DOTや画像の作成の自動化とかになるかもしれない。

gen_mesh.g

ゲームを展開するためのメッシュグラフを生成する。

BEGIN {
  if (ARGC != 1) {
    printf(2, 'usage: gvpr -f gen_mesh.g -a width,height [-o outfile]\n');
    exit(0);
  }

  int w = xOf(ARGV[0]), h = yOf(ARGV[0]);
  if (w < 1 || h < 1) {
    printf(2, 'error: width and height must be positive integer: %d,%d\n', w, h);
    exit(0);
  }

  node_t gen_node(graph_t g, int x, int y) {
    return node(g, sprintf('%d,%d', x, y));
  }

  void gen_edge(graph_t g, node_t n, int x, int y) {
    edge_sg(g, n, gen_node(g, x, y), '');
  }

  graph_t g = graph('', 'U');
  int x, y;
  for (y = 0; y < h; y++) {
    for (x = 0; x < w; x++) {
      node_t n = gen_node(g, x, y);
      if (x < w - 1) {
        if (y > 0) gen_edge(g, n, x + 1, y - 1);
        gen_edge(g, n, x + 1, y);
        if (y < h - 1) gen_edge(g, n, x + 1, y + 1);
      }
      if (y > 0) gen_edge(g, n, x, y - 1);
    }
  }
  write(g);
}
gen_torus.g

トーラス面状のメッシュグラフを生成するgen_torus.gは直近であり変更もしていないので#28を参照。
したがって当然、例の幅や高さが2以下のときの問題はそのまま残っている。

set_gen0.g

aliveノードリストのファイルを読み込んでメッシュグラフの当該ノードに設定する。

BEGIN {
  if (ARGC < 1) {
    printf(2, 'usage: gvpr -cf set_gen0.g -a filename [[-a dx,dy -a filename]...] [-a dx,dy] [-o outfile] [infile]\n');
    exit(0);
  }

  string p[];
  int arg = 0, pn = 0, mpx = -1, mpy = -1, minusp = 0;
  while (arg < ARGC) {
    string filename = ARGV[arg++];
    int x0 = 0, y0 = 0;
    if (arg < ARGC) {
      x0 = xOf(ARGV[arg]);
      y0 = yOf(ARGV[arg++]);
    }

    int fd = openF(filename, 'r');
    string s;
    for (s = readL(fd); s != ""; s = readL(fd)) {
      s = substr(s, 0, length(s) - 1);
      int x = xOf(s) + x0, y = yOf(s) + y0;
      p[pn++] = sprintf('%d,%d', x, y);
      mpx = MAX(mpx, x);
      mpy = MAX(mpy, y);
      if (minusp == 0 && (x < 0 || y < 0)) minusp = 1;
    }
    closeF(fd);
  }
}

BEG_G {
  int mx = -1, my = -1;
}

N {
  int i;
  for (p[i]) {
    if (name == p[i]) {
      alive = 1;
      break;
    }
  }
  mx = MAX(mx, xOf(name));
  my = MAX(my, yOf(name));
}

END_G {
  if (minusp != 0 || mx < mpx || my < mpy) {
    printf(2, 'warning: some alive nodes in list exceed bounds of graph:%s\n', name);
  }
}

バグはノードのname属性となっている座標から読み取ったメッシュの幅と高さが実際より1小さいことであった。
N節でname属性の座標値とmxやmyを比較して大きい値の方をmxやmyとすることで座標値の最大値を求めているのだが、
座標の最小が0から始まるため、こうして求めた最大値はメッシュの幅や高さより1小さい値となる。
それにも関わらず、END_G節でalive属性を設定するノードの座標値の最大値mpxやmpyと比較する際に、
修正前のコードでは、

  if (minusp != 0 || mx <= mpx || my <= mpy) {

としていた。mxやmyを幅や高さそのものと勘違いしていたせいだった。正しくは等号は要らない。

これに関連して、もし今後、set_gen0.gに機能を追加するとすれば、
メッシュがトーラス状かどうかを検出するかオプションで指示して、
トーラスの場合は設定座標がはみだした時にトーラス的に座標を設定して警告は出さないようにするとかがありかも。
そのときにははみ出しでなく重なり警告とかが必要かもしれない。
もしくは、トーラスか否かというレベルではなく、
与えられたグラフのノードとエッジの実態から設定座標に無理があるかどうかを判断するように一般化するとか。

next_gen.g

現世代のグラフから次世代のグラフを生成する。
このプログラムだけusageがないのでここに書いておく。
usage: gvpr -cf next_gen.g -a size [-o outfile] [infile]

BEGIN {
  int count_alive(node_t n) {
    int count = 0;
    edge_t e;
    for (e = fstedge(n); e != NULL; e = nxtedge(e, n)) {
      if ((e.tail == n && e.head.alive) || (e.head == n && e.tail.alive)) {
        count++;
      }
    }
    return count;
  }
}

N [alive] {
  int c = count_alive($);
  if (c == 2 || c == 3) {
    $.next_alive = 1;
  } else {
    $.next_alive = "";
  }
}

N [! alive] {
  if (count_alive($) == 3) {
    $.next_alive = 1;
  } else {
    $.next_alive = "";
  }
}

END_G {
  node_t n;
  for (n = fstnode($); n != NULL; n = nxtnode(n)) {
    if (n.next_alive == 1) {
      n.alive = 1;
      n.next_alive = "";
    } else {
      n.alive = "";
    }
  }
}
vis_alive.g

グラフにレンダリング用の属性を付与する。

BEGIN {
  if (ARGC != 1) {
    printf(2, 'usage: gvpr -cf vis_alive.g -a size [-o outfile] [infile]\n');
    exit(0);
  }

  double size = ARGV[0];
  if (size <= 0) {
    printf(2, 'error: size must be positive value: %f\n', size);
    exit(0);
  }

}

N [alive] {
  fillcolor = 'blue';
  style = 'filled';
}

N {
  width = size;
  height = size;
  shape = 'box';
  color = 'grey';
  pos = sprintf('%f,%f!', xOf(name) * size, yOf(name) * size);
}

E {
  style = 'invis';
}
vis_alive_2.g

vis_alive.gとは異なる見栄えのレンダリング用の属性を付与する。

BEGIN {
  if (ARGC != 1) {
    printf(2, 'usage: gvpr -cf[q] vis_alive_2.g -a size [-o outfile] [infile]\n');
    exit(0);
  }

  double size = ARGV[0];
  if (size <= 0) {
    printf(2, 'error: size must be positive value: %f\n', size);
    exit(0);
  }

}

N [alive] {
  fillcolor = 'black';
  style = 'filled';
}

N {
  width = size;
  height = size;
  shape = 'box';
  if (! style) style = 'invis';
  pos = sprintf('%f,%f!', xOf(name) * size, yOf(name) * size);
}

E {
  style = 'invis';
}