問題タブ [path-finding]

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

すべてのゴーストは、画面のランダムな領域で起動し、パックマン キャラクターに向かって進まなければなりません。プレイヤーがパックマンを操作して動かしている間、プレイヤーはパックマンに従い、可能な限りパックマンに近づく必要があります。

迷路/障害物は (まだ) ないため、マップ全体 (400x400 ピクセル) はオープン グラウンドです。

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

そのため、それぞれが異なる重みを持つ複数のターゲット エンドポイントへの最短ルートを事前に計算する単純なパスファインディング アルゴリズムがあります。これは、エッジの重みが異なりますが、1 つのエンドポイントと各エンドポイントの間にノードを持つことと多少同じです。使用するアルゴリズムは単純な拡散アルゴリズムで、1 次元では次のようになります (| は壁を意味し、- は空間を意味します)。

• 5 - - - 3 | - - - 2 - - - - 2
• 5 4 - - 3 | - - - 2 - - - - 2 : Handled distance 5 nodes
• 5 4 3 - 3 | - - - 2 - - - - 2 : Handled distance 4 nodes
• 5 4 3 2 3 | - - - 2 - - - - 2 : Handled distance 3 nodes
• 5 4 3 2 3 | - - 1 2 1 - - 1 2 : Handled distance 2 nodes
• Done. Any remaining rooms are unreachable.

したがって、次のような事前計算されたパスファインディング ソリューションがあるとします。5 のみがターゲットです。

- - - - | 5 4 3 2 1 -

壁を部屋に変えたら。再計算は簡単です。すべての距離ノードを再処理するだけです (ただし、既に存在するノードは無視します)。ただし、4が壁になった場合の効率的な処理方法がわかりません。明らかに結果は次のとおりです。

- - - - | 5 | - - - -

ただし、2d ソリューションでは、4 を効率的に処理する方法がわかりません。4 が 5 に依存しているため、再計算が必要であることを簡単に保存できますが、新しい依存関係と値を安全に判断するにはどうすればよいですか? 配列全体を再計算するのは避けたいと思います。

何もないよりはましな解決策の 1 つは、(大まかに) 5 から 5 のマンハッタン距離を持つ配列要素のみを再計算し、ソース情報を維持することです。これは基本的に、選択した領域にアルゴリズムを再適用することを意味します。

私は現在、Theme Hospitalのアイデアに基づいた非常に基本的な Java ゲームを作成しています。

私は Java の初心者で、現在大学で 1 年間勉強しています。私は 2 年近く Java を使ってきましたが、ようやくまともなプロジェクトに時間を割くことができました。

入院する人（患者）を作らないといけない段階です。彼らは受付に行き、次にGPのオフィスに行き、その後元の位置に戻る必要があります。

A* パス検索を調べましたが、非常に複雑に思えます。仕組みは理解できたと思いますが、ゲームに実装する方法がわかりません。

これまでのところ、ユーザーは受付デスクを配置し、GP のオフィスを構築できます。これらのそれぞれには、患者が到達しなければならない場所となる「使用ポイント」があります。グリッドの四角形は満タンかどうかのみで、異なる地形はありません。

過去数か月で GUI に関する多くの新しいテクニックを学んだので、面倒なので、まだコードを貼り付けることをためらっています。私の計画は、マイルストーン 1 に到達し、患者をデスクに移動させ、次にオフィスに移動させ、退院させることです。これができたら、コードをさらに整理します。

私は A* と多くの異なる型の多くの実装を見てきました。一緒に作業できる出発点を誰か教えてもらえますか? 既に作成された一連のクラスを適応させる必要がありますか?それとも、独自のクラスを最初から作成する必要がありますか?

現在、Javaでのパス検索に関する別の質問があります。しかし、これは別の質問だと思います。

ゲームを作っています。経路探索では、複数のエンド ポイントを処理できる必要があります。私が見つけたすべてのパス検索アルゴリズムとチュートリアルには、1 つのエンドポイントしかありません。

この変更は、既存のコードに簡単に変更できるのでしょうか?それとも、自分でゼロから作成するほうがよいでしょうか?

いくつかのタイルが壁で、他のタイルが歩きやすいタイルベースのマップがあります。歩きやすいタイルは、経路計画で使用したいグラフを構成します。私の質問は、グラフ内のすべてのノードを訪問し、繰り返しの訪問を最小限に抑えるパスを見つけるための優れたアルゴリズムはありますか?

例えば：

地図の例 http://img220.imageshack.us/img220/3488/mapq.png

一番下の黄色のタイルが開始点である場合、繰り返しが最も少ないすべてのタイルにアクセスするための最適なパスは次のとおりです。

