目次
1.はじめに
ここでは、戦術SLGの作り方について説明をします。
「戦術SLGの作り方（移動範囲を求める）」では、移動範囲の求め方を紹介しましたが、今回はその応用として、AIの移動アルゴリズムを紹介します。
2.基本編
まず最初は、「移動可能な範囲にプレイヤーがいる」といったシンプルなモデルで考えてみます。
最短移動距離を求める
この表は、前回の最後で求めた、移動範囲の検索結果です。
黄色の部分にプレイヤーがいるとします。
人間であれば、上→上→右（攻撃範囲を考えると右は必要ない）と瞬時に答えが出ますが、コンピュータはそうはいきません。
最短距離で移動させるアルゴリズムとしては、
- 経路探索開始地点をプレイヤーがいる地点（黄色）とする
- 数値が増加する地点に移動する
といった方法を用います。
探索方法は、前回の移動範囲探索処理と同じく上下左右を再帰処理で探索し、コンピュータのユニット（赤色）がある地点のとなりまで探索できれば、探索完了です。
実際に考えてみましょう。現地点は「0」です。
上・右は「-1」と数値が減少しているので、条件に反します。下も「-9」なので、除外します。左が「1」と増加しているので、こちらに進みます。
次を考えてみます。現地点は「1」です。右・上・左は「0」なので、下に進みます。
これで探索は完了です。移動範囲を大きくしても、このアルゴリズムが有効となるはずです。
3.応用編
移動範囲外の索敵方法
応用として、移動範囲外にプレイヤーがいる場合を考えてみます。その場合の問題としては、「障害物に引っかかってしまう」という問題があります。
例えば、以下のケースです。□がコンピュータで、△がプレイヤーとします。
これはこれで、「頭の悪い」という設定のキャラならオッケーと思いますが、「天才戦術家」という設定のキャラだとしたら、これでは説得力がありません。
この引っかかりという問題を解決するには、以下の方法があります。
- 探索範囲を広げ、力技で移動経路を求める
- 移動経路をテーブルで保持しておく
そもそも障害物に引っかかるようなマップを用意しない1の方法を用いると、処理が膨大に増えるため、あまりオススメはしません。
3は消極的にみえますが、こういった方法もアリであると思います。方法としては、例のような「上と右」の「２方向を塞ぐ」地形を作らないようにします。
2の方法はどういうことかというと、例えば次のようになります。赤い部分を「エリアA」、青い部分を「エリアB」とします。
コンピュータが「エリアA」、プレイヤーが「エリアB」にいる場合、濃い赤の経路をたどり移動します。コンピュータとプレイヤーが同じエリアにいるときは、このアルゴリズムを使用せずに、単純にプレイヤーがいる方向へ移動します。
このように、経路をあらかじめ決めておくことで、最短距離での移動が可能となります。
移動範囲外の索敵方法（補足）
ただ、単純にプレイヤーに近づくアルゴリズムが正しい、とは必ずしもいえません。他にどんなアルゴリズムがあるかを列挙してみます。
- 自分の攻撃範囲がギリギリ届く地点に移動する
- 次ターンにプレイヤーが移動し、その上での攻撃範囲にギリギリ入らない地点に移動する
- ある範囲を守る（倒されるとクリアとなるキャラを守る、など）
- プレイヤーとは逆の方向に移動する（逃げる、など）
さらに補足
ここではやや力技っぽい経路探索を行いましたが、A*アルゴリズムという最適解がありますので、「A*アルゴリズム」で別途解説を行なっています。
