artificial-intelligence - パックマン：目はどのようにしてモンスターの穴に戻るのですか？

Question

パックマンで幽霊のAIについて多くの言及を見つけましたが、パックマンが幽霊を食べた後、目が中央の幽霊の穴に戻る方法については言及していませんでした。

私の実装では、単純ですがひどいソリューションを実装しました。どちらの方向に進むべきか、隅々までハードコーディングしました。

より良い/または最良の解決策はありますか？おそらく、さまざまなレベルの設計で機能する一般的なものですか？

score 153 · Accepted Answer

実際、あなたのアプローチは非常に優れたソリューションであり、あらゆる種類のパスファインディングと比較して、実行時間のコストはほぼゼロです。

任意のマップに一般化する必要がある場合は、任意のパスファインディングアルゴリズムを使用できます（たとえば、幅優先探索は簡単に実装できます）。これを使用して、ゲームを実行する前に、各コーナーでエンコードする方向を計算します。

編集（2010年8月11日）：パックマンシステムの非常に詳細なページであるパックマンドシエを参照されました。ここで回答が受け入れられたので、更新する必要があると感じました。この記事は、モンスターの家に戻る行為を明示的にカバーしていないようですが、パックマンでの直接のパスファインディングは次の場合であると述べています。

次の交差点に向かって移動を続けます（これは基本的に'の特殊なケースですが、選択肢が与えられた場合は、次のステップで見られるように、方向を逆にすることを伴わない方向を選択します）。
交差点で、あなたがちょうど来たものを除いて、隣接する出口の広場を見てください。
ゴールに最も近いものを選ぶ。複数の方向が同じようにゴールに近い場合は、最初の有効な方向を上、左、下、右の順序で選択します。

score 86 · Accepted Answer

私はこの問題を一般的なレベルでこのように解決しました。レベルが始まる前に、モンスターの穴からある種の「フラッドフィル」を行います。壁ではない迷路のすべてのタイルには、穴からどれだけ離れているかを示す数字が表示されます。したがって、目が距離68のタイルにある場合、隣接するタイルのどれが距離67であるかがわかります。それがその時の道です。

score 43 · Accepted Answer

従来のパスファインディングアルゴリズムの代わりに、（適切な名前の！）パックマンの香りのアンチオブジェクトパターンを確認できます。

起動時に迷路の周りにモンスターの穴の香りを拡散させ、目を家に追いかけることができます。

匂いが設定されると、実行時のコストは非常に低くなります。

編集：悲しいことに、ウィキペディアの記事が削除されたので、WayBackMachineが救助に...

score 19 · Accepted Answer

ダイクストラのアルゴリズムやA*アルゴリズムなどのパスファインディングアルゴリズムを確認する必要があります。これがあなたの問題です：グラフ/パスの問題。

score 18 · Accepted Answer

動作する単純なソリューションは、保守可能で信頼性が高く、十分に機能するため、優れたソリューションです。あなたはすでに良い解決策を見つけたように私には聞こえます...

パスファインディングソリューションは、現在のソリューションよりも複雑になる可能性が高いため、デバッグが必要になる可能性が高くなります。おそらくまた遅くなるでしょう。

IMOは、壊れていない場合は修正しないでください。

編集

IMO、迷路が修正された場合、現在のソリューションは優れた/エレガントなコードです。「良い」または「エレガント」を「賢い」と同一視することを間違えないでください。単純なコードは、「優れた」「エレガントな」ものにすることもできます。

構成可能な迷路レベルがある場合は、最初に迷路を構成するときにパスファインディングを実行する必要があります。最も簡単なのは、迷路の設計者に手作業でそれを行わせることです。何億もの迷路がある場合、またはユーザーがそれらを設計できる場合にのみ、これを自動化する必要があります。

（余談ですが、ルートが手動で構成されている場合、迷路デザイナーは次善のルートを使用してレベルをより面白くすることができます...）

score 13 · Accepted Answer

オリジナルのパックマンでは、幽霊は彼の「匂い」によって黄色いピルを食べる人を見つけました。彼は地図上に痕跡を残し、幽霊は匂いを見つけるまでランダムに歩き回っていました。プレイヤー。パックマンが移動するたびに、「匂いの値」は1ずつ減少します。

さて、プロセス全体を逆にする簡単な方法は、マップの中央に最高点がある「幽霊の匂いのピラミッド」を作成することです。その後、幽霊はこの匂いの方向に移動します。

score 5 · Accepted Answer

pacmanを追跡するために必要なロジックがすでにあると仮定して、それを再利用してみませんか？ターゲットを変更するだけです。まったく同じロジックを使用してまったく新しいルーチンを作成しようとするよりも、はるかに少ない作業で済むようです。

