凹包（Concave Hull）

デモを見る（github.io）

Adriano Moreira と Maribel Yasmina Santos によるK-近傍を用いた凹包（Concave Hull）の計算です。画像の灰色の線が凹包で、コンピュータで凹んだ形を認識するときなどに応用されています。

本来は画像のように字間がつながることは好ましくありません。論文によると、事前にクラスタリングを行った後、各クラスタに対して適用することでより良い結果となるそうです。

三角形分割

デモを見る（github.io）

適当にでっち上げた三角形分割と要素技術です。

以下の手順で分割しています。

1. 凸包を計算。
2. 凸包の一番上にある点と、凸包の全ての辺との間で三角形を作る。
3. 凸包内の点を順次追加していく。点が内側にある三角形を見つけたらそれを分割する。

点が三角形の内側にあるかどうかの判定にblackpawnさんのアルゴリズムを利用しました。

外接円モビールと2次元のベクトル計算

デモを見る（github.io）

外接円が、重力に似せた動作でモビールのように揺れ動くシンプルな作品です。キャンバスをクリックすると赤点を追加できます。

外接円の計算は、mutooさんの実装を用いています。mutooさんの実装を読んでいるときにベクトル計算について調べたので、ついでにキャンバスに描画しました。自前でも外接円の計算を実装してみたものの、遅かったので使っていません。

GLSL小品

デモを見る（github.io）

Munching Square

デモを見る（github.io）

座標変換とMunching Squareの組み合わせです。モアレ模様が出ています。

Munching Squareは x^y という簡単な式で現れる模様です。

var x, y
for (y = 0; y < canvas.Height; ++y) {
    for (x = 0; x < canvas.Width; ++x) {
        canvas.setPixel(x, y, brightnessToColor(x ^ y))
    }
}

Go言語に興味を持ってA Tour of Goを進めていたところSliceの演習で x^y が紹介されていたことが制作のきっかけとなりました。素のMunching Squaresは以下の画像のようになります。

-

私がMunching Squareのことを知ったのは、XScreenSaverがきっかけです。iOSで動くのでごろ寝しながら楽しめます。動画のMunching Squaresは、説明によると古典的な動きをシミュレートしているため上のものとは少し異なっています。

-

実は以前にWebGLでやってみようと思って失敗しています。お手本となるコードは見つけたのですが、そのときは私のコード読解力が低かったので投げました。WebGL 1.0のシェーダでは ^ 演算子が使えないので、XORを自前で実装する必要があります。お手本では ^^ (logical exclusive or) という演算子を使って何とかしています。

Durdle Dwarvesの紹介

黄色はドワーフ（D）、灰色は石（S）、黒は空のセル（_）

Hyphen-atedによるDurdle Dwarvesシミュレータ

r/cellular_automataで紹介されていたセルオートマトンです。元はGood Gameryというフォーラムでpazという名前のユーザによって作られたようです。説明を読んだ印象では、知的エージェントとも言える気がします。

このセルオートマトンはドワーフ、石、空の3状態を持ちます。状態の更新は、各ドワーフについて範囲2のムーア近傍を参照して、あらかじめ用意してあるルールとマッチした場合に行われます。

リンクを張ったシミュレータではルールを自由に編集できます。Oは現在みているドワーフ、Dはドワーフ、Sは石、_は空、*は任意のセルを意味します。編集後にApply Rulesのボタンを押すと変更が適用され、ポーズしてからLoad World Stateで初期状態に戻すことができました。

Burrow rightのOutcomeを以下に変更した場合
*D***
*****
**_O*
*****
*****

Canvas小品

デモを見る（github.io）

HTML5のCanvasで作った小品です。上の2つはフィードバックで派手さが増しています。

今回使ったフィードバックの手法は裏にCanvasをもう一枚用意して、座標変換で回転などをかけています。画面の4隅に色が残るのですが、これが味でもあり、欠点でもあります。

ワイヤワールドに基づくゲーム、ĐiệnWorldsの紹介

セルオートマトン画像などを探していたところ、Redditの/r/Cellular Automataで、Theta Gamesによって作られたĐiệnWorldsを見つけました。

ĐiệnWorldsは限られた資金で送電網を構築して、家に明かりを灯す経営シミュレーションゲームです。明かりを灯した家からは収入が得られますが、送電網の規模に応じて月ごとにメンテナンス料が発生します。うまく収入と支出のバランスをとって赤字にならないように管理することがゲーム性になっています。仕組みはワイヤワールド（Wireworld）のルールに基づいていますが、電流値（Current Value）と変圧器（Transformer）の要素やお金に関する要素が加えられています。

初回プレイ時にまったく分からなかったのでマニュアルを翻訳しました。いろいろと細かい仕組みが書いてあります。元の英語マニュアルも併せて参照してください。

ĐiệnWorldsマニュアル日本語訳（gist.github.com）

2023-05-17: マニュアルがリンク切れになっていたので更新。

以下はざっくりとしたゲームの始め方です。

Turmite

デモを見る（github.io）

Langton's Antの拡張である、Turmiteを作りました。TurmiteのnStateを1にすることでLanton's Antになります。ルールの記法はWikipediaで紹介されている記法（SummaryのDescription）に倣っています。

以下は画像で使われたルールです。

Langton's Ant

デモを見る（github.io）

Langton's Antを作りました。R、Lが偶数個ずつ並ぶようにルールを選ぶと線対称な模様が現れるそうです。以下は画像で使われたルールです。

セルオートマトンと編み物（2D Cellular Automaton and Knitting）

初期状態（Grid 16）

ルール83, 286世代目
セルオートマトンは2次元、2状態、ムーア近傍のTotalistic

ルール83, 286世代目の模様を使用した編み物

セルオートマトンの模様を母に見せたところ、編み物に使えそうだということで実際に試してもらいました。

デザインの面からみると、セルオートマトンから出てくる模様は少し変わっているそうです。今回の場合、編み物画像の右側、赤い小物入れの模様の4隅は元と異なっていますが、色が交互に現れるパターンがよくあるので勘違いしたとのことです。左の青い小物入れは正しい模様になっています。

編み物に応用しやすいよう、カタログのように模様を探すことのできるWebページを作りました。

2次元セルオートマトンのカタログ（github.io）
注意：最新のFirefoxとChromeで動作します。

WebGLでうねうねと動く版も楽しめます。こちらが本記事の発端となりました。

うねうねと動く2次元セルオートマトン（github.io）