本文へジャンプ

第3章:迷路ロジックの初歩

手始めとして、ゴーストが目標を遂行するために迷路でどのように移動できるのか、見ていく必要があります。本章で説明するすべての経路探索ロジックは、4体のゴーストに共通しています。ゴーストごとの違いはさておき、まずはゴーストの共通点を理解することが重要です。

先へ進む前にこのゲームにおけるアクター(パックマンと4体のゴースト)の位置がどのように追跡されるのか見てみましょう。ゲーム画面は8×8ピクセルのタイルを敷き詰めたグリッドであると考えてください。

画面の実サイズは224×288ピクセルであり、8で割ると28×36タイルのグリッドが生成されます:

タイルグリッドの図

各タイルはリーガルスペースまたはデッドスペースの何れかに属しています。上記の図では、リーガルスペースは灰色のタイルとして、他のすべてのタイルはデッドスペースとして見なされます。

アクターが移動するのはリーガルスペースのタイル間だけです。各ドットはタイルの中央に配置されるので、正確に8ピクセル(1タイルぶん)離れています。これは、ゲームプレイ中に距離を推定するのに役立ちます。

どのタイルにいるの?

アクターが迷路を移動するさい、ゲームは彼らの占有タイルを常に追跡しています。アクターは同時に1つのタイルにしか関連づけられませんが、そのグラフィックは周囲のタイルと重なり合っています。アクターの中心点は常にその時々でアクターの占有タイルを決定づけます。アクターはピクセル単位の精度で移動できるため、多くのばあいアクターのいるタイルの真上で中央に配置されていません。次の例で考えてください:

6フレームの間に切り替わってゆく占有タイル

半透明な赤いゴーストが、リガールスペースのタイル列を左から右へ移動しています。フレーム1では、占有タイル(明るい赤で表示)は図の左寄りにあります。ゴーストのグラフィックの一部がタイル上にないことは問題ではありません。重要なのはゴーストの中心点がタイル上にあることです。

フレーム2までに中心点が右隣のタイルに乗る十分な距離まで移動し、それに応じて占有タイルが更新されます。ゴーストの中心点が次のタイルに乗るフレーム6までのあいだ、同じタイルに結びつけられます。

ゴーストの経路探索ロジックを理解するためには、タイルの基本概念が不可欠です。これはアクターの占有タイルのみを考慮し、そのタイルにおけるピクセル単位の位置は考慮していません。

ロジック・ルーチンから見ると、5体のアクターは下図のように見えます。

各アクターは現在の進行方向と占有タイルによって定義され、アクター間の距離もタイルで測定されます(たとえばピンクのゴーストは、パックマンから水平方向に5タイル、垂直方向に1タイル離れています)。

ロジック・ルーチンの図

ぴったしのすれ違い

Pac-Manがリリースされてから程なく、プレイヤーのあいだで“時おり無傷でゴーストとすれ違う”という噂が広まり始め、それは一見するとランダムにみえます。多くの粘り強いPac-Manプレイヤーが証明しているように、この噂は完全に真実であることが判明しました。

ゲームをじゅうぶん長くプレイすると、パックマンがゴーストのある一体と衝突しても、向こう側へ無傷ですり抜ける現象を体験します。それほど頻繁には発生しないので喜んでください! 一部のプレイヤーはこの神秘的かつ奇妙なすれ違いをパターンに組み込むことさえしました。

この捉えどころのない特異性の根本原因は、パックマンとゴーストの当たり判定を検出する方法にあります。パックマンがゴーストと同じタイルを占有していれば、常にゴーストと衝突したと見なされライフが失われます。

ゴーストのタイルにパックマンが移動したのか、パックマンのタイルにゴーストが移動したのかは関係がありません。結果はどちらでも同じです。このロジックは、ゲームプレイ中に99%以上のばあい衝突を処理するのに十分であることが証明されていますが、ある1つの非常に特殊なケースを考慮していません。

アカベエとパックマンがすれ違う場面

上記の図は、この奇妙なふるまいを生み出す必要条件を示しています。アカベエとパックマンがすれ違うことを示す5つの連続したフレームがあり、下側には現在の占有タイルおよび中心点(ピクセル単位での位置)で表される同じシーンがあります。この両者は、互いのタイルを同時に交換する丁度いい位置と速度にいます。

つまり、パックマンの中心点がアカベエのタイルへ上向きに移動するのと同じ1/60秒の間に、アカベエの中心点がパックマンのタイルへ下向きに移動するため、結果として両者はぶつかることなくすれ違うことになります。パックマンの中心点がフレーム4のタイル上辺にあることに注目してください。これはまだ下のタイルの内側にあると見なされますが、さらに1ピクセル上へ移動するとパックマンは境界を越えて次のタイルへ押し出されます。

パックマンとアカベエはフレーム5で互いにタイルを交換し、アカベエとまったく“衝突”(つまり同じタイルを共有)しなかったので、パックマンはわが道を行くことができるのです! 以下のYouTubeビデオではパススルー・バグの例を見ることができます(再生開始から40秒後に発生します):

ターゲットタイル

ゴーストが追跡モードまたは縄張モードのときは常に画面のどこか(または画面外)のターゲットタイルに到達しようとしています。これはゴーストがある時点での占有したいタイルを説明する方法にすぎません。