score 3 · Accepted Answer

それはパスファインディングの問題です。一般的なアルゴリズムについては、http：//wiki.gamedev.net/index.php/A*を参照してください。

score 3 · Accepted Answer

中心までの距離の値を持つ各正方形はどうですか？このようにして、与えられた正方形ごとに、すべての可能な方向で隣接する正方形の値を取得できます。値が最も小さい正方形を選び、その正方形に移動します。

値は、使用可能なアルゴリズムを使用して事前に計算されます。

score 3 · Accepted Answer

これは、それが実際にどのように機能したかについて私が見つけることができた最高の情報源でした。

http://gameai.com/wiki/index.php?title=Pac-Man#Respawn 幽霊が殺されると、肉体のない目が元の場所に戻ります。これは、ゴーストのターゲットタイルをその場所に設定することで簡単に実現できます。ナビゲーションは同じルールを使用します。

それは実際に理にかなっています。たぶん世界で最も効率的ではありませんが、ターゲットを変更しているだけで、別の状態やそれらの線に沿った何かについて心配する必要がない非常に良い方法です。

補足：これらのpac-manプログラマーが、基本的に非常に限られたメモリを備えた非常に小さなスペースでメッセージシステム全体を作成したことがどれほど素晴らしいかはわかりませんでした...それは素晴らしいことです。

score 2 · Accepted Answer

幽霊が穴からパックマンまでたどった道を保存することを提案します。したがって、幽霊が死ぬとすぐに、彼はこの保存されたパスを逆方向にたどることができます。

score 2 · Accepted Answer

あなたの解決策は問題に適切だと思います。それよりも簡単なのは、幽霊の目が壁を通り抜けることができる新しいバージョンをより「現実的」にすることです=）

score 2 · Accepted Answer

これは、ammoQのフラッドフィルのアイデアのアナログおよび擬似コードです。

queue q
enqueue q, ghost_origin
set visited

while q has squares
   p <= dequeue q
   for each square s adjacent to p
      if ( s not in visited ) then
         add s to visited
         s.returndirection <= direction from s to p
         enqueue q, s
      end if
   next
 next

幅優先探索であるという考え方です。したがって、新しい隣接する正方形sに遭遇するたびに、最適なパスはpを経由することです。それは私が信じているO（N）です。

score 2 · Accepted Answer

ゲームをどのように実装したかはよくわかりませんが、次のことができます。

ゲートに対する目の位置の相対位置を決定します。つまり、それは上に残されていますか？真下？
次に、2つの方向のいずれかと反対側に目を動かし（たとえば、ゲートの右側にある場合は左に移動し、ゲートの下に移動するなど）、それを妨げる壁があるかどうかを確認します。
そうすることを妨げる壁がある場合は、反対方向に移動させます（たとえば、ピンに対する目の座標が右北にあり、現在左に移動しているが、途中に壁がある場合）南に移動します。
移動するたびにチェックを続けて、ゲートに対して目がどこにあるかをチェックし、緯度座標がないかどうかを確認することを忘れないでください。つまり、ゲートの上だけです。
ゲートの上だけの場合、壁がある場合は下に移動し、左または右に移動して、目が巣穴に入るまでこの番号1〜4を続けます。
私はパックマンで行き止まりを見たことがありません。このコードは行き止まりを考慮していません。
また、擬似コードの原点にまたがる壁の間で目が「ぐらつく」場合の解決策を含めました。

いくつかの擬似コード：

   x = getRelativeOppositeLatitudinalCoord()
   y
   origX = x
    while(eyesNotInPen())
       x = getRelativeOppositeLatitudinalCoordofGate()
       y = getRelativeOppositeLongitudinalCoordofGate()
       if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
            while (move(y) == false)
                 move(origX)
                 x = getRelativeOppositeLatitudinalCoordofGate()
        else if (move(x) == false) {
            move(y)
    endWhile

score 2 · Accepted Answer

dtb23が提案した、各コーナーでランダムな方向を選択するだけで、最終的にはモンスターの穴の音がひどく非効率になります。

ただし、非効率的な帰宅アルゴリズムを利用して、ゲームの難易度にバリエーションを追加することで、ゲームをより楽しくすることができます。これを行うには、ウェイポイントやフラッドフィルなどの上記のアプローチのいずれかを適用しますが、非決定論的に適用します。したがって、隅々で、乱数を生成して、最適な方法をとるか、ランダムな方向をとるかを決定できます。

プレイヤーがレベルを上げると、ランダムな方向が取られる可能性が低くなります。これにより、レベル速度、ゴースト速度、ピルを食べる一時停止などに加えて、全体的な難易度レベルに別のレバーが追加されます。幽霊が無害な目である間、あなたはリラックスするためのより多くの時間を持っています、しかしその時間はあなたが進むにつれてますます短くなります。

score 2 · Accepted Answer

短い答え、あまりよくありません。:)パックマンの迷路を変更しても、必ずしも目が戻るとは限りません。浮かんでいるハックのいくつかはその問題を抱えています。ですから、それは協力的な迷路を持つことに依存しています。

