Home | Blog (Japanese)

JavaScript 1KBの3Dデモを読んでみる。

2016/5/20

1KBのJavaScriptで作ったデモを競う JS1K の、2014年大会で 3位のMinecraft が驚きのデモっぷり。3Dグラフィックライブラリとか一切使わず、canvasに素のjavascriptで描いているようだ。3Dグラフィックの計算方法はどうやっているのか気になって、1KBなら追いかけられるだろうと読んでみた。

前処理

ソースは こちら。Submission の部分が投稿された生のソースコード。これをコピペしたところ、生のコントロールコードが入っていて化けて扱いづらい。なのでbase64のほうをコピーしてきてpythonでデコードする。 

>>> import base64
>>> base64.b64decode('Zm9yKF89J2F0Wk1aaC5ZWXNpbihYKlhlLzhXKyspVj5zO3NWVWZvcihUVVRvU1hvKVIyNTVRMjU2UCZRT08qUE4xNkw9MDtLS0w+SikrHyYmHiksHV09HD4+Gzw8MRoaMHxhK3ArGTQyMTA5NDMYVHNLF10sFj1bFhVMKhRwWxM5ODU4MTIyLBIxLREsNjMrFFIQZnVuY3Rpb24oD1tkXQ5JbWFnZURaYSgMdmFyIAs9LTE7Mj4JKSpuKyhlCB4oBykqKBFuKQY7VGRLMz5kO2RWcA4FO2VbbCsrHAQ9D2UsdCxuKXtyZXR1cm4DWXJhbmRvbSgpAjEwMjMBdBVuFWU9KGo9Yy5jcmVaZQxNPWEud2lkdGgvPTQsaz1hLmhlaWdodC89NCkpLmRaYTtyAyh0G0wIG0wGGjZ8KHROCE4GTnwodE8ITwZ9O2kDIDQrM1cpVyt0LzUpfTsXMmU3VW89cxsxOCY2MyxuW3Mcbzw9aShzJgEscxsxME8pPzI+bz8xOjI6MDsXAVM9ASoCLHU9USoCLGE9aShvLHUdZglmO2ZWVGwJbDtsVlRwCXA7cFYyPGEHbltvfHUZMRo4HDUpHhFmKmwqcAduW28rZnx1K2wZNBo4HDQpO1RhSmE7YVYXM1NKbztvVlR1SnU7dVZwPRECLzMsZj0yPmE/GDo1PmE/Njk5MDQwMDoSbD1YMip1H3UvOCwRcwdwLz0xLjUrcy8yKR4yPT1hHm8+bCsxB2Y9EnAqPRExL28ddFt1KxQoMTUtbx9QKnMrASphHHIoMCxmLHApO3NldEludGVydmFsKA8pewtvPW5ldyBEWmUvATAsdT1ZY29zKFIdYT1YUh1mPVsUbyUBLGkoFG8lARAfMhAWaBVwFWQ9bT1sSxdrU0tNPm87b1Z7C3Y9by9rLTEsZz1bYSp2K3UsLjURcy9rLGEtdSp2FmI9MzI7VHFLMz5xO3FWewt3PWdbcRZ2PWZbcV0tfn5mW3EWRD0xL3c7MDx3P3Y9EXY6RD0tRDsLST1EKnYFPWYOKyhoDj1nDipEKSp2O1QwPnceE3FdLS07STxiOyl7KHc9blsTMF0mAXwoEzFdJjYzKRo4fCgTMl1PKRowXSkHYj1JLHY9EzAWZD0TMhYRcQd2Kz1kLGQ9EzFdHW09dFsoFHYmMTUfFCgUZCYxNR8BKncrUCpxXSkFKz1oDjtJKz1EfX1tPXIobSwzKhgsYipiLwEpBG0bTE8EbRs4TwRtTwRRfWMucHV0DGosMCwwKX0sTCknO2c9L1teIC1JTVstfl0vLmV4ZWMoXyk7KXdpdGgoXy5zcGxpdChnKSlfPWpvaW4oc2hpZnQoKSk7ZXZhbChfKQ==')
"for(_='atZMZh.YYsin(X*Xe/8W++)V>s;sVUfor(TUToSXo)R255Q256P&QOO*PN16L=0;KKL>J)+\x1f&&\x1e),\x1d]=\x1c>>\x1b<<1\x1a\x1a0|a+p+\x194210943\x18TsK\x17],\x16=[\x16\x15L*\x14p[\x139858122,\x121-\x11,63+\x14R\x10function(\x0f[d]\x0eImageDZa(\x0cvar \x0b=-1;2>\t)*n+(e\x08\x1e(\x07)*(\x11n)\x06;TdK3>d;dVp\x0e\x05;e[l++\x1c\x04=\x0fe,t,n){return\x03Yrandom()\x021023\x01t\x15n\x15e=(j=c.creZe\x0cM=a.width/=4,k=a.height/=4)).dZa;r\x03(t\x1bL\x08\x1bL\x06\x1a6|(tN\x08N\x06N|(tO\x08O\x06};i\x03 4+3W)W+t/5)};\x172e7Uo=s\x1b18&63,n[s\x1co<=i(s&\x01,s\x1b10O)?2>o?1:2:0;\x17\x01S=\x01*\x02,u=Q*\x02,a=i(o,u\x1df\tf;fVTl\tl;lVTp\tp;pV2<a\x07n[o|u\x191\x1a8\x1c5)\x1e\x11f*l*p\x07n[o+f|u+l\x194\x1a8\x1c4);TaJa;aV\x173SJo;oVTuJu;uVp=\x11\x02/3,f=2>a?\x18:5>a?6990400:\x12l=X2*u\x1fu/8,\x11s\x07p/=1.5+s/2)\x1e2==a\x1eo>l+1\x07f=\x12p*=\x111/o\x1dt[u+\x14(15-o\x1fP*s+\x01*a\x1cr(0,f,p);setInterval(\x0f){\x0bo=new DZe/\x010,u=Ycos(R\x1da=XR\x1df=[\x14o%\x01,i(\x14o%\x01\x10\x1f2\x10\x16h\x15p\x15d=m=lK\x17kSKM>o;oV{\x0bv=o/k-1,g=[a*v+u,.5\x11s/k,a-u*v\x16b=32;TqK3>q;qV{\x0bw=g[q\x16v=f[q]-~~f[q\x16D=1/w;0<w?v=\x11v:D=-D;\x0bI=D*v\x05=f\x0e+(h\x0e=g\x0e*D)*v;T0>w\x1e\x13q]--;I<b;){(w=n[\x130]&\x01|(\x131]&63)\x1a8|(\x132]O)\x1a0])\x07b=I,v=\x130\x16d=\x132\x16\x11q\x07v+=d,d=\x131]\x1dm=t[(\x14v&15\x1f\x14(\x14d&15\x1f\x01*w+P*q])\x05+=h\x0e;I+=D}}m=r(m,3*\x18,b*b/\x01)\x04m\x1bLO\x04m\x1b8O\x04mO\x04Q}c.put\x0cj,0,0)},L)';g=/[^ -IM[-~]/.exec(_);)with(_.split(g))_=join(shift());eval(_)"
>>>

