Java 2dゲームでのパス検索？

StackOverflow https://stackoverflow.com/questions/623095

質問

本質的には、私が取り組んでいるパックマンクローンゲームです。 Enemyクラスがあり、このクラスの4つのインスタンスが作成され、これらはすべてゲームの4つのゴーストを表します。

すべてのゴーストは画面のランダムな領域で起動し、その後パックマンキャラクターに向かって進む必要があります。プレイヤーがパックマンを制御し、それを動かしながら、彼らはそれに追従し、彼に向かって可能な限り最も近い方法を取るべきです。

迷路/障害物はまだないので、マップ全体（400x400ピクセル）がそれらに対して開かれています。

プレーヤーと各ゴーストについて、X、Y、画像の幅と高さの属性を取得できます。また、私はすでに衝突検出アルゴリズムを持っているので、それについては心配していません。ゴーストがパックマンへの道を見つけることについてだけです。

役に立ちましたか？

解決

適切な経路探索アルゴリズムの場合、 A * を使用することはおそらく良い考えです。ただし、洗練された、効率的な、または効果的なパス検索を必要としないシンプルなゲームの場合、ターゲットの方向を見つけてキャラクターをターゲットに向かって移動させるだけで十分です。

たとえば、擬似コードでキャラクターを移動させる決定：

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

はい、キャラクターは最も効率的な動きをするつもりはありませんが、ゲームループの各反復でターゲットにどんどん近づいていきます。

また、80年代前半のアーケードゲームではおそらく高度な経路探索アルゴリズムを使用しないと思います。

他のヒント

ピクセルのグリッドがある場合-「大きなフィールド」パックマンとゴーストが自由に動き回ることができます-最短経路は簡単です-ゴーストとパックマンの間の直線。

ただし、「最短パス」常にグラフ理論の問題を解決しようとしていることを意味します。 （グラフの知識、いくつかのグラフ理論、調整マトリックスなどを想定しています！）

上記の場合、各ピクセルはグラフ上のノードであると考えてください。各ノードはエッジによって隣接ノードに接続され、各エッジは等しい「重み」を持ちます。 （「上」のノードへの移動は、「下」のノードへの移動より遅くありません。）

これで次のようになります：（＆quot; *＆quot; = node、＆quot;-、/、\、|＆quot; = edge）

*-*-*
|\|/|
*-*-*  ... (etc)
|/|\|
*-*-*

パックマンが中央にある場合、他のノードに非常に簡単に移動できます。

より現実に近いものは次のとおりです：

*-*-*
| | |
*-*-*  ... (etc)
| | |
*-*-*

現在、pacmanは斜めに移動できません。中央から右下に移動するには、「ホップ」が2つ必要です。 1つではなく。

進行を継続するには：

*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*

今、中央のノードから最上位のノードに移動するには、3ホップが必要です。ただし、下に移動するには1ホップしかかかりません。

ゲームボードの設定をグラフに変換するのは簡単です。各「交差点」ノードです。 2つの交差点間のパスはエッジであり、そのパスの長さはそのエッジの重みです。

A *を入力します。グラフを作成する（隣接行列またはノードのリストを使用する）ことにより、A *アルゴリズムを使用して最短経路を見つけることができます。他のアルゴリズムにはダイクストラが含まれます。そして他にもたくさん！ただし、最初にグラフの観点から問題を整理し、次にノードA（pacman）からノードB（ghost）に移行する方法を試す必要があります。

役立つことを願っています！

非常に長い時間が経ちましたが、記憶から、パックマンの幽霊は経路探索の方法であまり何もしませんでした。彼らは、「斑点を付ける」までかなり標準的なランダム化された迷路探索を行います。廊下の軸に沿って障害物のない経路を見つけて、あなたが視線から消えるまであなたに向かって直接移動し、ランダムなパターンを再開します。より高いレベルでは、パックマンは幽霊が「臭い」をするという目に見えない道をしばらく彼の後ろに残すでしょう。そして時々続く。

パックマンがパワーアップしたとき、アルゴリズムの唯一の違いは、彼らがあなたを見つけたとき、幽霊があなたの方に移動する代わりにあなたから逃げるということです。

したがって、本格的な体験のためには、おそらく非常に高度な経路探索アルゴリズムはまったく必要ありません。もちろん、空想になりたい場合は、A *を実装できます。

敵に向かって直接歩くことは出発点ですが、迷路を追加するときは、幽霊が曲がりくねったり行き止まりで立ち往生したりしないように、少しスマートな経路探索を追加する必要があります。

次のチュートリアルは、A *の使用を開始するための優れた軽量ガイドであり、ダウンロード可能な例があります。

タイルベースのマップでのパス検索

パックマンでは、すべてのゴーストに異なる追跡アルゴリズムがありました

  • 点滅-＆gt;チェイス。通常は最短のルートであなたに近づきます。
  • ピンキー-＆gt;待ち伏せ。パックマンにもっと回り道をする傾向があります。致命的。 （ピンキーと瞬きは、方向を選択するときに異なる選択をする傾向があり、多くの場合、コーナーのプレーヤーをケージします）
  • 真っ黒-＆gt;フリーク。この男は奇妙に動作します。彼はボード上をかなりランダムに動きますが、近づいてくると時々追いかけます。
  • クライド-＆gt;馬鹿。ランダムに移動します。それほど脅威ではありません。

幽霊の動きには興味深いパターンがプログラムされています：時折、パックマンの追跡をやめ、同時に迷路のそれぞれのコーナーに戻り、「散乱モード」に入ります。

the pacman dossier にアルゴの詳細な説明があります

よろしく

ギヨーム

A *（星）を見て開始することができます

およびこちらのページには、他のパス検索アルゴリズムへのリンクがあります。

>

[edit] gah ...脳が遅すぎる...この本を忘れてしまった、それはCかC ++（どちらかは忘れる）だが、Javaの概念はまだ得られる。読むのが最も簡単ではないかもしれませんが、全体的に悪いことではありません。 ゲーム開発者向けのAI、デビッドM.ブール、グレンゼーマン。

pacmanが行うすべての動きで最短経路アルゴリズムを使用すると思います。非常に適切な実装は、 Dijkstraのアルゴリズムです。

要約すると：迷路を、頂点とエッジを持つグラフとして視覚化します。各エッジには待機があります（あなたの場合、すべてのエッジのウェイトは同じです）。アルゴリズムは、直接到達可能な各エッジを1ステップ下に移動することにより、ソース頂点からターゲット頂点までの最短経路を見つけます。次に、次の頂点で同じことを行い、ターゲットに到達するまで続けます。最初に到達したパスが最短パスです。このアルゴリズムに対して多くの最適化を行うと、パックマンが以前の位置にあった場所や移動した方向を考慮して、アルゴリズムの経験則を得ることができます。すべての動きで各ゴーストからパックマンまでの最短経路を見つけて、その方向にゴーストを移動することをお勧めします。最終的には距離が短くなり、パックマンを捕まえることができます。

パックマンから到達可能な直接のエッジをすべて見つけ、これらの頂点のできるだけ多くをゴーストでカバーしようとするために使用できる別のヒューリスティック。したがって、pacmanをターゲットの頂点として設定する代わりに、pacmanがすぐに到達できる頂点をターゲットとして設定します。その結果、利用可能なゴーストはpacmanの主要なエスケープルートを隠蔽し、捕まえようとします。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top