この記事はクソアプリ Advent Calendar 2022の22日目の記事です。
みなさん、『ぷよぷよプログラミング』はご存知でしょうか。
セガが提供している、JavaScriptでぷよぷよを実装するプログラミング教材です。
無料で学ぶことができます。
先日地元のプログラミングコミュニティ鹿児島.mkでこれを題材にした体験会を実施しました。
というわけで画像を連鎖で消すやつを作ってみました
ぷよぷよを実装していくうちに、色んなものを連鎖で消したい欲求がムクムクと湧き上がってきたので、任意の画像を連鎖で消すやつを作ってみました。
こういう画像があるとします。
これを連鎖で消すやつを作りました。
なにをしているのか
このプログラムは以下のような動作をしています
- 画像を100x100pxに縮小する。
- 画像の色を16色に減色する。
- 同じ色が4ドット以上隣接しているドットを消す。
(ただし消える場所が複数ある場合は一番大きい塊だけ消す) - 空いた領域を落下させる。
最初はぷよぷよと同じく4つ以上の塊を一度に全部消す実装にしていたのですが、一瞬でほぼすべてが消失したので「一番大きい塊だけ消す」という制約を加えました。これがないとあまりにも虚無です。
実装の中身
あくまで学習目的で公開されているぷよぷよのソースを参考にしているので、ソースおよびサービスは非公開です。
とはいえ中の実装は色々と工夫しているので、やってることを大まかに解説します。
画像を100x100pxに縮小する
これは特に工夫せず、100x100pxに縮小してCSSで拡大しています。
なぜ100x100なのかというと、処理が重すぎるからです。
最初500x500で実装したところ、ぷよを1回消すために30秒ほどかかりました。
本当は1920×1080で「フルHDぷよぷよ作りました！」と言いたかったのですが、残念ながら最適化が間に合わず100x100になっています。
画像の色を16色に減色する
単純にwebcolorのパレットなどと使って減色すると色が汚くなるので、https://lokeshdhakar.com/projects/color-thief/
というライブラリを使って代表的な色を抽出しています。
たとえば冒頭の画像からパレットを作るとこんな感じです。
街の写真のような色数が多い場合でも代表的な色を抽出してくれます。
同じ色が4ドット以上隣接しているドットを消す & 空いた領域を落下させる
これがメインロジックです。
アルゴリズム
当初はぷよぷよプログラミングを参考に実装していました。
しかしもとのコードは再帰で実装されており、これのせいでスタックオーバーフローが発生したので再帰を使わないアルゴリズムで実装し直しました。
実はこの再帰を使わないアルゴリズム、自分は過去にも実装したことがありました。
マインスイーパーで爆弾のないマスを自動でピッと開く処理がまさにこれです。ペイントソフトのバケツツールで塗りつぶすのもこれです。ぷよぷよとは塗りつぶしなのです。
React+SVGで作ってます。ぜひ遊んでください。
Rust & WebAssembly
今回のプログラム、実装する前からやばいくらい処理が重くなるのは予想されていたので、Rustで実装しWebAssemblyで組み込みました。
自分はこのプログラムを作る前に別のプログラムをWebAssemblyで実装したのですが、そちらはあまりパフォーマンスが上がらなかったので、WebAssemblyは銀の弾丸ではなかったかも知れません。
おわりに
ぷよぷよの実装って普段Webプログラミングする時にはあんまり使わない手法が結構使われてるので、なかなか新鮮味があって面白いです。みなさんもぜひぷよぷよプログラミングに挑戦してみてはどうでしょうか。
それでは最後にAIに作ってもらったお気に入りの3枚の画像を連鎖で消したいと思います。
クリックすると崩壊します。