こうして得られたのが次のJavaScriptソース。コントロールコードはエスケープ表記されていてエディタで扱える。 

for(_='atZMZh.YYsin(X*Xe/8W++)V>s;sVUfor(TUToSXo)R255Q256P&QOO*PN16L=0;KKL>J)+\x1f&&\x1e),\x1d]=\x1c>>\x1b<<1\x1a\x1a0|a+p+\x194210943\x18TsK\x17],\x16=[\x16\x15L*\x14p[\x139858122,\x121-\x11,63+\x14R\x10function(\x0f[d]\x0eImageDZa(\x0cvar \x0b=-1;2>\t)*n+(e\x08\x1e(\x07)*(\x11n)\x06;TdK3>d;dVp\x0e\x05;e[l++\x1c\x04=\x0fe,t,n){return\x03Yrandom()\x021023\x01t\x15n\x15e=(j=c.creZe\x0cM=a.width/=4,k=a.height/=4)).dZa;r\x03(t\x1bL\x08\x1bL\x06\x1a6|(tN\x08N\x06N|(tO\x08O\x06};i\x03 4+3W)W+t/5)};\x172e7Uo=s\x1b18&63,n[s\x1co<=i(s&\x01,s\x1b10O)?2>o?1:2:0;\x17\x01S=\x01*\x02,u=Q*\x02,a=i(o,u\x1df\tf;fVTl\tl;lVTp\tp;pV2<a\x07n[o|u\x191\x1a8\x1c5)\x1e\x11f*l*p\x07n[o+f|u+l\x194\x1a8\x1c4);TaJa;aV\x173SJo;oVTuJu;uVp=\x11\x02/3,f=2>a?\x18:5>a?6990400:\x12l=X2*u\x1fu/8,\x11s\x07p/=1.5+s/2)\x1e2==a\x1eo>l+1\x07f=\x12p*=\x111/o\x1dt[u+\x14(15-o\x1fP*s+\x01*a\x1cr(0,f,p);setInterval(\x0f){\x0bo=new DZe/\x010,u=Ycos(R\x1da=XR\x1df=[\x14o%\x01,i(\x14o%\x01\x10\x1f2\x10\x16h\x15p\x15d=m=lK\x17kSKM>o;oV{\x0bv=o/k-1,g=[a*v+u,.5\x11s/k,a-u*v\x16b=32;TqK3>q;qV{\x0bw=g[q\x16v=f[q]-~~f[q\x16D=1/w;0<w?v=\x11v:D=-D;\x0bI=D*v\x05=f\x0e+(h\x0e=g\x0e*D)*v;T0>w\x1e\x13q]--;I<b;){(w=n[\x130]&\x01|(\x131]&63)\x1a8|(\x132]O)\x1a0])\x07b=I,v=\x130\x16d=\x132\x16\x11q\x07v+=d,d=\x131]\x1dm=t[(\x14v&15\x1f\x14(\x14d&15\x1f\x01*w+P*q])\x05+=h\x0e;I+=D}}m=r(m,3*\x18,b*b/\x01)\x04m\x1bLO\x04m\x1b8O\x04mO\x04Q}c.put\x0cj,0,0)},L)';g=/[^ -IM[-~]/.exec(_);)with(_.split(g))_=join(shift());eval(_)

プログラムは圧縮されていて、解凍後にevalで実行する仕組み。冒頭で変数 _ に代入している文字列が本体プログラム。解凍＆ランチャー部分はこんな感じ。 

for(_='';g=/[^ -IM[-~]/.exec(_);)with(_.split(g))_=join(shift());eval(_)

同じ文字列を特定の文字に置換することで圧縮している。最後の eval を alert に書き換えれば解凍後のソースが表示される。こうやって得られた本体プログラムが下記。1388バイトある。 

t=[],n=[],e=(j=c.createImageData(M=a.width/=4,k=a.height/=4)).data;r=function(e,t,n){return(t>>16)*n+(e>>16)*(1-n)<<16|(t&255*256)*n+(e&255*256)*(1-n)&255*256|(t&255)*n+(e&255)*(1-n)};i=function(e,t,n){return 4+3*Math.sin(e/8)*Math.sin(e/8+t/5)};for(s=0;2e7>s;s++)o=s>>18&63,n[s]=o<=i(s&1023,s>>10&255)?2>o?1:2:0;for(s=0;1023>s;s++)for(o=1023*Math.random(),u=255*Math.random(),a=i(o,u),f=-1;2>f;f++)for(l=-1;2>l;l++)for(p=-1;2>p;p++)2a;a++)for(s=0;3>s;s++)for(o=0;16>o;o++)for(u=0;16>u;u++)p=1-Math.random()/3,f=2>a?4210943:5>a?6990400:9858122,l=Math.sin(2*u)+u/8,1-s&&(p/=1.5+s/2)&&2==a&&o>l+1&&(f=9858122,p*=1-1/o),t[u+16*(15-o)+256*s+1023*a]=r(0,f,p);setInterval(function(){var o=new Date/10230,u=Math.cos(Math.sin(o)),a=Math.sin(Math.sin(o)),f=[16*o%1023,i(16*o%1023,63+16*Math.sin(o))+2,63+16*Math.sin(o)],h=[],p=[],d=m=l=0;for(s=0;k>s;s++)for(o=0;M>o;o++){var v=o/k-1,g=[a*v+u,.51-s/k,a-u*v],b=32;for(q=0;3>q;q++){var w=g[q],v=f[q]-~~f[q],D=1/w;0d;d++)p[d]=f[d]+(h[d]=g[d]*D)*v;for(0>w&&p[q]--;Id;d++)p[d]+=h[d];I+=D}}m=r(m,3*4210943,b*b/1023);e[l++]=m>>16&255;e[l++]=m>>8&255;e[l++]=m&255;e[l++]=255}c.putImageData(j,0,0)},16)

読解

このプログラムが走る前にいくつかの変数が設定される。詳細は Rules の 9. にあるが、実際のデモページのスクリプトをベースに不要な部分を除去して、minimumな動くプログラムを準備し、徐々に可読化しつつ読んでいった。結果が次のソース。runボタンを押すと動く。 



※全画面モードで動き出すので注意。止めるときはブラウザをreloadする。



全体の流れや、マップとテクスチャ生成の詳細は分かったが、3Dレンダリングの投影計算アルゴリズムはよくわからない。roll/pitchは固定でyaw軸だけ動かしていることは分かる。1KBなので何か簡易な計算方法があるのかと期待したけれどそうでもない。このあたり と同じか。





と、ここまできて作者 Reinder Nijhoff 氏のブログを見たら、解析したのと同じことが書いてあった。orz.
そして3Dレンダリングは ray casting だと書いてある。ray tracing なら知っているが、ray casting というのは初めて聞いた。検索してみるといろいろ見つかる。ああ、そういうことか。










  
  

    

    
    

    

    
  

  
  

    
    
  






















©