解説: Life Universe

公開からだいぶ時間が経ってしまいましたが、Life Universe の技術解説を書きます。

English version is here.

Life Universe について

その前に、いくつか知っておくとよい事柄があるので先に説明します。

OTCA Metapixel について

ライフゲームの説明については割愛します。ライフゲームはチューリング完全なので様々なパターンが存在し、その中に OTCA Metapixel というものが存在します。OTCA Metapixel は(メタ)セルのオンとオフの状態が視覚的に分かる特殊なパターンで、ライフゲームのみならず outer totalistic なルール[1]で動く全ての[2]2次元セルオートマトンを再現できます。

つまり、ライフゲームの中で動くライフゲームを見ることができます。

こちらは有名な動画ですが、実際にこういう計算が可能になります。

Hashlife について

OTCA Metapixel の実質的なサイズ[3]は 2048×2048 セルです。つまり1つのメタセルを動かすだけで400万を超えるセルの計算が必要になり、メタセルでパターンを作ろうと思えば億単位のセルを動かす必要が出てきます。普通に計算していては当然リアルタイムでは動きません。

そこで(というと因果関係が逆になる[4]のですが)、Hashlife という超高速にライフゲームが計算できる手法を用います。Hashlife はフィールド全体を四分木で表現し、状態が同じ子を縮約して DAG にしたうえで、キャッシュと doubling を用いて爆発的な速さで次の世代を計算するアルゴリズムです。

Hashlife を用いると OTCA Metapxiel を非常に効率よく計算することができ、現代的なマシンであれば OTCA Metapixel を使ってさらに OTCA Metapixel を動かす (meta-metapixel) ようなシーンも計算することができます。

しかし Hashlife にも限界はあり、やはり効率が良いとはいえ階層を増やすにつれて使用メモリと計算時間は指数的に増大していくため、meta-meta-metapixel を用いたパターンの構築などは現実的ではありません。

Life Universe のアイデア

ある時ふと思いました。「これ、階層を無限にしたくない?」

そもそもそんなことができるのかという話ですが、OTCA Metapixel の存在によって少なくとも数学的にはそのような存在が作れてしまいます。例えば、あるレベルのセルを用いて次のレベルの OTCA Metapixel を構築するような写像の最小不動点を考えればよいです。

次に、細かい点を色々と誤魔化せばリアルタイムで計算可能であることも分かります。

例えば、実際には meta-metapixel のレベルまで計算しておいて、十分に縮小されて最も小さい metapixel の中身が潰れた段階で、metapixel を通常のセルに、meta-metapixel を metapixel にすり替えます。こうすることで、実質的な計算の分量を固定したままどこまでも拡大縮小ができるライフゲームを「見せる」ことができます。

しかし、これには大きな問題が2つあります。

時間に対する一貫性

一つ目は、「時間を進めたときに計算が破綻する」という点です。Meta-metapixel のレベルで計算をしているとき、meta-meta-metapixel のことは考えられていないのですが、ある階層における meta-metapixel の点滅パターンは、そのセルがさらに上位の meta-meta-metapixel のどの位置に存在するかに依存します。

さらに、meta-meta-metapixel の点滅パターンを決定するためには meta-meta-metapixel が meta-meta-meta-metapixel のどこに位置しているかを知る必要があり、さらに……という風に無限に続いていきます。つまり、本当に無限の階層の計算を正しく行おうと思うと、途中の階層で計算を打ち切ることができないのです。

位置に対する一貫性

二つ目は、「拡大してから縮小したとき、元の場所に戻ってこない可能性がある」という点です。拡大したときは最も大きい meta-metapixel の情報を捨ててしまうので、再び縮小したとき同じシーンを構築できるとは限りません。

拡大と縮小は限りなく続けられるため、ここでも「今自分がいる位置」を正確に表そうとすると無限の情報が必要になることが分かります。

結局のところ、「正しさ」を追及すると計算量と消費メモリどちらをとっても無限からは逃れることができないのです。

