- City In A Bottle は、256バイトのHTMLにレイキャスティングエンジンと都市生成器を詰め込んだJavaScriptデモ
- 実行は
<canvas> と onclick=setInterval(...) だけで始まり、幅99ピクセルのキャンバスに毎フレームシーンを再描画する
- レンダリングは三角関数を使わず、基本的な代数と ビット演算 だけで処理され、各ピクセルごとにカメラ光線と光源方向の光線を追跡して影を作る
- 都市の形状は
X, Y, Z 座標と X/9^Z/8, X%99, Z>32 のような条件で、建物の高さ、道路、空き空間を分けている
- 最終的な明るさは、距離フォグ、影、
(X&Y&Z)%3/Z テクスチャを fillRect の幅に混ぜて表現し、極端に小さなコードで都市・遠近感・質感をすべて実装している
256バイトHTML内の全体構造
- このデモはJavaScript断片ではなく、有効なHTMLプログラム 1つとして動作する
<canvas style=width:99% id=c onclick=setInterval('for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)* 8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a',t=9)>
- 全体はHTMLコード、フレーム更新ループ、レンダリングシステム、レイキャスティングエンジン、都市生成ロジックに分かれる
- 三角関数や高度な数学の代わりに、基本的な代数とビット演算だけを使っている
- 公開後およそ2年間、作者のTwitterタイムラインで最も人気のあった投稿の1つだった
HTMLと実行ループ
- HTMLはキャンバス1つとクリックイベントだけで構成されている
<canvas style=width:99% id=c onclick=setInterval('',t=9)>
canvas の id を c にすることで、JavaScriptから短く参照できるstyle=width:99% は必須ではなく、なくても動作するonclick で setInterval を呼び出して 更新ループ を開始する
- 間隔は
9 ミリ秒に設定されている
- 時間変数
t もここで 9 に初期化して、文字数を節約している
- キャンバスを何度もクリックすると interval が複数走って遅くなるという小さなバグがある
読みやすく展開したJavaScript
- クリック後に実行されるJavaScriptペイロードは 199バイト
for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)* 8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a
c.width = w = 99
++t
for (i = 6e3; i--;)
{
a = i%w/50 - 1
s = b = 1 - i/4e3
X = t
Y = Z = d = 1
for(; ++Z<w &
(Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46 ||
d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w));)
{
X += a
Y -= b
}
c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)
}
c.width = w = 99 はキャンバスをクリアし、幅を 99ピクセル に設定し、同じ値を w に保存して繰り返し使う- デフォルトのキャンバス高さは150で、それより下の領域は空白になる
++t は毎フレーム時間値を増やし、シーンをアニメーションさせるfor (i = 6e3; i--;) はピクセルごとの明るさを決める外側ループ
カメラ光線の計算
- 各ピクセルは、カメラから出る1本の 光線 として処理される
- 水平方向の成分は
a に保存される
a = i % w / 50 - 1
i % w で現在のピクセルの横位置を取得し、50 で割ってから 1 を引くことで、おおよそ -1 から 1 の間の値に正規化する- 垂直方向の成分は
b に保存され、同じ値が背景フェード用の s にも入る
b = s = 1 - i / 4e3
- 正確な垂直比率計算の代わりに
i / 4e3 へ単純化することで、コードサイズを縮めている
- この単純化により、ほとんど気付かない程度の傾きが生まれるが、バイト数を節約できる
4e3 は地平線を中央より下へ移動させるために選ばれた値- カメラの初期位置は時間値を使い、右方向へ移動するシーンを作っている
X = t
Y = Z = d = 1
Y, Z, 距離フォグに使われる d はすべて 1 に初期化される
都市生成と衝突判定
- 内側ループはレイキャスティングシステムの中核で、何かに当たるまで
Z を前方へ進める
for(; ++Z<w &
Z は w、つまり99より小さい間だけ増加する- 都市の建物、路地、海辺側の空き空間は、次の条件で作られる
Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46
- 光線がその位置の高さより低いかどうかを確認し、衝突の有無 を判定する
6 - は高さの結果を中央より下へずらし、地面が下側に来るよう反転させる役割を持つ- 括弧内の条件が都市の形を決めている
32<Z はカメラと最初の建物列の間に空間を残す27<X%w は周期的な空き空間を作り、道路のように都市ブロックを分割する- 負の値では常に false になり、海のような空白領域が生まれる
X/9^Z/8 はビットXORで建物高さにランダムっぽく見える分布を作る9 と 8 で割る値は建物の幅と奥行きを調整するX/9 は道路幅に関わる数値とともに9で割り切れるため、端に極端に細い建物ができるのを防ぐ
- 括弧の結果は
8 を掛けて 46 で剰余を取り、最大高さの範囲を作る
8 と 46 は多様な建物の高さを生むために試行錯誤で選ばれた値
影、テクスチャ、距離フォグ
- 衝突が起こると、同じ内側ループが2つ目の役割を担い、光源方向のチェック を行う
d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w)
d | は、現在の光線がカメラから出る光線なのか、光の方向へ影を調べる光線なのかを区別する- 最初は
d = 1 なので、カメラ光線として動作する
- 衝突後に
d = Z/w になると1より小さい値になり、ビットOR評価の結果が変わってループが再実行され、影の検査が始まる
- 影の検査中に再び衝突すると、ループを抜けてそのピクセルを影として描画する
- テクスチャ値
s は次の式で生成される
s = (X&Y&Z)%3/Z
X, Y, Z にビットANDを適用し、3 で割った余りを使って、窓のように見えるグレーのテクスチャを作る- さらに
Z で割ることで、遠くのテクスチャが薄く見えるようにしている
- 光線を太陽のような指向性光源へ飛ばすため、
a と b を両方とも 1 に設定する
d = Z/w は距離フォグの値で、遠くの建物を明るくするのに使われる
ピクセル描画と明るさの表現
c.getContext`2d`.fillRect(i%w, i/w|0, 1-d*Z/w+s, 1)
i%w は x 座標、i/w|0 は y 座標になる- 明るさはピクセルの幅を縮める方式で表現されており、小さなコードで グレースケール 画像を作る中核的な手法になっている
1 は黒いピクセルに相当するので、最終式は 1 から値を引いて画像の明るさを作るd * Z/w は影と距離効果を結合する
- 影でなければ光線は最大距離
w まで進むため、Z/w は 1 になる
- 影の中では
Z が w より小さくなり、より暗く見える
- 光を遮る物体が近いほど影が濃くなり、ambient occlusion に似た効果が出る
- 最後に
s を足して、建物テクスチャを最終的な明るさに混ぜる
後続デモと実験ツール
- Revision 2022 demo party に出展され、Pouetで見ることができる
- 当時は誤ったカテゴリに提出されたため、高順位には入れなかった
- その後、ShadertoyでXorやほかのコーダーたちがJavaScript版を再現する 256バイトシェーダー を作成した
- Daniel Darabos は、プログラムのさまざまな要素をリアルタイムで操作できるObservableツールを作成した
- コードは Dwitter でリミックスでき、CapJSでも実験できる
1件のコメント
Hacker Newsのコメント
初期の8ビットゲーム Elite における手続き型生成: https://procedural-generation.tumblr.com/post/112509130817/e...
手続き型生成の一般的な文書: https://en.wikipedia.org/wiki/Procedural_generation
やや関連する概念として、関数型プログラミング言語の 遅延評価 もある: https://en.wikipedia.org/wiki/Lazy_evaluation
あるレイトレーシングアルゴリズムが3Dデータから2D画像を作る際に、見える地点だけを評価するなら、「値が必要になるまで式の評価を遅らせる」という遅延評価の考え方に似ているように見える: https://en.wikipedia.org/wiki/Ray_tracing_(graphics)
さらに言えば、見た目の上では「観測が波動関数を収縮させる」という話ともおおまかに結び付く感じがある: https://en.wikipedia.org/wiki/Wave_function_collapse
ただし、この作品がJavaScriptで作られている点のほうがさらに印象的だ。JavaScriptは通常、16ビットx86機械語よりコード密度が悪いことが多いためだ
ソースコードも含まれている
http://www.youtube.com/watch?v=36BPql6Nl_U
名前は元になった Menger sponge フラクタルに由来する: https://en.wikipedia.org/wiki/Menger_sponge
ここでJavaScriptが大きく有利なのは、標準のdweetライブラリ に sin/cos/fill/line のような機能があることだ。一方、x86 BIOSは「モード切り替え」程度しかしてくれず、その後は単にピクセル配列を直接扱わなければならない
そのため、大規模言語モデルは世界をモデリングする最善の方法ではないのかもしれない、という気がしてくる
自分なら256行くらいで作れたとしても満足しそうだし、実際にはそれよりはるかに多く必要になる気がする
視覚的なものは人工物であれ自然物であれ、多くの場合パターンに従っている。そうでなければ、そもそも認識することすら難しい。だから数学的に活用できることが多い。ハイトテクスチャにはさまざまな種類のノイズやパターンを使えるし、フラクタルも面白く活用できる。また、植生や木にはフィボナッチ数列や黄金比、骨格要素や骨の間にはサイズ比のようなものを使える。こういうところに魔法のような推測マシンは必要ない
Pico-8仮想コンソール向けのツイートサイズのプログラム群だ