このタイルは所定の位置に固定したり、頻繁に場所を更新したりできます。たとえば、ゴーストが迷路の四隅へ散らばるとき、各ゴーストは常に縄張ちかくの固定ターゲットタイルに到達しようと努めています。

追跡モードでのターゲットタイルは通常(常にではありませんが)、パックマンのいる現在のタイルに関連して頻繁に変更されます。最初は理解しづらいかもしれませんが、ゴーストにとっての追跡/縄張モードの唯一の違いは、ターゲットタイルが配置されている場所です。どちらも同じ経路探索ロジックが適用されます。

将来の展望

ゴーストは迷路上を移動するさい、常に未来への一歩を考えています。ゴーストが新しいタイルに入ると現在の進行方向に沿って次のタイルを先読みし、そこに到着したときにどちらへ進むのか決定します。

最終的にそのタイルに到着すると、事前のタイルで決定した進行方向に変更します。そして同様のプロセスが以後も繰り返され、進行方向に沿ってさらに次のタイルを先読みし、次の進行方向を決定します。

ゴーストが次のタイルを先読みする際にはそのタイルの出口を調べて、進める方向を決定する必要があります。下の図では赤いゴーストがタイルAに到着したばかりで、右から左へ移動しているところです。

そして、直ちにタイルB(進行方向に沿った次のタイル)を先読みします。

各タイルには考慮すべき4方向(左、右、上、下)の出口がありますが、タイルBのばあい上下の出口は壁で塞がれているため候補として破棄する必要があります。右の出口も除外されます。これはゴーストが再びタイルAに戻るだけであり、ゴーストは自発的に進行方向を反転することはないためです。タイルBでは4つの出口のうち3つが除外されているため、残っている選択肢は左へ移動することだけです。

ゴーストがタイルを先読みする場面、この例では左にしか進めない

この例ではゴーストは一方向にしか正しく進めないので、説明は最も簡潔です。そのため、ターゲットタイルがどこにあるのか考慮する必要はありませんでした。リーガルスペースにあるタイルの大部分はこれに似ていますが、ゴーストがより多くの出口を選択できるタイルに近づくと、事態はより興味深いものになります。

交差点

ゴーストが次の交差点から1タイル離れたところに到着すると、先へ進むためにいくつかの進める方向からひとつを選ぶ必要があります。次の例を考えてみましょう:

十字路の交差点で進む方法を決めるプロセス

最初の図では、赤いゴーストがタイルAに到着し、ターゲットを探しています(緑のタイル)。現在の進行方向(上)に沿ってすぐに次のタイルを先読みします。この場合、そのタイルは十字の交差点です。この交差点タイルには出口をふさぐ壁がないのでゴーストは逆方向(下)のみを破棄し、3つの出口を開いたまま移動できます。

残りの3方向でそれぞれ交差点を越えた1つ先の“テストタイル”(白い破線タイル)を収集します。中央の図ではゴーストが各テストタイルからターゲットタイルまでの二点間の距離を求めています。

交差点タイルに到着したゴーストの進行方向はターゲットまでの距離が最も近いテストタイル、この例では右側が最短であり、それに応じてゴーストは交差点タイルで選択方向を更新します。

ときおり、ゴーストに対してターゲットタイルまでの距離が等しい複数のテストタイルが提示されることがあります。以下の例では、赤いゴーストは次の交差点タイルで下へ移動するのか? 左へ移動するのか? 選択を迫られますが、あいにく両者のテストタイルはターゲットまでの距離が等価です(左側の図)。

この均衡を破るためにゴーストは上、左、下、右の順で方向を優先します。上が最優先される方向であり、右は最も後回しになります。したがって、優先リストでは左が下より先行するために、ゴーストは交差点で左へ移動することを選択します。ターゲットを捕捉するには下へ進むべきなのは人には明らかですが、ゴーストはそれほど賢くはありません。彼らは前方の数タイルを見ることしかできず、両者の差異を見分けることは出来ません。

2つのテストタイルは距離が等しいが、優先リストによって左に進む

固定されたターゲット

各ゴーストには、縄張モードで到達しようとする固定ターゲットタイルがあります。下の図は、各ゴーストが縄張モードで使用するターゲットの物理的な位置を示しています(配色は各ゴーストに合わせたもの)。

各ターゲットタイルは、実際には迷路の上端または下端のデッドスペースにあり、ゴーストが到達することは不可能であることに注目してください。このため、各ゴーストはそれぞれの縄張対象にもっとも近い迷路の隅へと向かい、別のモードが発生するまでこの領域で輪を描き続けます。

これが縄張モードの正体です。ゴーストが迷路の“お気に入りの縄張”を持っているのは、決して到達することのない固定ターゲットタイルの位置によるものなのです。

パックマンに噛みつかれたゴーストの目玉が迷路の中央にあるゴーストハウスに戻るさいには、もう1枚の固定ターゲットタイルが使用されています。このターゲットタイルは、ゴーストハウスにある左側の“ドア”の真上にあり、下の図では緑色のタイルとして示されています。

縄張モードのターゲットによって各ゴーストは輪を描く
inserted by FC2 system