Life Universe

上記二つの問題を解決し、完全に正しい計算をリアルタイムで実現した作品が Life Universe です。

当初自分でも「すごいものができた」とは思ったのですが、それでも予想以上の反響を世界中からいただいて大変びっくりしました。

ありがとうございます。

部分的な構造の考察

実現したい対象の構造を分解して考察することは重要です。まず OTCA Metapixel(以下 OTCAMP)の構造を考察します。

OTCAMP の構造と状態数

OTCAMP の実質的なサイズは 2048×2048 で、無限に敷き詰めることが前提なので端っこにあるセルは考えません。また、パターンの周期は 35328 なので、35328 世代進めると meta レベルの世代が 1 進むことになります。また、OTCAMP 自体のオンオフがあるので、ある時刻における OTCAMP の状態というのは、2 (on/off) × 35328 (time) で決定できそうな気がしてきます。しかし、これでは足りません

敷き詰められた OTCAMP は周囲の OTCAMP とグライダーを通じて通信しています。よって、周囲の OTCAMP の状態によって中心の OTCAMP の状態はわずかに変わってきます。隣接するセルは 8 セルあるので、追加で 2^8 の情報が必要になります。

実はこれでもまだ足りず、自身の一つ前の状態が必要になります。OTCAMP は内部状態と表示されている状態の時刻が微妙にずれており、内部状態を更新した少し後に表示を更新します。そのため、一つの周期の間に ON→OFF, OFF→ON, ON→ON, OFF→OFF のような表示の更新が見えることになります。

結局のところ、ある瞬間の OTCAMP の状態を特定するには、

  • 自分を含む周囲 9 のセルの状態 2^9
  • 自分の一つ前の状態 2
  • 周期内の時刻 35328

の情報があればよいことになります。これらのパターンを事前にすべて用意しておけば、理論上は適切な敷き詰めを行うことで正しい表示が得られます。

さて、これはどのくらいの容量になるでしょうか。圧縮をしないと仮定すると、一つの状態で 2048\times2048=4194304 ビットを使うので、合計で 2^9\times2\times35328\times4194304=151732604633088 ビット、すなわち 138 TiB になります。とんでもない分量ですが、ひとまずこのパターンがすべて事前計算できたと仮定して、どのようにパターンを敷き詰めていけばいいかを考えます。

拡大しかしない場合

単一の OTCAMP の状態を特定する方法が分かったところで階層構造を作ることを考えますが、まずは縮小を続けていくとある段階で同じ階層の全ての OTCAMP がオフになるような場合を考えます。この場合、それ以上縮小しても何も見えなくなるだけなので、拡大しかすることがないということになります。この場合に正しい計算をするにはどうすればよいかを考えます。

オフの OTCAMP が敷き詰められている階層をレベル 0、それらの OTCAMP の内部のセルを構成する OTCAMP をレベル 1、さらにその内部のセルを構成する OTCAMP をレベル2、という風に階層にレベルを割り当てます。拡大していくほど大きな数字のレベルが見えてくるわけですね。

次に、自分が今見ている位置を特定するための座標の概念を導入します。いま、ある状態が固定された一つの OTCAMP に注目しているとします。ここから、その OTCAMP を構成するセルの一つに注目を移すためには、

  • 注目するセルの場所
  • 注目したセルを OTCAMP と見なしたときの、その OTCAMP の周期内の時刻

を決定する必要があります。この場所と時刻を、整数の三つ組 (x,y,t) で表します。ただし、0\leq x,y\lt20480\leq t\lt35328 を満たすものとします。これで次に注目する OTCAMP の状態が決定されることになります。この三つ組のことを単に注目と呼ぶことにします。

例えば、レベル 0 に存在する OTCAMP の一つに注目しているとします。レベル 0 の OTCAMP は全てオフの状態を繰り返しているので、周期内時刻を t_0 として (*,*,t_0) によって状態を決定することができます(どのセルを見ているかは関係ないので、周期内の時刻だけで状態が決定されます)。

