敵の移動アルゴリズム

■これは何?

ここでは敵をどのように移動させるかについて書いたものです。

■パックマンの敵のアルゴリズム

パックマンの生みの親の岩谷徹氏によると、プログラマーに「パックマンが四方八方からモンスターに囲まれるように」という注文を出したところ、

  1. 追跡タイプ(アカベイ)
  2. 待ち伏せタイプ(ピンキー)
  3. プレイヤーと点対称に動くタイプ(アオスケ)
  4. ランダムに動くタイプ(グズタ)

という4つのアルゴリズムを用意したそうです。そして休息状態時には縄張りを「巡回」、パワーエサを取った時に「逃走(イジケ)」状態、イジケ復帰後は休息状態に戻ります。

これを元に移動パターンを考えてみます。

■移動パターン類型

以下は個人的な類型です。

移動パターン名説明
追跡型プレイヤーを愚直に追いかける
迎撃(先読み)型追跡型の派生。プレイヤーが数フレーム後に移動するであろう座標を、先読みして移動する
逃走型追跡型の逆。プレイヤーとは逆の方向に逃走する
待ち伏せ型迎撃型の派生。通常は隠れているがプレイヤーが近づくと追跡・迎撃をする
間合い確保型プレイヤーと一定の距離を確保するタイプ
直角移動型間合い確保型の派生。一定距離を取りつつプレイヤーの周りを囲むように動く
評価値計算型プレイヤーにとって評価値の高い座標を狙って移動する
巡回型プレイヤーの行動とは関係なく、特定の座標に向けて移動する

これを元に説明をしたいと思います。

▼追跡型

プレイヤーを愚直に追いかけるタイプです。

このタイプは、単純ながらもゲーム的にかなり有効だったりします。

それは、

  • 「耐久力が高い」または「数が多い」場合にゴリ押しできる

というメリットがあるからです。

例えば、ピンクスウィーツのステージ4では、プレイヤーを誘導する耐久力の高い敵や、高速で大量に発射される誘導弾が飛び交うため、何も考えずローズクラッカーを連発しているだけでは、すぐにやられてしまいます。

ただ、追跡型は行動パターンを読みやすいため、

  • 待ち伏せ

をされるとあっさりやられてしまいます。

また、

  • 狙った場所に誘導しやすい

ということもあります。(つまり、ピンクスウィーツの例では、攻略するには敵をうまく誘導する必要がある)

実装方法は簡単です。

プレイヤー座標から敵座標を引いて(P’)、

 P1(プレイヤー座標)-P2(敵座標)=P'

P’を正規化し(||P’||)、移動量をかけてやれば求めることができます。

 追跡移動量=||P'|| × 移動量

▼迎撃(先読み)型

迎撃とは、プレイヤーが数フレーム後に移動するであろう座標を、先読みして、そこに移動するタイプです。

追跡型よりも、行動パターンが読みにくいのが特徴です。

ですが、プレイヤーが全く移動しないと、追跡と同じ移動量になるので、結局、待ち伏せには弱かったりします。

実装方法です。手順は、

  1. プレイヤーと敵の相対速度(Vr)を求める
  2. プレイヤーと敵の相対距離(Sr)を求める
  3. |Sr|÷|Vr|で接近時間(Tc)を求められる

となり、Tcから、

 プレイヤー座標+プレイヤー移動ベクトル×Tc

により、迎撃ポイントを算出することができます。

念のため式を書いておくと、

  • プレイヤーの現在座標をSp
  • プレイヤーの移動ベクトルをVp
  • 敵の現在座標をSe
  • 敵の移動ベクトルをVe

とすると、

  1. Vr=Vp-Ve
  2. Sr=Sp-Se
  3. Tc=|Sr|÷|Vr|
 迎撃ポイント=Sp+Vp×Tc

となり、

 迎撃移動量=||迎撃ポイント-敵座標||×移動量

となります。

▼逃走型

追跡型の移動ベクトルを逆にするだけ。使い道としては、中〜長距離が得意な敵がプレイヤーに接近した時にこの移動タイプを選択します。

▼待ち伏せ型

普段は隠れていて、プレイヤーと敵との距離が「ある一定の値以内」となった場合に、追跡・迎撃型となるタイプです。強力な攻撃力を持つ敵がこのタイプである場合、対処が非常に困難になります。

▼間合い確保型

プレイヤーと敵との「距離を常に一定」に保とうとするタイプです。プレイヤーの有効な攻撃範囲に入らず、敵の有効な攻撃範囲であるギリギリの距離を保たれるとたぶん倒せませんので、接近手段をプレイヤーに与えるか、ほどほどにしておいたほうがいいです。

▼直角移動型

プレイヤー座標と敵座標を結んでできた線から直角の方向へ移動するタイプです。

固定画面シューや全方向シューなどで、プレイヤーとの距離をとりながら、遠距離攻撃をするような敵に向いています。また、この移動量を毎フレーム求めてやると、プレイヤーの周りをぐるぐる回るといった動きになります。

移動量の求め方は、相対距離のベクトルから角度を求めて90°を加算・減算したり、ベクトルをZ軸まで拡張して、法線ベクトル(0, 0, 1)をかけても求めることができます。

▼評価値計算型

評価値の高いスペースを狙うタイプです。例えば、シューティングでは画面の中心は弾を避けやすいため、プレイヤーは中心に移動しようとします。そこを狙います。

また、アイテムをプレイヤーが取りに行こうとするのを狙うのもありです。

▼巡回型

例えば宝石を守るモンスターなどの性格付けとして使われます。この場合は宝石がある座標の周りをぐるぐると巡回します。

他にも見張りの番兵であれば、あらかじめ決められたルートをたどる、というタイプもあります。

■参考

▼資料:パックマンの敵のアルゴリズム

名称タイプ追跡モード休息モード補足
アカベイ追跡型パックマンの現在マスを最短距離で追跡画面右上付近を動き回る
ピンキー待ち伏せ型パックマンの進行方向の3つ先のマスに向かう画面左上付近を動き回る
アオスケ点対称型パックマンを中心にしてアカベイの点対象のマスを目指す画面右下付近を動き回る
グズタランダム型パックマンから半径約130ドット外ではアカベイと同じ追跡方法、半径130ドット内ではパックマンの移動に関係なく動く画面左下付近を動き回るパックマンに近づき過ぎると移動方向が逆転する

あと、イジケ状態の移動は逃走かと思ったのですが、どうやらランダムっぽいですね。