PICO-8 でセルオートマトン

2019年2月24日 23:27

PICO-8 で作った Starwars というルールのセルオートマトンを公開した。今日はそのパフォーマンスと PICO-8 の話を中心に書こうと思う。
ローグライク（仮）の作業は今日はなし。

実行の仕方

このサイトで実行できるようになっている。ソースコードも閲覧可能だ。しかし実に遅い。それには理由がある。それについて今日は色々考えたことや説明を書いた。

PICO-8 の処理速度について

PICO-8 というコンソールは様々なプラットフォームで動作する。例えば Windows/macOS 以外にもブラウザだったり Rasberry Pi だったりでも動く。Fantasy Console （架空のコンソール）とも言われていて様々な実行環境で同様の性能が出るように、またレトロコンソールをエミュレートすることが目的であるため、計算処理の速度は意図的にその環境の最高速度を出さず、一定の上限を設けていると思われる。これはドキュメントを探したけど見つからなかったことなので、憶測ではある。

例えばだが、こういうコードを書いてみた。特に何か有益なことを実行するわけではないコードだが、処理フレームでは t をインクリメントし、run() という関数を実行し、描画フレームごとに t の値を表示するようにしている。つまり実行開始時から update が何回呼ばれたかが表示されているということになる。

function run()
 for y = 0, 99 do
   for x = 0, 99 do
     for i = 0, 9 do
     end
   end
 end
end

t = 0
function _update()
 t = t + 1
 run()
end

function _draw()
 cls()
 print(t)
end

run の中身は 100 x 100 x 10 (= 10000 回) のループを実行している。ループ内は何も実行していないが最適化は行われないようなので、これで run の実行時間は 30FPS を保てないほど遅くなる。これを 100 x 100 x 5 にすると 30FPS を保つことができる。

function run()
  for i = 0, 9999 do
    for i = 0, 9 do
    end
  end
end

run() をこんなふうに同じループ回数で別の書き方にしても同じく 30FPS は出なくなる。ちなみに PICO-8 では数値は最大 32767 なので、for i = 0, 99999 do ... という記述をすると意図通りに実行されないので注意。

では、僕の今使っている iMac で同じコードを luajit で実行してみたらどうなるか。やってみると、秒間2万回 run() が実行できた。30FPS (秒間30回) を達成するためには 0.0333 秒以内で run() が実行できればよいが、luajit では 0.00005 秒で run() を実行できる。666 倍の実行速度が出ているのだ。

処理系が異なるので安直な比較になるのだが、少なくとも PICO-8 ではオーバーヘッドが引き起こす速度低下を遥かに下回る実行速度であり、やはり意図的に実行速度に制限を掛けていると考えて良い。

セルオートマトンの実行速度について

今回作ったセルオートマトンは2次元の4状態8近傍総和型の世代ルールである。広さは 99 x 99 で、およそ1万セルある。このセルは生きている・死にかけている・更に死にかけている・死んでいる、の4つの状態を持っている。ま8近傍とはあるセルの周囲8セルの状態に依存して計算される、ということだ。

この計算は 99 x 99 ごとに 8 個のセルの状態を取得し条件分岐の結果セルの状態を変更する、ということを行うことになる。これを1フレームで実行しなければ描画に間に合わなくなる、というわけである。

単純に計算しても 99 x 99 x 8 = 78408 となり、先程のループである 10000 x 10 = 10万に届きそうな量となる。しかし、先程のループには何かを実行するコードは入っていない。当然セルオートマトンのループの中では変数にアクセスしたり計算したり条件分岐したり、そういったコードが含まれる。つまり 30FPS は間に合うわけがないのだ。

これだと、当初の目的である Panic shooter の移植は不可能である。どうしたものか。

実行速度を改善するための案（ビットボード）

ビットボードというアルゴリズムを使う手を考えた。ビットボードというのは、将棋や囲碁、オセロなどの解析・AI などで使われている技術で、2次元のボードをビット演算を用いて高速に計算する方法だ。これをセルオートマトンでも使えるように C++ で実装したことがあり、ローグライク（仮）でも使っていたりする。オープンソースにしているのでご覧いただければビットボードが何たるかがわかるかと思う。

コードは例えばこんなふうになっている。見て分かっていただけると思うが、非常に可読性の悪い、そしてこれで何故セルオートマトンが計算できるのかよくわからないコードだ。これを実装したのは10年以上前なので自分でもわからなくなっている。だが、この可読性の悪さは改善がとても難しい。なぜなら可読性は高速化のために犠牲になっているからだ。

大雑把に言うと、64bit のビット列を 8 x 8 のセルに見立てて計算する方法をビットボードという。このアルゴリズムを使うと、なんと近傍セルの合計を取得するのに条件分岐は一切不要だったりする。さらに 1 セルごとではなく 64 セルを同時に計算することにもなるので高速化につながっている。ビット演算のみで計算することは CPU 最適化にも大きくメリットが有る。理由を解説すると長くなってしまうので知りたい方はコードを読んでいただきたい。（なお、ビットの並列計算といえば GPU の得意分野で、GPU でも同じアルゴリズムを使えば更に多くのビットを同時に処理できるし、CPU とは分離して実行できるためさらに高速に計算できる。）

PICO-8 でビットボードを使う？

では、これを PICO-8 で実装するにはどうしたらよいか。

まず PICO-8 の Lua は改造されており、通常の Lua におけるビット演算子は使えなくなっている。そのかわり、band, bor, bxor, shl, shr などの関数が用意されている。

この関数は符号付き16ビット整数用になっているようだ。

print(shl(1, 14)) -- -> 16384
print(shl(1, 15)) -- -> -32768

そのため、先程解説した 64bit のビットボードは使えず、その 1/4 の 16bit でビットボードを実装しなくてはならなくなる。先程のコードを見てもらえばわかるが、これを 16bit で動くように再実装するのは骨が折れる。

また同時に計算できる量も 64 セルではなく 16 セルに大幅に減少する。通常の 1 セルごとの処理に比べれば 16 倍の実行速度が出ると考えがちだが、これは間違っている。なぜなら、先のコード通り長々と計算式を記述することになるからだ。16 セルを同時に計算できたとしても各セルに掛かる時間が 16 倍になってしまえば意味がない。そして次に説明する通りおそらく 16 倍以上となるだろう。
ビットボードを使わない 1 セルの処理は、近傍セル用の 8 回のメモリアクセス、条件に一致するかの判定、その判定により 1 回だけメモリに変更を加える、という単純なものだ。それにくらべてビットボードでは何度も何度もビット演算を行う。最適化も期待できず、律儀にビット演算関数を呼び出すと数十回〜百数回の演算を 16 セルごとに実行するようなコードになるだろう。

以上の理由から、ビットボードは適していないと結論を出した。

他の道は？

PICO-8 のドキュメントを読み、何かしらのハックができないか考えている最中だが、

さきほどこのドキュメントを見たが、あまり役に立つ情報はなかった。どうしたらいいのだろうか。よく考えれば、MSX やファミコンで Panic shooter を実装することは出来そうにない。これと同じことが PICO-8 でも言えるのではないだろうか。

というわけで、Panic shooter は残念ながら諦めるが、せっかく PICO-8 を買ったので他に実装できそうなゲームを気楽に作ってみようと思う。

応援してくださると嬉しいです。よろしくお願いいたします！