さらにこの OTCAMP を構成するセルのうち、左から x_1 番目、上から y_1 番目のセルに注目し、そのセルを OTCAMP と見なしたときの周期内時刻を t_1 とすることで、ある特定のレベル 1 の OTCAMP に注目することができます。これを (*,*,t_0)\to(x_1,y_1,t_1) で表します。

同様にして、ある特定のレベル n の OTCAMP に対する注目を、次のような注目の連鎖

(*,*,t_0)\to(x_1,y_1,t_1)\to\dots\to(x_n,y_n,t_n)

で表すことができます。これを対応する OTCAMP の座標と定義します

座標とセルの状態

今考えたいのは、ある座標が与えられたときに、対応する OTCAMP の状態を計算する方法です。これができれば、注目している OTCAMP を「見る」ことが可能になります。

これはトップダウンに行うことができます。例えば、座標

(*,*,t_0)\to(x_1,y_1,t_1)

に対応する OTCAMP の状態を決定したいとします。レベル 0 ではオフの OTCAMP が敷き詰められていることが分かっているので、周期内の時刻 t_0 のみから OTCAMP の状態が決定できます。レベル 1 の OTCAMP の状態を決定するには、

  • 周囲 9 セルの状態
  • 自身の一つ前の状態
  • 周期内の時刻

が必要です。このうち、周囲 9 セルの状態は、整数 -1\leq i,j\leq1 について座標 (*,*,t_0) で表される OTCAMP の (x_1+i,y_1+j) にあるセルを見ることで決定することができます。また、自身の一つ前の状態は、座標 (*,*,t_0-1) で表される OTCAMP の (x_1,y_1) にあるセルを見ることで決定できます。周期内の時刻は t_1 で決定されます。

これで、座標 (*,*,t_0)\to(x_1,y_1,t_1) が表すレベル 1 の OTCAMP の状態を決定することができました

同様にして、レベル 2 以降のセルの状態もレベル 1 までのセルの状態を用いて決定することができ、任意の座標

(*,*,t_0)\to(x_1,y_1,t_1)\to\dots\to(x_n,y_n,t_n)

に対応するレベル n の OTCAMP の状態を有限回の計算で決定することができます。

時間発展とスクロール

座標から状態を決定することができれば、実は時間発展とスクロールはそれほど難しくありません。

OTCAMP の周期は 35328 なので、あるレベルで時刻が 35328 進むと、親レベルでの時刻が 1 進みます。つまり、全体の時刻はレベルを桁数と見たときに 35328 進数として扱うことができます。例えば座標 (*,*,0)\to(0,0,35327) においてレベル 1 で時刻を 1 進めると、座標は (*,*,1)\to(0,0,0) に変化します。

同様に、座標についても xy それぞれについて 2048 進数と見なすことができます。例えば、座標 (*,*,0)\to(0,0,0)\to(2047,0,0) からレベル 2 において一つ右のセル(+x 方向)に移動すると、座標は (*,*,0)\to(1,0,0)\to(0,0,0) に変化します。続いて上のセル(-y 方向)に移動すると、座標は (*,*,0)\to(1,2047,0)\to(0,2047,0) に変化します。

こうして階層構造の中を自由に動き回れるようになりました。注目の連鎖が有限であれば座標も有限の情報しか持たないので、使用メモリも有限で済みます。

全体の構造の考察

拡大しかしない場合、座標は有限の長さで表現され、状態の決定もトップダウンに有限の計算で求まることが分かりました。

では、レベル 0 で階層構造が終わらずに、レベル -1、レベル -2、… と無限に続く場合を考えてみましょう。

