経路探索を追加して敵の群れを移動させる（巫女＆築城＆防衛ゲーム）

フィールド情報のロードが動作し始めたので、敵に建物を避けさせながら移動させるのを目指して作業していきます。

やること

実装する前に、どういう経路探索が必要かを再度検討します。以前にも検討しましたが、こういう実装前の確認は何度やってもいいです。

そしてこれは拠点の建物（神社）を守りきるゲームなので、ほとんどの経路探索で拠点の位置が関係してきます。

経路探索では A* アルゴリズムを使います。
前提としてこのプロジェクトでは地形と建物の編集単位をブロック（2 Unity unit の大きさ）と呼び、ユニットまわりで使う単位をタイルと読んでいます。（1 Unity unit の大きさ）

敵が押し寄せるときの経路探索

基本動作

「このタイルの上にいる敵ユニットはこっちに移動する」という方向をタイルに対して定義し、それに基づいて敵ユニットに速度を加算することで移動させます。

なので、行うべきことは「拠点から敵が使うタイルに拠点への方向を定義すること」になります。よって、

• 敵ユニットが上にいるが方向が定義されていない複数タイルを noRouteTiles として管理する。
• noRouteTiles の１つに対して拠点から経路探索を行い、経路が確定したタイルに方向を定義する。
  • 探索途中で通過した noRouteTiles の要素は削除する。
• A* アルゴリズムでの OpenList とかをクリアせずに上記の noRouteTiles が空になるまで行う。

という処理を行わせます。

敵は石垣や斜面を乗り越えたり建物を壊して進んだりするときには平地よりも移動コストを高くしたいので、重み付きグラフを処理できる A* アルゴリズムにします。

グラフは X, Y の２次元配列で表現して、高低差がないときの移動コストを１で、それ以外のときだけ (from, to) をキーにしたエッジを管理する実装でいいかな、と思います。

迂回の実現

これは後で追加実装すればいいと思うのですが、敵が門の前で渋滞を起こしたり、石垣を登るときに後ろに列を作るのではなく周囲のタイルに広がって登るような「迂回する」動作をさせたいと思っています。

ある程度はユニットが密集してタイルから押し出されるとそれっぽく動作すると思うのですが、そういう迂回する経路が作られるようにもします。

具体的には、想定通りに移動できなかった敵ユニットが「ここの移動コストを上げる」という処理を呼び出すのと先述した「基本動作」の探索を繰り返し行って経路を更新し続ければよいのでは？ と思っています。

なので「基本動作」の経路探索は１フレームに指定ステップだけ行えるような探索処理を小分けに行える実装にします。

ただ、迂回が必要かは敵の出現速度や量に依存しそうなので、実際に動くようになってから再検討したいです。

味方部隊が移動できるかの判定に使う経路探索

敵は石垣は登れるし建物や壁は壊せるのでどのタイルにも必ず移動できることが保証されているのですが、味方部隊については門以外の建物や壁や石垣は移動できないものとして扱います。

そして、味方部隊は敵と違って拠点に近づく移動だけではないので、普通にその時点でのグラフを用いて現在位置から目的地までの経路探索を行わせます。

注意としては、指示した移動先が壁に囲まれてたりしてた場合、経路探索はほぼすべてのグラフのノードを走査した後でないと「経路なかったわ」と判別できません。（いつもより時間がかかる）

なので、最初の実装では「移動元から移動先へ」の経路探索だけでいいと思うのですが、追加で「移動先から移動元へ」の経路探索も同時に行わせようと思っています。
こうすることで、どちらかの走査で経路が確定するか、経路がないことが確定しやすくなるといいなぁ、と思います。

あと、この「移動元から移動先」への走査については、A* アルゴリズムの OpenList とかをクリアしなくてもいいし移動先を決めている最中も走査し続けられると思います。

味方部隊の移動先を UI パネルを決めている最中は、ゲームの時間経過はスローにするつもりなのでリアルタイム的な制約も厳しくないです。

敵が反撃するときの拠点以外がゴールの経路探索

これ、基本的な考えは敵について「移動先を拠点でなく、攻撃してきた相手に変える」だけなのですが、リアルタイムで処理する必要があるし、すっごい遠い経路になるなら反撃しない方が良さそうだしで、後で詳しく考えようと思います。

今のところのアイディアでは

• 攻撃してきた相手に対して経路探索を開始する。
• しきい値以下の移動コストで到達できる場合は移動を開始する。
• 周囲のユニットも同様に反撃の行動を行わせる。
• すでに攻撃中か反撃中の場合は新しい反撃の影響を受けない。

とかです。この時点で小難しいですね。
まぁ、反撃は最悪なくてもいいと思っています。

やったこと

A* アルゴリズムでの経路探索の実装

ここまでのことを念頭に置きつつ、A* アルゴリズムの実装に着手しました。
そして、地形の高低差や建物概念なしの段階で動作させた結果がこれです。

平面で (5, 5) から (15, 5) に移動するときの経路は直線になってほしいので、とりあえず適切ではないです。
ただ、経路自体は生成され始めたので後でまた修正しようと思います。よいです。

設定パネルの作成に着手

なんか疲れててゲームのメインでないあたりに着手してしまいました。
疲れてたら休むべきだぞ？

それはそれとして、今回、UI まわりの実装には買って使ってなかった New UI Widgets を利用します。
なんというか、例えば UI の「タブ」を使いたいとき、自分でも実装できるけど有料アセットパワーで楽をできたらいいな、という想いがあります。

そして、New UI Widgets のデモシーンを確認して「Text でなく TextMeshPro を使うようにしたいなぁ」と思ってソースコードを見ていたのですが、そのあたりは用意されていて Window メニューの項目から可能でした。

よいです。
それからタブについては、Active, Default のときのタブの見た目を用意すると、その見た目を複製して作りたいタブ UI を作ってくれる仕組みでした。

割とよいアセットに思えました。使っていこうと思いました。よいです。

あと、この New UI Widgets アセットでの多言語対応のための仕組みは I2 Localization アセットを使うようになっていました。いずれ作業します。

まとめと今後の予定

経路探索の種類を確認して、実装に着手して動作し始めました。よいです。
それから、気分転換に UI まわりに着手した件については、本当ならもっと後に着手すべきタスクだったと思います。

次回は、経路探索の実装を修正するのと、地形の高低差を考慮した経路になるような修正とか、その結果に基づいて敵を移動させるのとかをやろうと思います。がんばります。