04/17 14:51 一時期、シードフィルのアルゴリズム研究に凝っていたことがある…というか、シードフィルの速度や機能（タイリングとか）がBASICやアドベンチャーゲームの技術的ウリになった時代がですね… :D https://twitter.com/snapwith/status/1118312700902170627
(mumo)
04/17 15:14 シードフィルというのは「注目点のピクセルを塗る→上下左右の隣のピクセルが境界色でなければそこを新しい注目点にする」をずっと（再帰的に）繰り返すことで、閉空間が塗り潰せてしまうというアルゴリズムのことなのだが、これが奥が深い…
(rido)
04/17 15:50 まず「次に注目する点の探索（スキャン）」。既に塗り潰したところをまたスキャンするのは大変もったいないので、それを減らすことが最初の課題になる。そこで、ライン単位に分解して効率化しよう…ということになる
(gizi)
04/17 15:50 次に「再帰的に繰り返す」作業はスタックを使うのが一般的だが、「再帰で書けることの多くはキューで書いたほうが効率がいい」の法則の通り、シードフィルもこれに従うことが多い
(gizu)
04/17 15:50 また、その世代の多くのパソコンはスキャンのためのメモリすら貴重だったくらいで、境界・塗り潰し判定用のオフスクリーンバッファなぞ考えようもなかった。よって、表示バッファ（VRAM）から境界色を直接読み出し、塗り潰し色を直接描き込む必要があった
(gize)
04/17 15:50 当時のVRAMは「横8pxで１バイト、それを数プレーン重ねることで多色化」という構造が一般的だったので、ここから１ピクセルの境界色を読み出し、また１ピクセルの塗り潰し色を描き込むのに「何バイトもアクセスしては論理演算を繰り返す」必要があり、これをいかに効率化するかの手腕が問われた
(gizo)
04/17 15:50 更にはこの「何バイトもアクセスしては論理演算を繰り返す」部分がハードウェア支援されるようになり、特定の手法でアクセスすることで単純化できるようになった。いかにこの機能を使いこなすかの手腕も問われるように
(gida)
04/17 15:50 また、多色が扱える環境では、「境界色を１つじゃなくて複数選びたい」「塗り潰しも１色じゃなくてタイルパターンを扱いたい」という要求が生まれて、複雑化していく
(gidi)
04/17 15:50 ということで、「高機能のシードフィルを効率よく実装する」ことは、単純な考えから始められて、かつ多方面のアルゴリズムやハードウェア知識を要求されるテーマたりうるのであった… :D
(gidu)
04/17 15:50 もっとも、今なら大抵のことは「対象サーフェスから境界ピクセルを抽出したサーフェスを作成」「そのサーフェスに対して単純なシードフィル」「シードフィルしたサーフェスをマスクにして、描き込みたい画像を合成」で済んじゃうんだけどね… :D
(gide)
04/17 15:56 余談：効率的なシードフィルを試験するための「複雑な閉空間」を用意する手段として、迷路を生成する手法を覚えると便利。確か初代PC-8801なんかでこの迷路画像にPAINT命令を仕掛けると、スタックオーバーフローで死んだりするんだ…（苦笑
(gudu)
04/17 16:30 (
@sinpen)
@gorry5 んー、アニメも公共放送なら好きじゃ無いし、ドラマも子供向けなら好きじゃないなあ。エロ自体はとても好きなんだけどね。ゲームに関しては、ファミ通とか4gamerとかのゲームサイトでレーティング機能してないのが嫌な感じかな。
(zegi)
04/17 16:39 @sinpen アニメやコミックだと「R18か否か」くらいにしか分けてなくて、ゲームも国内ならその程度にしか分けなくていいや…というのはあるのかな…
(danu)
04/17 16:41 (
@sinpen)
@gorry5 まあボクはゲーム関連の人だからゲームが目につくんじゃないかなあ。この手のゲームにイライラするのも、「メディアが取り扱い分けろよ」と思うよりは、「開発者や広報がメディアの取り扱いに口出せよ（D区分のものがA区分と同じ… https://twitter.com/i/web/status/1118419127142502405
(daze)
04/17 19:03 当時を思い出しながらM88でさくっと迷路生成を書いてみる…道を伸ばすだけの簡単なやつね https://t.co/WS9FjUoHwf
(tohe)
04/17 19:05 で、V2 BASICでペイントしてみたんだけど…これたぶんキュー（リングバッファ）溢れてるね…（苦笑 https://t.co/7GBKd9rXkC
(todo)
04/17 19:29 しかしこれ、いかにも「古の行番号BASIC」らしい「理路整然としたハナモゲラコード」だな…大半の行がGOTOで終わるかGOTO飛び先、変数名は１文字、それでも可能な限り可読性は確保したつもりだが…（苦笑 https://twitter.com/gorry5/status/1118454856551768065
(hira)
04/17 19:32 あーでも、BASICっぽいというよりはむしろアセンブラ風味なのかな…命令数が最小になるようにコードを積んで、ジャンプで繋いで構成する感じ
(huma)
04/17 19:53 @ume3fmp これでGOTO１つ減るかな…あと最初のPSETはループ内になくていいので出すと少し速くなるか https://t.co/jeHXnW94pc
(meta)
04/17 20:51 こうするとGOTOが一切なくなるのだけど、ループ変数の途中書き換え（U=-1）とか、同じ作業を２回書いてる（T=INT(RND(1)*4)）のは、それはそれで美しくないよね…（苦笑 https://twitter.com/gorry5/status/1118480593702940674
(zegi)
04/17 20:59 もうちょっと稼げることがわかった… :D https://t.co/OMmhAh3ZEy
(dapo)