レベル 0 における座標 (0,0,0) のセルの状態を知りたいとします。レベル 0 における OTCAMP がすべてオフであるという仮定は存在しないので、レベル 0 におけるとある OTCAMP の状態を決定するためには、その OTCAMP がレベル -1 においてどの状態の OTCAMP のどこに属しているかの情報が必要になります。さらに、レベル -1 における OTCAMP の状態を決定するにはレベル -2 の情報が必要になり、同様にして無限に先のレベルの情報が必要になってしまいます。つまり計算が終わりません

また、座標の拡張も必要になってきます。今まではレベル 0 での状態が明らかだったために、レベル 0 を基点とした注目の列で状態が特定できましたが、今度は無限遠から続く注目の列を座標にする必要が出てきます。すなわち、座標は

\cdots\to(x_{-1},y_{-1},t_{-1})\to(x_0,y_0,t_0)\to\cdots\to(x_n,y_n,t_n)

と左に無限に伸びる注目の列として表さざるを得ません。つまり無限の記憶容量を必要とします

さらに、よくよく考えるとこのような座標が実は状態を一意に決定しない可能性があるという問題があることも分かりますが、非常にややこしくなってしまうのでここでは触れないことにします。

不可能を可能にする

さて、真面目に計算しようとすると不可能であることが分かってしまったので、どうにかしてこれを可能にしたいです。

計算が止まらない原因は、ある OTCAMP の状態を取得するために一つ上のレベルの OTCAMP の状態が必要だからでした。止まらない再帰関数のような構造になっています。そこで、この再帰を途中で無理やり止めることを考えます。つまり、あるレベルまで来たところで、自身の状態を決定するためにそれ以上上のレベルに状態を問い合わせることはせず、今ある情報から自身の状態を決め打ちで決定してしまいます。これは、さっき「レベル 0 においてオフの OTCAMP が敷き詰められている」と仮定を置いたことに似ています。こうすることで状態決定のための計算は有限回で停止し、座標も決め打ちしたレベルを基点とした有限の注目の列で表すことができます。

ここで問題となるのが、縮小して決め打ちのレベルまで到達してしまった場合の処理です。それより上のレベルは考えていないので、何もしなければそこで宇宙が終わってしまいます。どうすればよいでしょうか?

 

正解は「辻褄の合う親を動的に構築する」です。これがこの作品を実現するための最大の鍵になります。

 

親を動的に構築する

例えば、自身を含む周囲のセルがすべてオフで、自身の一つ前の状態はオンであり、周期内の時刻が t であるような OTCAMP を考えます。この OTCAMP の親となりうるのは、次の 3×3 のパターン遷移

  ? ? ?             □ □ □
  ? ■ ?     -->     □ □ □
  ? ? ?             □ □ □

time = t          time = t+1

■: ON
□: OFF
?: ON or OFF

をとある時刻 t' と場所 (x,y) に持つような状態の OTCAMP です。この OTCAMP が存在している場所とその親は分からないため、この OTCAMP の座標を仮に (?,?,t') で表すとします。

すると、前述の OTCAMP は (?,?,t')\to(x,y,t) という座標で表すことができます。その後、さらにこの親の親となる OTCAMP を見つけることができれば、座標を (?,?,t'')\to(x',y',t')\to(x,y,t)左に伸ばすことができます。

ただし、変な状態の OTCAMP を選んでしまうと、その親となるような OTCAMP が存在しなくなってしまうことがあるので、決め打ちする状態、および条件を満たす親の選択は慎重に行う必要があります。

実際の作品内では、縮小を続けたときに見える風景に多様性を持たせるため、あらかじめ計算打ち切り時に使う OTCAMP の状態とその親の状態をある程度列挙しておき、実際に親が必要になったときに可能な選択肢の中からランダムに親の状態を選択しています[5]

親が展開される様子

さて、このように遅延評価のようなアプローチで再帰計算を打ち切ると、完全に矛盾のない構造を有限時間で計算していくことが可能になります

例を見ていきましょう。まず最初に根となる OTCAMP の状態を選択します。状態はどのように取っても構いませんが、親が必ず存在するような状態を選びます。この OTCAMP の周期内時刻 10000 の状態を見ているとすると、その座標は

