4

私は現在、SDL を使用して C++ で小さなグリッド ベースのゲームを構築しています。マップ上の個々のタイルを表すタイル クラスを作成しました。このタイル クラスは 2 次元ベクトルで使用されます。一方の次元は X 軸を表し、もう一方の次元は Y 軸を表します。

アルゴリズムに問題があります。どこから始めればよいかさえわかりません。たとえば、次のマップがあるとします。

0 0 1 1 0 E
0 0 0 1 0 1
0 C 0 1 0 1
0 1 0 1 0 1
0 1 1 1 1 1

C は私のキャラクター、E は出口、1 は床タイルです。

キャラクターが出口にたどり着く方法があるかどうかを判断するための最適な方法を見つけたいと思います。関数を使用して、C の周りのすべてのタイルを手動でチェックできることはわかっています。C の周りのすべてのフロア タイルについて、E に到達するための一貫したパスが見つかるまで、すべてのタイルをもう一度チェックしますが、それはあまり最適ではないようです。

自分を向ける手がかりや何らかの方向性を知ることができますか?

4

4 に答える 4

7

2 点間のパスを見つけることができる非常に多くのアルゴリズムがあります。実装と理解が容易な 3 つのアルゴリズムがあります。

  1. 深さ優先検索 (DFS)
  2. 幅優先探索 (BFS)
  3. ダイクストラのアルゴリズム

深さ優先検索

このアルゴリズムは、現在のノードを取得し、すべての隣接ノードを見つけてスタックに入れ、1 つポップして最後までトラバースするか、パスを見つけます。

幅優先探索

このアルゴリズムは、現在のノードを取得し、すべての近隣ノードを見つけてキューに入れ、1 つずつキューから取り出し、最後までトラバースするか、パスを見つけます。

DFS と BFS の違いは、DFS は最適解を保証できないことです。この場合を考えてみましょう。

S 1 1
1 1 1
1 1 E

S が (0,0) で、E が (2, 2) であると仮定します。この迷路には多くの最適解があります。DFS はそのネイバーのパスを最後までチェックするため、S -> (1,0) -> (2,0) -> (2,1) -> (1,1) -> (1,2) -> Eかかる場合があり、パスのコストとして 6 を返します。一方、BFS はすべての隣人、すべての隣人の隣人を見つけて続行します。ネイバーの 1 つが E の場合、コストを返します。それは最適であることが保証されます。したがって、BFS は次のようになります。S -> (1,0) -> (2,0) -> (2,1) -> E（隣人の隣人を見つけます。隣人のそれぞれで最後まで行きません）。

ダイクストラのアルゴリズム

BFS に似ていますが、重みを持つことができます。この例では、あるノードから別のノードに移動するコストが 1 ユニットかかると仮定しました。ダイクストラのアルゴリズムでは、任意の正の整数をコストとして使用でき、リンクごとに異なる場合があります。

結論

最適な結果が必要な場合は、BFS またはダイクストラのアルゴリズムを使用してください。あなたの場合、BFSは機能するはずです。

于 2013-10-05T03:09:55.677 に答える
5

最も使用されているパス検索アルゴリズムを見てみましょう。

http://qiao.github.io/PathFinding.js/visual/

これは JS で行われますが、ニーズに合った C++ 実装を見つけるか、独自のものを作成できるはずです。

于 2013-10-05T02:49:43.340 に答える