塗りつぶしのアルゴリズムをなぜか自分で考えてみた話

世界創造ツールの方でいわゆるペイントでいうところの塗りつぶし処理を作る機会があった。
昔勉強した記憶があるけどなんか忘れてるし、ちょうどその時インターネットがなかったので自分で実装方法考えてみた。

自力実装の結果

いろいろ考えた結果、こうなった。

基点にジャンプ
基点後の動作
1. 基点から東西南北のどこかに動こうとする（東→南→西→北の優先順位。優先順位は別にランダムでもいいけど）
2. 動こうとする場所が動けない場所なら、基点の場所で該当方向に動けないフラグを立てる
3. 動こうとする場所が動ける場所なら、基点の場所で該当方向に移動済みフラグを立て、移動先の場所に移動元への移動フラグ（東へ移動したなら西に移動できないフラグ）を立てて、移動元をスタックに記録した上で基点を移動先に移動する
4. 東西南北すべてに動けない場合、スタックから元の場所を読み込み一つ前に戻る

多分最小ステップだと思うんだけどどうだろう。
わかりづらいからテーブルでも書くか。Xを基点としよう。

o	o	o
o	X	o
o	o	o

Yに移動しようとしている。

o	o	o
o	X	Y
o	o	o

Yに移動できないと、XはYに移動できないという情報を持つ。ちなみにその後の実行コスト削減の問題で、Y自身にも移動不可フラグを立てる。ということでYをZ、Xを仮にAにする。

o	o	o
o	A	Z
o	o	o

次にAがYに移動する。

o	o	o
o	A	Z
o	Y	o

今度は移動に成功したので、AはYに移動済みとなりBになり、YはA以外の場所に移動できると言うことでCになる。

o	o	o
o	B	Z
o	C	o

この後Cはいろいろ動こうとするけど、全部動けない。

o	o	o
o	B	Z
Z	C	Z

東西南北すべて動けないので、基点はCから戻ってBになる。Bの次の優先順位は西なので、西に動こうとする。

o	o	o
Y	B	Z
Z	C	Z

これをひたすら繰り返す。
最終的に最初の基点で移動が出来なくなったら終了。

一般的な実装

今はネットがあるので、せっかくだから答え合わせがてら調べてみる。

独自スタックとか持ってないで再帰使えよハゲってのが一般的な解法らしい。
http://www.etcnotes.info/almath/algofill.html
スタックが関数か独自かってだけでアルゴリズムは同じだけど、移動済みフラグを管理する必要が無い分ずっとシンプルだ。確かにフラグ一個減らせそうとは思ってたんだけどなぁ。くそぅもう一歩だった。

ちなみに線単位で処理してもっと早くしようぜとかの話もあるみたいけど、
http://fussy.web.fc2.com/algo/algo3-2.htm
今回の用途では再帰関数に作り変えるどうかはおいといて、とりあえずシンプルなスタックで別にいいかな。

アルゴリズムの自前実装についての所感

よく車輪の再発明をするなって話があるけど、時々頭の体操としてよくあるアルゴリズムを自分で１から考えてみるのもいい気がするね。
まあ、大抵の場合ぐぐった方が早いけど、うんうんうねりながら最適な解法考え出してプログラム書いてみて、実装してみてにやりとするってのはプログラムの醍醐味の一つだしな。

暇な時はそれなりに面白い遊びではある。
ものっそい暇な時には、さいころの確率計算ツールをちゃんとしたアルゴリズムで作り直したいなぁ。