(?,?,10000)

で表されます。さらに時間を進めて、座標が (?,?,35327) になったとしましょう。次に時刻を進めるとき、時刻の繰り上がりが生じます。この段階で、この OTCAMP の親を実際に決定する必要が出てきます。つまり、例えば座標を

(?,?,500)\to(50,100,35327)

のように左に拡張してから、

(?,?,501)\to(50,100,0)

のように繰り上がりを計算することで次の状態を決定します。同様の処理は、スクロールに対しても適用されます。例えばこの状態から一つ左のセルに注目を移すと、座標は

(?,?,501)\to(49,100,0)

となりますが、これを続けていって

(?,?,501)\to(0,100,0)

となった段階で、次に左のセルに注目するときに親の展開が必要になります[6]

(?,?,2000)\to(20,30,501)\to(0,100,0)

のように親を展開して ? の数字を決定してから、繰り下がりを計算して座標を更新します。

(?,?,2000)\to(19,30,501)\to(2047,100,0)

こんな感じで、必要に応じて親が展開されていきます。重要な性質として、一つ親を展開するたびに 2048 倍の移動と 35328 倍の時間経過までそのまま計算できるようになるので、非現実的なほどに高速に移動したり、超高速で時間を進めたりしても展開される親の個数は数個程度で済みます。

例えば時刻を 5000 兆ステップ進めても展開される親の個数は高々 4 個です。指数って恐ろしいですね。

実際に OTCAMP の状態を計算する際は、愚直に実装すると再帰計算により指数的に計算時間がかかってしまうので、メモ化を用いて座標の長さに対して線形程度までオーダーを減らしています。

アニメーションを用意する

さて、これはどのくらいの容量になるでしょうか。圧縮をしないと仮定すると …… すなわち 138 TiB になります。とんでもない分量ですが、ひとまずこのパターンがすべて事前計算できたと仮定して、どのようにパターンを敷き詰めていけばいいかを考えます。

敷き詰めの計算部分は解決しましたが、前提として仮定していたこれが残っていました。Web でどうにか公開できる程度の大きさまでこれを圧縮する必要があります。

圧縮せずに容量を削減する方法としては、一部のみ記録して残りは再生時に計算する、というような手法が考えられます。しかし、時刻へのランダムアクセスができなくなってしまうので、多階層の OTCAMP を表示するには不適と考え、結局全フレームを完全に記録することにしました。

とりあえず Hashlife

ひとまず全状態の OTCAMP が計算できないと話にならないので、とりあえず Hashlife を実装して、2^9\times2=1024 通りの配置の OTCAMP 全てについて 35328 世代分の計算を行い、全アニメーションデータの出力を行いました。

Hashlife を使う利点として、Hashlife はメモリ上で同じ状態の四分木のノードを縮約して DAG として保存しているので、そのままグラフを書き出せば画像等で保存するよりも圧倒的に小さなサイズでデータを保存できます。保存すべきデータは2種類あり、全ての必要なノードを含む DAG の構造と、各状態における OTCAMP が参照しているノードの番号を記したアニメーションデータが必要になります。特に後者の容量が大きく、全体として 4 GiB 以上になったのを覚えています。138 TiB に比べるとだいぶ小さくはなりましたが、まだとても配布できるようなサイズではありません。

データを圧縮しやすくする

出力したファイルには、1024 通りのセル配置の OTCAMP それぞれについて、35328 フレーム分のデータを書き込んでいました。このデータを、35328 フレームそれぞれにおける 1024 通りのセル配置のデータとなるように並び替えます。こうすることで、格段にデータが圧縮しやすくなります。なぜでしょうか。

その理由は、各セル配置における同時刻でのデータの類似性にあります。例えば、あるセル配置[7] A における時刻 t と時刻 t+1 での OTCAMP を比較してみます。世代が隣り合っているので、パッと見大きな違いはありません。しかし、ライフゲームは細かい振動子を多く含むので、よく見るといろんな所が少しずつ変わっています。結果として、参照するノード番号は全く異なったものが多く含まれます。

