パックマン 解析プログラム動画から見る 追跡アルゴリズム

2020.09.23

この記事は最終更新日から1年以上が経過しています。

どもです。

4連休はいかがお過ごしでしたか？

私ぐらいになると、4連休もあっという間よ。

と言うことで、いきなりですが、今から5年ほど前にこちらの動画がアップされ、皆さんテンションが上がったことかと思います。

いや。俺だけか。

なにはともあれ動画を見てもらえればと。

言わずと知れたパックマンの解析動画なのですが、よくわからない方も動画を見てみると「なんとなく解析しているなぁ」と雰囲気は掴めるかと思います。

こちらLua言語を用いて解析しているみたいなのですが、実際何をやっているか（表示しているのか）を見ていきたいと思います。

まず、パックマンをざっと説明すると、1980年5月2日にナムコが発表されたアーケードゲームで、ドットイートゲームと言われるジャンルの一つで、ドットをすべて食べると１ステージクリアとなります。

また、パワーエサといわれるちょっと大きめのエサを食べると、通常は逃げて回避するしかないモンスターを一定時間食べる事が可能となります。

国内のみならず海外でもブームとなり大ヒットとなったナムコの代表作品のひとつです。

モンスターは４種類存在し、それぞれに特徴があるのもパックマンの面白さの一つでしょう。

そのモンスターの特徴は以下のとおりとなっております。

色	ニックネーム	縄張り	追跡パターン
赤	オイカケ（アカベエ）	右上	粘着タイプ。パックマンの後ろをひたすら追いかける。
ピンク	マチブセ（ピンキー）	左上	頭脳タイプ。パックマンのいる地点の少し前を目指し、先回りするように動く。
水色	キマグレ（アオスケ）	右下	気まぐれタイプ。パックマンを中心にして、オイカケ（赤）の点対称の位置を最短距離で目指して行動する。パックマンのいる通路がその最短距離と被っていた場合、襲われやすい。ただし後述の緊急回避通路やルールの影響でインキーが思うように動けず、明後日の方向に進んでしまう場合もある。
オレンジ	オトボケ（グズタ）	左下	好き勝手タイプ。何も考えず自由に行動する。パックマンより遠いところにいるときは追いかけ、近いところにいるときは逃げる。ただし後述の緊急回避通路やルールの影響でクライドが思うように動けず、追いかけや待ち伏せをしてしまう場合もある。

引用:ウィキペディア（Wikipedia）

モンスター４種類それぞれ行動に特徴があるのが確認できます。

はてこれらのモンスターは、実際どのように動いているのでしょうか？

まず、基本としてモンスターはそれぞれ目標タイルが設定されています。

その目標タイルまでの距離の計算を行いルート選択し移動していきます。目標タイルまでの距離の計算は以下の様に計算されます。

モンスターは、それぞれ設定された目標タイルまでの距離の2乘が最小になるルートを選択し移動していくそうです。

もし、最小になるルートが複数存在する場合は、上、左、下の順を優先に選択される様です。

それでは、各モンスターに設定された目標タイルを見ていきたいと思います。

上記の表から追跡パターンを確認すると、「パックマンの後ろをひたすら追いかける。」とあります。

こちら、アルゴリズム的には「現在、パックマンがいるタイル」が目標タイルとなり、移動して（追いかけて）きます。

ピンキーの特徴は「パックマンのいる地点の少し前を目指し、先回りするように動く。」とありますが、目標タイルは「パックマンの4個先のタイル」となっております。

アオスケの特徴は「パックマンを中心にして、オイカケ（赤）の点対称の位置を最短距離で目指して行動する」となっており、

目標タイルは「アカベエのいるタイルを起点に、パックマンの2個先にあるタイルまでのベクトルの2倍先のタイル」となっております。

グズタの特徴は「何も考えず自由に行動する。パックマンより遠いところにいるときは追いかけ、近いところにいるときは逃げる。」とあります。

目標タイルはパックマンまでの距離で異なり、パックマンまでの距離が8より遠い場合は、「現在、パックマンがいるタイル」となり、8以下の場合は「縄張りモードの所定の位置」が目標タイルとなります。

モンスターが上記の行動をするのが、「追跡モード」と言われるときで、一定時間すぎるとモードの切り替わりが行われ、「縄張りモード」と言われるモードになります。

という事で、色々とアルゴリズムが分かって来たところで再び動画を再び見ていきましょう。

まず、右側が何を表示しているかを見ていきます。

各パラメータは以下の通り。