パスの例 http://img222.imageshack.us/img222/7773/mapd.png

このパスには 2 回の再訪があります。悪い道は、最初のジャンクションで左折し、すでに訪れた 3 つのタイルを引き返すことです。

終了ノードは気にしませんが、開始ノードは重要です。

ありがとう。

編集：

質問に写真を追加しましたが、表示時にそれらを見ることができません。どうぞ：

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

さらに、グラフでは最小繰り返し数 = 0 という状況は決してないため、これが必要です。つまり、マップ内のすべてのタイルを踏むには、プレイヤーは自分のパスを少なくとも 1 回横断する必要があります。

私は（ごくわずかな）自由な時間にローグライクゲームに取り組んでいます。各レベルは基本的に、パスで接続されたいくつかの長方形の部屋になります。でも、部屋の間の小道は自然に見えて風が強いようにしたいと思います。たとえば、私は次の自然な見た目を考慮しません。

私は本当にこのようなものが欲しいです：

これらのパスは、いくつかのプロパティを満たす必要があります。

1. 私はそれらが境界を定められている領域を指定できなければなりません、
2. 私は彼らがどれほど風が強くて長いかをパラメータ化できなければなりません、
3. 線は、一方のパスで開始し、もう一方のパスで終了したように見えるべきではありません。たとえば、上記の最初の例は、Aで始まり、Bで終わるように見えます。これは、基本的に、Bと並ぶまで方向を繰り返し変えてから、そこにまっすぐ進むためです。

A *を使用したいと思っていましたが、正直なところ、ヒューリスティックがどうなるかわかりません。遺伝的アルゴリズムの使用も検討しましたが、その方法がどれほど実用的かはわかりません。

私の質問は、私が望む結果を得るための良い方法は何ですか？「A*」や「ダイクストラのアルゴリズム」のような方法を指定するだけでなく、優れたヒューリスティックの支援も必要です。

パス検索に A-star (A*) を使用するゲームに取り組んでいますが、1 つのグリッド スクエアよりも大きなオブジェクトがいくつかあるところまで来ました。

16*16px のグリッドで実行しています。壁のセグメントは 16*16 であるため、1 つの正方形は通行できません。私の悪役の何人かは 32*32 で、隙間を通り抜けるには少なくとも 2 グリッドの正方形の隙間があることを確認する必要があります。

デザインには薄い壁 (16 ピクセル) が必要であり、16*16 の正方形を 1 つしか占有しない小さな悪者がいくつかあるため、単純にグリッドを 32*32 にすることはできません。

このマルチ解像度環境を実装するにはどうすればよいですか? A-star は今でも使用する正しいツールですか?

AS3 に A* アルゴリズムを実装しましたが、1 つのことを除いてうまく機能します。多くの場合、結果のパスは、ターゲットへの最も「自然な」またはスムーズなルートをたどりません。私の環境では、オブジェクトは、水平または垂直に移動できるのと同じくらい安価に斜めに移動できます。これは非常に簡単な例です。開始点は S でマークされ、終了 (または終了) 点は F でマークされます。

ご覧のとおり、最初の検索ラウンドでは、ノード [0,2]、[1,2]、[2,2] がすべて N のスコアを持つため、可能なノードのリストにすべて追加されます。私が抱えている問題は、続行するノードを決定しようとしている次の時点で発生します。上記の例では、次のノードを選択するために possibleNodes[0] を使用しています。これを possibleNodes[possibleNodes.length-1] に変更すると、次のパスが得られます。

そして、 possibleNextNodes[Math.round(possibleNextNodes.length / 2)-1] で

これらのパスはすべて同じ数のステップを含むため、コストは同じですが、この状況では、最も賢明なパスは次のようになります...

数学的に正しいだけでなく、パスをより賢明に見せるための正式に受け入れられた方法はありますか?

私は、インテリジェントなパスファインディングを行うのではなく、障害物をスライドして、クリーチャーオブジェクトが環境内の他の任意のオブジェクトに向かって移動できるようにするシミュレーションを書いています。経路を計画させようとしているわけではありません。一般的な 1 つの方向に移動し、障害物を回避するだけです。

これは 2D 環境 (俯瞰) であり、すべてのオブジェクトには衝突検出用の境界四角形があります。グリッドはありません。私は A* ソリューションを探していません。

この種の「ばかげた」衝突ベースのパスファインディングに関するチュートリアルを見つけることができなかったので、最も一般的な用語を使用してこれを説明していない可能性があります。

これを実装する方法に関する推奨事項 (またはチュートリアルへのリンク) はありますか?