一方、セル配置 A の時刻 t における OTCAMP と、別のセル配置 B の時刻 t における OTCAMP を比較してみると、これは驚くほど細部がよく一致します。時刻を揃えているため、各振動子のパターンが一致しているものがほとんどだからです。

多くの圧縮アルゴリズムでは、似たようなパターンがデータの近くに出現するほど圧縮率が高くなるため、このようなデータの並び替えを行うだけでも桁違いに圧縮率が高くなることが期待できます。

LZSS

前述の並び替えの結果、35328 個の 1024 個の番号列を圧縮することになりました。このそれぞれの 1024 個の番号列について、LZSS アルゴリズムを適用してデータを圧縮します。番号列が 1024 と短いので、全探索によって圧縮後の容量を最小にできます。

この LZSS アルゴリズムはシンプルながらも非常に強力で、多く発生する繰り返しパターンのほとんどを除去できます。また、展開が高速なのも LZSS の特徴の一つなので、メモリには圧縮済みのデータを保存しておいて、計算で必要になったときに展開して取り出すことができます。

この圧縮によって、アニメーションデータを 20 MiB 程度まで圧縮できました。どうにか Web で公開できなくはなさそうですが、できればさらに小さくしておきたいところです。

LZSS 結果のパターン化

LZSS で圧縮されたデータを見ていると、異なる時刻の圧縮済みのデータで同じようなパターンが出現していることが分かります。例えば、

A B C 1 2 A 1 3 A 4 5 B ...

X Y Z 1 2 X 1 3 X 4 5 Y ...

のようなデータが異なる時刻に点在していることが確認できます。そこで、これらのデータを

$1 $2 $3 1 2 $1 1 3 $1 4 5 $2 ...
A B C ...
$1 $2 $3 1 2 $1 1 3 $1 4 5 $2 ...
X Y Z ...

のように、穴埋めパターン + 使用する番号列 に分解し、同じ穴埋めパターンを再利用するようにしました。これでサイズは 10 MiB 程度になりました。

PNG にする

ダメ押しの一手です。画像形式は JavaScript で読み込みがしやすいうえ、PNG 自体に Deflate が付いているので、バイナリ化に加えさらなる容量削減が期待できます。

エンコード対象のデータに含まれる数値はいずれも 19 bit に収まっていたので、アルファなし PNG で利用可能な 24 bit のうち残りの 5 bit を使ってランレングス圧縮を行いました。多少ながら効果がありました。

加えて、OptiPNG というツールを使って PNG ファイル自体のサイズ削減を試みました。これも多少効果がありました。

最終的に、全 DAG データとアニメーションデータを合わせて 4 MiB 程度まで圧縮することができました。これなら Web で公開しても特に問題ない程度のサイズです。

データの一部を抜粋するとこんな感じになります。こうしてみると結構色に偏りが多いですが、この辺は PNG 自体の Deflate で処理されていると思いたいところです。

描画する

描画は特殊なシェーダを書いて行いますが……実はこれが結構大変でした。

データ転送

状態計算によって求めた OTCAMP のデータを GPU に転送する必要がありますが、一つの OTCAMP の大きさが 2048×2048 と巨大テクスチャに匹敵するサイズなので、毎フレームデータを転送していたのでは遅すぎます。そこで、全体の DAG データを画像で保存したのと同じように、GPU にも同じようにテクスチャとしてグラフ全体のデータを予め転送しておきます。これは起動時の1回で済みます。

すると、特定の状態の OTCAMP の描画を行うためには対応するグラフのノード番号を送るだけで済むようになります。これを全体の DAG データを見ながらシェーダ内部で展開してセルの状態を決定します。

同時に描画する階層は高々2階層[8]で、同じ階層では周期内時刻が一致しているので、全体として 2048 個分の OTCAMP のノード番号を転送すれば十分です。これなら毎フレーム転送しても大した負荷ではありません。

