【ツクールMV】キャラクター間の最短距離を計算する
はいどーもツクラー界に始まってツクラー界に終わる無職です。
本日はキャラクター間の最短距離を返すプラグインを公開したので、そちらの制作の過程でも書こうかと思います。
「うるせープラグインさっさとよこせ！」という方はGitHubからどうぞ。
なんで作ろうと思ったか
キャラクター間の最短距離を計算するプラグインを作ろうと思ったきっかけは、ツクマテさんのこちらの記事です。
ご覧の通り、古い記事なのですが、レスが新しくついていたので僕も便乗した感じですね。
最短距離を返すには
RPGツクールMVの経路探索にはA＊という有名なアルゴリズムが使われているそうです（どっかで読んだだけで、アルゴリズム自体は理解してないので本当に使われてるかどうかはわかりません。興味ある人はWkipediaをご覧ください）。
この経路探索アルゴリズムを流用すれば最短距離を計算できそうですね。
A*が使われてい箇所
A*アルゴリズムが使われているのはGame_CharacterクラスのfindDirectionToでしょう。
実装はめちゃんこ長いので省略しますが、以下のシグネチャを持ちます。
findDirectionTo(goalX:number, goalY:number):number
目的地（X座標とY座標）を入力して使用すると、目的地に到達するためにどの方角へ移動すればいいか（このメソッドは向きをnumberとして返すだけで実際の移動は別メソッドに委譲しています）を教えてくれます。
この処理をうまいこと使えばなんだかいけそうですね。
findDirectionToが使われている箇所
次はfindDirectionToが使われている場所を探してみましょう。
するとGame_PlayerクラスのmoveByInputメソッドが該当することがわかります。
このメソッドは「キー入力」と「マウス入力」の両方を処理します（正確にはちょっと違いますが、そこは今はどうでもいいので無視します）。
で、マウス入力の際にfindDirectionToが使われています。
具体的にはマウスでクリックされたX座標とY座標を目的地とし、次に向かうべき方角を決定するという処理のために使われています。
実際の移動はexecuteMoveに委譲されていますが、実はこのメソッドはGame_Characterクラスには実装されておらず、Game_Playerクラスのみに実装されています。
すなわちイベントにはこのメソッドは使えません。
ただexecuteMoveはGame_CharacterクラスのmoveStraightに処理を委譲しているだけですので、経路探索するだけならmoveStraightを利用すればよいです。
探索終了の条件を考える
さて情報が出揃ってきました。
次に決めるべきなのは、探索終了の条件です。
というのもfindDirectionToはあくまでも次に進むべき向きを教えてくれるだけなので、探索を終了すべきかどうかはわかりません（0が返ってきたとき探索終了してもいいかも）。
ここでは以下の条件を満たすとき、探索を終了すべきとします（探索オブジェクトとは、目的地ではなく、目的地へめがけて進んでいるオブジェクトのことです）。
- 探索オブジェクトの周囲4方向に対象がいるとき
- 規定回数探索しても1の条件を満たせなかったとき
最初の条件はいいですね。
もしも8方向探索する場合は、周囲8方向に対象がいる場合となります。
2の条件は、例えば目的地が絶対に到達不能の場所にいるときに探索を打ち切るために使用されます。
もし探索を打ち切らなければ、永遠に探索し続け、プログラムがフリーズしてしまいます。
実際の実装
目的地への最短距離を計算する歳、目的地を探索するキャラクターを動かすわけにはいきません（最短距離を計算したいがキャラクターは動かしたくない、というシチュエーションは存在すると考えたいため）。
ですがfindDirectionToは「現在の場所からどちらの方角を目指せばよいか」しか教えてくれません。
すなわちキャラクターを動かすことが必須となります。
これは困ったため、最短距離を計算する際、ダミーのキャラクター（画面上では見えない）を作成し、動かすことにしました。
そのダミーのキャラクターが1か2いずれかの条件を満たすまで探索を続けるわけですね。
また移動した距離はどこかで記録しておかなければなりません（1歩ずつ進ませるので最短距離がわからなくなる）。
この移動した距離を保存するためだけに一時変数を用いるのはブサイクだと感じたので再帰処理で書いてみました。
ただ開発現場によっては「再起処理は遅いしわかりにくいので書くな」と言われることもあるくらいなので、この辺は好みでしょうね……。
終わりに
いかがでしたでしょーか。
前回公開したプラグインもそうでしたが、短いプラグインなので読みやすいかなと思います。
「プラグイン自分で書いて見たいなあ～！」という方の参考になればなあと思ってこんな記事にしてみました。
なにか参考になれば幸いです。