本質的には、私が取り組んでいるパックマン クローン ゲームです。Enemy クラスがあり、このクラスの 4 つのインスタンスが作成され、これらはすべてゲームの 4 つのゴーストを表します。
すべてのゴーストは、画面のランダムな領域で起動し、パックマン キャラクターに向かって進まなければなりません。プレイヤーがパックマンを操作して動かしている間、プレイヤーはパックマンに従い、可能な限りパックマンに近づく必要があります。
迷路/障害物は (まだ) ないため、マップ全体 (400x400 ピクセル) はオープン グラウンドです。
プレイヤーと各ゴーストについて、X、Y、画像の幅と高さの属性を取得できます。また、私はすでに衝突検出アルゴリズムを持っているので、それについては心配していません。幽霊がパックマンへの道を見つけているだけです。
ピクセルのグリッド (パックマンとゴーストが自由に動き回れる「大きなフィールド」) がある場合、最短経路は簡単です。つまり、ゴーストとパックマンの間の直線です。
しかし、「最短経路」とは常に、グラフ理論の問題を解決しようとしていることを意味します。(グラフ、いくつかのグラフ理論、調整行列などの知識があることを前提としています!)
上記の場合、各ピクセルをグラフ上のノードと見なします。各ノードはエッジによって隣接するノードに接続され、各エッジの「重み」は等しくなります (「上」のノードへの移動は、「下」のノードへの移動よりも遅くはありません)。
したがって、次のようになります: ("*" = ノード、"-、/、\、|" = エッジ)
*-*-*
|\|/|
*-*-* ... (etc)
|/|\|
*-*-*
パックマンが中央にある場合、他のノードに非常に簡単に移動できます。
より現実に近いものはこれかもしれません：
*-*-*
| | |
*-*-* ... (etc)
| | |
*-*-*
これで、パックマンは斜めに移動できなくなりました。中央から右下に移動するには、1 回ではなく 2 回の「ホップ」が必要です。
進行を続けるには:
*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*
ここで、中間のノードから最上部のノードに移動するには、3 つのホップが必要です。ただし、一番下に移動するには 1 ホップしかかかりません。
ゲームボードのセットアップをグラフに変換するのは簡単です。各「交差点」はノードです。2 つの交点の間のパスがエッジであり、そのパスの長さがエッジの重みです。
入力します*。グラフを作成する (隣接行列またはノードのリストを使用する) ことにより、A* アルゴリズムを使用して最短経路を見つけることができます。他のアルゴリズムにはダイクストラのものがあります。などなど！しかし、最初にグラフの観点から問題を組み立てる必要があります。次に、ノード A (パックマン) からノード B (ゴースト) に移動する方法をいじります。
それが役立つことを願っています!
非常に長い時間が経ちましたが、記憶によると、パックマンのゴーストはパスファインディングの方法であまり機能しませんでした. 彼らは、あなたを「発見」するまで、かなり標準的な無作為化された迷路横断を行います。これには、あなたに向かって回廊の軸に沿って遮るもののない道を見つけることが含まれます。ランダムなパターンを再開します。より高いレベルでは、パックマンはしばらくの間彼の後ろに目に見えない道を残し、幽霊が「におい」を感じ、時にはそれをたどります.
パックマンがパワーアップしたときのアルゴリズムの唯一の違いは、彼らがあなたを見つけたとき、ゴーストはあなたに向かって移動するのではなく、あなたから逃げるということです.
したがって、本物の体験を得るためには、非常に洗練されたパスファインディング アルゴリズムはおそらくまったく必要ありません。もちろん、派手にしたい場合は、A* を実装できます。
敵に向かってまっすぐ歩くことから始めますが、迷路を追加するときは、幽霊が曲がり角や行き止まりに引っかからないように、もう少しスマートなパスファインディングを追加する必要があります.
次のチュートリアルは、ダウンロード可能な例を含む、A* を使い始めるための優れた軽量ガイドです。
パックマンでは、すべての幽霊が異なる追跡アルゴリズムを持っていました
幽霊の動きには興味深いパターンがプログラムされています。時折、パックマンの追跡を停止して停止し、迷路のそれぞれの隅に戻って「散乱モード」に入ることがあります。
パックマンの書類にアルゴの完全な説明があります
よろしく
ギヨーム
pacmanが行うすべての動きで最短経路アルゴリズムを選択すると思います。非常に優れた実装は、ダイクストラのアルゴリズムです。
要約すると、迷路を頂点とエッジのあるグラフとして視覚化します。各エッジには待機があります（この場合、すべてのエッジの重みは同じです）。アルゴリズムは、すぐに到達可能な各エッジを1ステップ下に移動することにより、ソース頂点からターゲット頂点への最短パスを見つけます。次に、次の頂点で同じことを行い、ターゲットに到達するまで続けます。最初に到達するパスが最短パスです。このアルゴリズムには多くの最適化を行って、pacmanが前の位置にあった場所や移動した方向を考慮に入れて、アルゴリズムのヒューリスティックを取得できるようにするなどの処理を行うことができます。すべての動きで各ゴーストからパックマンへの最短経路を見つけて、ゴーストをその方向に動かすことをお勧めします。やがて距離が縮まり、パックマンを捕まえることができるようになります。
これを使用して、pacmanから到達可能なすべての直接エッジを見つけ、ゴーストがこれらの頂点をできるだけ多くカバーしようとすることができる別のヒューリスティック。したがって、pacmanをターゲット頂点として設定する代わりに、pacmanがすぐに到達可能な頂点をターゲットとして設定します。その結果、使用可能なゴーストがpacmanの主要な脱出ルートを覆い隠して彼を捕まえようとします。
A* (A スター) を見始めることができます
そして、これは他の経路検索アルゴリズムへのリンクがあるページです。
[編集] うーん... 脳が遅すぎる... この本のことを忘れていた、それは C または C++ (どちらか忘れた) ですが、Java の概念はまだ理解できます。読みにくいかもしれませんが、全体的に悪くはありません。 David M. Bourg、Glenn Seemann によるゲーム開発者のための AI。