2段階描画

OTCAMP の状態を特定するには周囲のセルの状態を知る必要があるので、2階層を一度に描画しようとすると、2階層目の描画負荷は1階層目の9倍以上になってしまいます。

そのため、中間テクスチャを用意し、1階層目の描画結果を一度テクスチャに格納することで、2階層目の描画負荷を軽減しています。

セルの密度

せっかく OTCAMP を使っているので、OTCAMP を縮小したときにオンであればオンのピクセルを、オフであればオフのピクセルを割り当てたいです。これには四分木の各ノードに記録しておいたオンのセルの個数を用います。

オンの状態の OTCAMP のセルの密度のときに 1、オフの状態の OTCAMP のセルの密度のときに 0 になるような実数値を計算し、色計算で使用します。

モアレの軽減

拡大縮小が非整数倍にできるので、ピクセルの色を ON/OFF の2値で決めてしまうと、強烈なモアレが発生します。

理想的には、各ピクセルが占有する領域に存在するオンのセルの個数をカウントして色を決めるべきですが、データ構造が四分木になっているため、中途半端な位置での積分には大きなコストがかかります。仕方がないので、できるだけ密度変化に対して緩やかに色が変化するようにしてモアレを軽減しています。

Nearest neighbor フィルタリングにミップマップを組み合わせたような形になっています。それなりに見られるレベルにはなりました。

カラフルにする

虹色にしたかったのでしました。

よく観察すると気付くと思いますが、実は色の構造も再帰的になっています。一つの大きな OTCAMP に対して虹色の分布が割り当てられ、拡大していくにつれて小さな OTCAMP がそれぞれ虹色で塗られるように色が変化していきます。


全体の色のパターン


右下を拡大したもの


個別の OTCAMP が見えてくる


再びそれぞれに虹色が割り当てられる

おわり

書ききれないですが、他にも色々と細かい工夫をしてあります。

  • OTCAMP の周期内時刻が OTCAMP の見た目の切り替え時刻とずれていることに注意する
  • オフの OTCAMP を縮小したときに枠が目立たないようにする
  • 拡大を続けたときに中心を僅かにずらす
  • 数万階層以上拡大しても Stack Overflow が発生しないように関数を非再帰化する

大体何かを作るときは最初から実現可能であることが分かっているものを作るのですが、今回は珍しく途中で完全な計算が可能であることに気付いたパターンでした。頑張った甲斐あって世界的に初めての体験ができるコンテンツが作れたと思っています。

開発途中で @phi16_ には色々相談に乗ってもらいました。ありがとうございました。

ソースコードはこちらに置いてあります。


  1. 自身の状態と、自身の近傍の生きているセルの個数のみによって次の自身の状態が決定されるタイプのルール ↩︎
  2. 形は変えられないので、格子状のものに限る ↩︎
  3. 隣接するセルとの通信部分があるので、実際の bounding box はもう少し大きい ↩︎
  4. OTCA Metapixel は Hashlife アルゴリズムを用いて高速に計算できるように設計された ↩︎
  5. このとき、親から親への遷移を繰り返したときにエルゴード性が確保されるように注意する必要があります。そうでないと、せっかく多様な候補を選んでも短い閉路に入り込んで風景の多様性が失われてしまうことがあります。 ↩︎
  6. OTCAMP の状態の特定のためには隣接するセルの状態が必要だったので、本当はこの時点で既に親の展開が必要になります。 ↩︎
  7. 自身を含む近傍 9 セルの状態と、自身の一つ前の状態のこと ↩︎
  8. 1段目は最大 OTCAMP 4つ分のデータを転送しており、2段目の OTCAMP は 2×2 以上の解像度で描画されるようになっているので、ディスプレイの解像度が 16000×16000 に収まらないくらいになってくると描画がうまくいきません。 ↩︎

このエントリーをはてなブックマークに追加