第３章：迷路ロジックの初歩

どのタイルにいるの？

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

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

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

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

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

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

ぴったしのすれ違い

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

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

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

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

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

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

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

ターゲットタイル

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

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

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

将来の展望

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

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

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

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

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

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

交差点

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

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

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

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

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

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

固定されたターゲット

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

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

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

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