BFSアルゴリズムは、ソースからターゲットまでの最短経路をどのように教えていますか？

私はBFSアルゴリズムとその実装方法を知っていますが、誰かが2点間の最短経路を見つけるためにどのように使われているか教えてくれるでしょう...私は特にパックマンゲームボードを求めています。幽霊はBFSを使ってターゲット（パクマン）にどのように到達しますか？BFSアルゴリズムは、ソースからターゲットまでの最短経路をどのように教えていますか？

出典

2016-05-02 Azhar Sindhi

PacManの幽霊はBFSを使うと思いますか？ –

PACMANへの最短経路を検索するためにBFSを使用する必要があると言われます –

http://www.redblobgames.com/pathfinding/tower-defense/これは動作の概念化に役立ちます – vu1p3n0x

Pacmanマップを接続ノードのグラフに変換できます。マップの各セルをグラフのノードに変換します。あるセルから別のセルに直接接続できる場合（つまり、隣接している場合）、それらを接続します。

ゴーストが廊下にある場合、彼は隣接する2つのセルに行くことができます。したがって、現在のセルはグラフ内に2つの隣接ノードを有する。彼が交差点にいる場合は、行く道がさらにあります。そして、すべての細胞についても同様です。

ゴーストは、ゴーストが現在あるセルに根ざしたツリーであるかのようにグラフを検索します。

BFSは、左から右に検索するには、この写真で判明した場合、それは「15」に多くのノードを下に見つけるかもしれないが、それは、その後見つけることに注意してください「2」と最短経路を持つ。
'14'が別の接続を持っていて、 '1'経由で '2'になっても問題ありません。はが既に見つかったパスより長いため、 14 'は既に長い）。

現在のツリーでどのパスを使用したかを覚えておく必要があります（次のゴースト位置が異なるため、「現在」です）。 DFSでは、とにかくスタックを使用します。ここではBFSを使用するので、グラフの各ノードに空の余分なフィールドがあるようにすることができます。 BFSを実行すると、ノードの先行ノードがそのフィールドに格納されます。例：5の余分なフィールドに '6'を格納します。ゴール「2」を見つけたら、あなたはその鎖を歩きます：2-> 3-> 4-> 5-> 6、それを逆転します！

出典

2016-05-02 18:10:35

OK、次に移動する方法彼らのパスの幽霊はBFSを使用していますか？ –

例えばゴーストが廊下にあり、Pacmanがその隣にある場合、ゴーストはあたかもツリーのルートであるかのように現在のノードから始まります。この場合、根には2人の子供がいます。 2人の子供のうちの1人がPacmanによって占有されています。幽霊はパックマンを見つけました。 –

@AzharSindhi検索したノードを追跡し、見つかった場所からバックトラックするために使用することができます – vu1p3n0x

これはありません。 BFSは、単にグラフやツリーを検索する方法です。

2点間の最短経路を計算するには、それを行うアルゴリズムが必要です。 Dijkstrasアルゴリズムは、優先度キューを使用して実装するのが簡単です。 DijkstrasアルゴリズムはBFS（優先度キュー対キュー）の特殊なケースであると主張することができます。

我々は、我々は、私はBFSの深さが十分でない理由として、画像を作成するために管理GIMPで4分よりも多くを使用してパックマン

への最短経路を探索するためにBFSを使用しなければならないことを告げています最短経路を決定する。

レッドGは幽霊です。イエローPは私たちのヒーローです。青い点は、幽霊がどのような経路をとるべきかについての決定との交差点です。緑の線は最短経路です。ピンク？ lineはBFSが最初に見つけたパスです。

編集：私は道のために悪い選択をしたことを知った、彼らは3つのレベル離れている。私はちょうど実際の分岐ではなく、点をトレースしました。私はGとPのより適切なプレースメントがあると確信しています。これは、BFS - 最短経路の不一致をより明確に示しています。

質問のタイトルが間違っている可能性があります。BFSは、幽霊がPac-Manを見つけるのに合理的な方法ですが、最短経路ではありません。

編集：コメントに応じて。これは、Pac-Manボードが加重グラフとして表されているかどうかという質問に答えるものです。

|-----A-----|X|------B-----| 
|XXXXX|XXXXX|X|XXXXXX|XXXXX| 
oXXXXX3XXXXX|X|XXXXXX|XXXXXo 
|XXXXX|XXXXX|X|XXXXXX|XXXXX| 
C-----D-----E-F------G-----H

またはネイバー表現として

AD 4 
CD 6 etc..

ような何かものは、全ての画素である場合BFSはに減少し、ほとんどのパス非常に洗練されていないやり方でを試してみてください。

私はhttp://trelford.com/blog/image.axd?picture=maze_thumb.pngからgoogle経由でパックマンのバックグラウンドを盗んだ。

ゴーストの動きの実際の実装については、深さ分析におけるhttp://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior

出典

2016-05-02 18:14:58

BFSとDijkstraは問題ありません。 A-starは、廊下の狭い迷路では意味をなさない。しかし、これは多くの人が間違っているのであなたが良い会社になっているのです;-) –

@BerndElkemann確かにパックマングリッドのA *は役に立たないです。 –

ああ、あなたの答えはPacmanをターゲットにしていなかったが、もっと一般的だと思う。はい良い点：他のゲームのためにA-starはしばしば私たちができる最良のものです。 –

に利用可能であるBFSは、別の答えが言及ものとは対照的に、を正しく重み付けされていないグラフ内のノード間の最短経路を見つけるない 。重み付けされていないグラフでは、パスの長さは単にソースからデスティネーションまでのエッジの数です。

パクマンボードは、重み付けされていないグラフと考えることができます。ボードの各四角形（壁ではない）はノードであり、直接隣接するエッジがあります。

ゴーストがPacManへの最短経路を検索すると、ゴーストは座っている正方形からこのグラフ上でBFS検索を開始します。検索でPacManが見つかると、最短経路を見つけるために自分の道を戻すことができます。私たちは一連の動き（例えば、北→西→南...）を取得し、幽霊はこのパスに沿ってパクマンの現在の場所に移動する必要があります。

しかし、pacmanもゴーストと同時に動いている場合は、移動ごとにBFSを再実行して、新しい位置への最短経路を見つける必要があります。

出典

2016-05-02 19:15:02

答えを教えていただけますか？私たちは道を逆戻りさせることによって、どのように一連の動き（北→西→南...）を得るのだろうか？ –

BFSアルゴリズムは、ソースからターゲットまでの最短経路をどのように教えていますか？

答えて

関連する問題