score 1 · Accepted Answer

ゲームを開始する前に、ノード（交差点）をマップに保存します
モンスターが死んだら、ポイント（座標）を取り、ノードリストで最も近いノードを見つけます
そのノードから穴までのすべてのパスを計算します
長さで最短経路を取る
ポイントと最も近いノードの間のスペースの長さを追加します
パスを描画して移動します

楽しみ！

score 1 · Accepted Answer

pacmanパスがランダムではないことを知っている（つまり、特定のレベル0〜255、真っ黒、まばたき、ピンキー、およびクライドは、そのレベルでまったく同じパスで機能します）。

私はこれを取り、パックマンが幽霊を食べたときに眼球オブジェクトが保留する「リターンパス」として迷路全体をラップするいくつかのマスターパスがあると思います。

score 1 · Accepted Answer

pacmanのゴーストは、目標が達成されるまで、最初にXまたはYで一致しようとするという点で、多かれ少なかれ予測可能なパターンに従います。私はいつも、これは彼らの帰り道を見つける目についてもまったく同じだと思っていました。

score 1 · Accepted Answer

私のアプローチは（パックマン時代の観点から）少しメモリを消費しますが、計算する必要があるのは1回だけで、あらゆるレベルデザイン（ジャンプを含む）で機能します。

ノードに一度ラベルを付ける

レベルを最初にロードするときに、すべてのモンスターの隠れ家ノードに0（隠れ家からの距離を表す）のラベルを付けます。すべてのノードにラベルが付けられるまで、接続されたノード1、それらに接続されたノード2などの外側へのラベル付けを続行します。（注：これは、隠れ家に複数の入り口がある場合でも機能します）

各ノードとその隣接ノードへの接続を表すオブジェクトがすでにあると想定しています。擬似コードは次のようになります。

public void fillMap(List<Node> nodes) { // call passing lairNodes
    int i = 0;

    while(nodes.count > 0) {
        // Label with distance from lair
        nodes.labelAll(i++);

        // Find connected unlabelled nodes
        nodes = nodes
            .flatMap(n -> n.neighbours)
            .filter(!n.isDistanceAssigned());
    }
}

目は最短距離ラベルのある隣人に移動します

すべてのノードにラベルが付けられたら、目のルーティングは簡単です...距離ラベルが最も短い隣接ノードを選択するだけです（注：複数のノードの距離が等しい場合は、どちらを選択してもかまいません）。擬似コード：

public Node moveEyes(final Node current) {
    return current.neighbours.min((n1, n2) -> n1.distance - n2.distance);
}

完全にラベル付けされた例

score 0 · Accepted Answer

私のパックマンゲームでは、shortest multiple path home（ルールのセット内で）提供する迷路で機能する「」アルゴリズムを作成しました。また、それらのトンネルを越えて機能します。

レベルがロードされると、すべてpath home data in every crossroadが空になり（デフォルト）、ゴーストが迷路を探索し始めるとcrossroad path home information、「新しい」交差点に遭遇するたび、または別のパスから既知の交差点で再びつまずくたびに、ゴーストは更新され続けます。

score -2 · Accepted Answer

元のパックマンは、パスファインディングや派手なAIを使用していませんでした。ゲーマーに、実際よりも深みがあると信じ込ませただけですが、実際にはランダムでした。ゲームの人工知能/イアンミリントン、ジョンファンジで述べたように。

それが本当かどうかはわかりませんが、私には非常に理にかなっています。正直なところ、私は人々が話しているこれらの行動を見ていません。彼らが言うように、元の赤/点滅は常にプレーヤーをフォローしているわけではありません。意図的に、一貫してプレーヤーをフォローしている人はいないようです。彼らがあなたをフォローする可能性は私にはランダムに見えます。そして、特に、小さなスペースで4人の敵と非常に限られた方向転換オプションがあり、追いかけられる可能性が非常に高い場合は、ランダムな動作を見るのは非常に魅力的です。少なくとも最初の実装では、ゲームは非常に単純でした。本をチェックしてください、それは最初の章の1つにあります。

artificial-intelligence - パックマン：目はどのようにしてモンスターの穴に戻るのですか？

22 に答える 22

ノードに一度ラベルを付ける

目は最短距離ラベルのある隣人に移動します

完全にラベル付けされた例

Related

Reference