04/17 14:51 (
@gorry5) 一時期、シードフィルのアルゴリズム研究に凝っていたことがある…というか、シードフィルの速度や機能（タイリングとか）がBASICやアドベンチャーゲームの技術的ウリになった時代がですね… :D https://twitter.com/snapwith/status/1118312700902170627
(mumo)
04/17 15:14 (
@gorry5) シードフィルというのは「注目点のピクセルを塗る→上下左右の隣のピクセルが境界色でなければそこを新しい注目点にする」をずっと（再帰的に）繰り返すことで、閉空間が塗り潰せてしまうというアルゴリズムのことなのだが、これが奥が深い…
(rido)
04/17 15:50 (
@gorry5) まず「次に注目する点の探索（スキャン）」。既に塗り潰したところをまたスキャンするのは大変もったいないので、それを減らすことが最初の課題になる。そこで、ライン単位に分解して効率化しよう…ということになる
(gizi)
04/17 15:50 (@gorry5) 次に「再帰的に繰り返す」作業はスタックを使うのが一般的だが、「再帰で書けることの多くはキューで書いたほうが効率がいい」の法則の通り、シードフィルもこれに従うことが多い (gizu)
04/17 15:50 (
@gorry5) また、その世代の多くのパソコンはスキャンのためのメモリすら貴重だったくらいで、境界・塗り潰し判定用のオフスクリーンバッファなぞ考えようもなかった。よって、表示バッファ（VRAM）から境界色を直接読み出し、塗り潰し色を直接描き込む必要があった
(gize)
04/17 15:50 (
@gorry5) 当時のVRAMは「横8pxで１バイト、それを数プレーン重ねることで多色化」という構造が一般的だったので、ここから１ピクセルの境界色を読み出し、また１ピクセルの塗り潰し色を描き込むのに「何バイトもアクセスしては論理演算を繰り返す」必要があり、これをいかに効率化するかの手腕が問われた
(gizo)
04/17 15:50 (
@gorry5) 更にはこの「何バイトもアクセスしては論理演算を繰り返す」部分がハードウェア支援されるようになり、特定の手法でアクセスすることで単純化できるようになった。いかにこの機能を使いこなすかの手腕も問われるように
(gida)
04/17 15:50 (
@gorry5) また、多色が扱える環境では、「境界色を１つじゃなくて複数選びたい」「塗り潰しも１色じゃなくてタイルパターンを扱いたい」という要求が生まれて、複雑化していく
(gidi)
04/17 15:50 (
@gorry5) ということで、「高機能のシードフィルを効率よく実装する」ことは、単純な考えから始められて、かつ多方面のアルゴリズムやハードウェア知識を要求されるテーマたりうるのであった… :D
(gidu)