アルゴリズム解説

Kacotte!

囲み判定と塗りつぶし処理のアルゴリズムについて。


魔力マップ（配列）を用意します。
この上で魔力ラインの囲み判定と塗りつぶし処理を行います。

_0 _1 _2 _3 _4 _5 _6 _7 _8 _9
0x 00 01 02 03 04 05 06 07 08 09
1x 10 11 12 13 14 15 16 17 18 19
2x 20 21 22 23 24 25 26 27 28 29
3x 30 31 32 33 34 35 36 37 38 39
4x 40 41 42 43 44 45 46 47 48 49
5x 50 51 52 53 54 55 56 57 58 59
6x 60 61 62 63 64 65 66 67 68 69
7x 70 71 72 73 74 75 76 77 78 79
8x 80 81 82 83 84 85 86 87 88 89
9x 90 91 92 93 94 95 96 97 98 99

説明は10×10のマップを前提にします。上記の数字はアドレスです（以後省略）。


魔力ラインの制御のために、オブジェクト管理テーブルに以下の情報を持たせています。

Index# 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
アドレス 　 　 　 　 　 82 83 73 63 53 43 33 34 24 25 26 36 46 56 55
方向 　 　 　 　 　 → → ↑ ↑ ↑ ↑ ↑ → ↑ → → ↓ ↓ ↓ ←

このテーブルのIndex#=99のところはプレーヤーの状態値です。
アドレスはプレーヤーの移動履歴。方向は、プレーヤーがそのアドレスに到達した時点での向きを示しています。
プレーヤーが一歩進むごとに、前側へ1つ分memcopyすることで、各情報を継承しています。


では、オブジェクト管理テーブルの情報をもとにマップ上に魔力ラインを置いてみます。
マスの値としてIndex#を格納すると、プレーヤーの位置「←」を99として、ひとつ前の場所は98、その前の場所は97というように、降順で置かれていきます。

_0 _1 _2 _3 _4 _5 _6 _7 _8 _9
0x 　 　 　 　 　 　 　 　 　 　
1x 　 　 　 　 　 　 　 　 　 　
2x 　 　 　 93 94 95 　 　 　
3x 　 　 　 91 92 　 96 　 　 　
4x 　 　 　 90 　 　 97 　 　 　
5x 　 　 　 89 　 ← 98 　 　 　
6x 　 　 　 88 　 　 　 　 　 　
7x 　 　 87 　 　 　 　 　 　
8x 　 　 85 86 　 　 　 　 　 　
9x 　 　 　 　 　 　 　 　 　 　

（空欄の値は0とします）


上記の状態からプレーヤーが2歩前進、マップでは左側へ2マス移動すると、オブジェクト管理テーブルの中身は以下のようになります。

Index# 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
アドレス 　 　 　 　 　 73 63 53 43 33 34 24 25 26 36 46 56 55 54 53
方向 　 　 　 　 　 ↑ ↑ ↑ ↑ ↑ → ↑ → → ↓ ↓ ↓ ← ← ←

魔力マップは、プレーヤーが移動するたびに最新情報で更新されますので、以下のようになります。

_0 _1 _2 _3 _4 _5 _6 _7 _8 _9
0x 　 　 　 　 　 　 　 　 　 　
1x 　 　 　 　 　 　 　 　 　 　
2x 　 　 　 91 92 93 　 　 　
3x 　 　 　 89 90 　 94 　 　 　
4x 　 　 　 88 　 　 95 　 　 　
5x 　 　 　 87 98 97 96 　 　 　
6x 　 　 　 86 　 　 　 　 　 　
7x 　 　 85 　 　 　 　 　 　
8x 　 　 　 　 　 　 　 　
9x 　 　 　 　 　 　 　 　 　 　

プレーヤーが移動する場所（アドレス53）に値が入っているので魔力ラインが閉じている（上記の場合87-98）と判断できます。
Kacotte!の浄化能力発動は「囲って」ループ状に閉じたことを条件としますので、有効なマーク値は95以下ということになります。
（97にあたった場合は、魔力ラインの長さを0に戻しています）


さて、囲み判定が出たので、塗りつぶすエリア（囲みの内側）が魔力ラインのどちら側になるかを判別します。
オブジェクト管理テーブルの「方向」の情報を拾って、右折は＋１、左折は−１として、どちらにどのくらい方向転換したかを求めます。
起点は閉じた場所なので、Index#87から計算します。

Index# 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
アドレス 　 　 　 　 　 73 63 53 43 33 34 24 25 26 36 46 56 55 54 53
方向 　 　 　 　 　 ↑ ↑ ↑ ↑ ↑ → ↑ → → ↓ ↓ ↓ ← ← ←
転回値 　 　 　 　 　 0 0 0 1 0 1 1 2 2 2 3 3 3

最終的にプラスになりましたので、このループは右回りで閉じたことがわかります。（マイナスであれば左回りです。）
右回りのループなので、各魔力ラインの方向に対して右がループの内側とわかります。
※ちなみに、「矢印の方向＝転回値」ではないので、仮に上記の状態から右折（上向き）すると、転回値は0ではなく4になります。


では塗りつぶしを行います。（このタイミングで、マップの魔力ラインもIndex#87から引き直します。）
魔力ラインに沿ってマップにIndex#を格納しつつ、１マス内側のアドレスを塗りつぶし候補として求めていきます。

Index# 87 88 89 90 91 92 93 94 95 96 97 98 99
アドレス 53 43 33 34 24 25 26 36 46 56 55 54 53
候補 54 44 34 44 25 35 36 35 45 55 45 44 43


この候補データを元に、更にマップの空のマスを埋めながら、新しい塗りつぶし候補を探します。
アドレス54は空ではない（既に魔力ライン98がある）ので読み捨てます。
アドレス44は空なので、ここを埋めます（便宜上★とします）。
そしてアドレス44の上下左右を候補として登録します。

残りの候補 34 44 25 35 36 35 45 55 45 44 43 43 34 45 54

次のアドレス34は90、その次のアドレス44は先ほどの★になっていますので、読み捨て。
これを繰り返していき、候補がなくなったところで塗りつぶし終了です。
魔力マップはこのようになっています。

_0 _1 _2 _3 _4 _5 _6 _7 _8 _9
0x 　 　 　 　 　 　 　 　 　 　
1x 　 　 　 　 　 　 　 　 　 　
2x 　 　 　 91 92 93 　 　 　
3x 　 　 　 89 90 ★ 94 　 　 　
4x 　 　 　 88 ★ ★ 95 　 　 　
5x 　 　 　 87 98 97 96 　 　 　
6x 　 　 　 　 　 　 　 　 　 　
7x 　 　 　 　 　 　 　 　 　
8x 　 　 　 　 　 　 　 　
9x 　 　 　 　 　 　 　 　 　 　


この魔力マップを元にフィールド描画する際、空でないマスに浄化のエフェクトを適用します。