問題タブ [path-finding]

2D グリッドがあるとしましょう。パスファインディングは、私の問題の二次的なステップです。

私のことは、グリッドの真ん中にユニットがあるとしましょう。ユーザーに「これらはすべて利用可能な宛先です。」と伝えたい。

ユニットが歩けるマスの数に基づいて、ユーザーに「到達できるマスはこれだけです」と表示したいと思います。次に、ユーザーが選択した目的地をパス検索します。

到達可能な目的地を表示するために最初の検索を行う最良の方法は何ですか?

地形には、地形に応じてボーナスの制限もある場合があります。

これが何と呼ばれているのかわからないので、どこを見ればいいのか、何をググるべきなのかを教えていただければ幸いです。

乾杯！:)

/E

私はOpenGLに本当に慣れていませんが、基本的な三角法をかなりよく理解しています（学校からかなり忘れられています！）が、これに問題があります。

Z軸を前後に移動するキャラクターがいます。ストレイフではなく、左右に動かすには、回転させて（それぞれ左矢印キーと右矢印キーを押したとき）、もう一度前後に押すと、向いている方向に動きます。

だから私がしたのは、左/右の関数に、キャラクターの回転を描くために使用される角度変数に少量を加算/減算させることでした。次に、順方向/逆方向関数は、x軸とz軸の変数に少量を加算/減算します。それらは次のとおりです（後方の場合）：

見出し変数は、左右の矢印キーで操作される角度です。

プレイヤーがまっすぐ進むとき、見出しは0であるため、cos（0）= 1およびsin（0）= 0であるため、これは機能すると思いました。つまり、Xではどこにも移動せず、Zでは0.005の全量を転送します。私の基本的な三角法の知識は完全には正しくなかったと思います。少し回してから前方に移動するとその方向に移動しますが、もう少し移動してから前方に移動すると、90度回転すると同じ線に沿って移動し、続行します。その後、180度、270度などのようになります。

編集：私はそれをよりよく説明しようとします、基本的に私が左に曲がった後に前方に押すとそれは私が望む方向に進みます、しかし私が前方に手を離すと、もう少し回してからもう一度前方に押すと角度が本来あるべき方向に増加しましたが、方向は本来あるべき方向から約90度です。申し訳ありませんが、これをうまく説明することはできません。

編集：さて、私は奇妙な「90度」の問題を引き起こしていると思われるいくつかの奇妙な問題を抱えています。キャラクターを90度（ハードコーディングされた見出し= 90）で左/右に見えるようにすると、cos（見出し）0である必要がありますか？しかし、何らかの理由で-0.44として出力され、cos-1（-0.44）で116.1が得られた場合、それはラジアンなどの角度が必要なMath.cos（）と関係がありますか？私はここで完全に迷子になっています。

これはこの問題を解決する正しい方法ですか？私は完全に試行錯誤してマイナス記号で立ち往生しています...

どんな返事でもありがたいです、

ありがとう

InfinitiFizz

（また、ハードコードされた0.005fではなく、文字の速度/回転値にdeltaTimeを使用する必要があることはわかっていますが、ソートする前に、まずこの問題を回避したいと思います）。

多くの A* Start Pathfinding チュートリアルでは、最後の部分は常に次のようになります。

パスを保存します。ターゲット スクエアから逆方向に作業し、開始スクエアに到達するまで、各スクエアからその親スクエアに移動します。それがあなたの道です。

これを A * star Pathfinding に実装するために何をすべきかがよくわかりません。私が使用している現在の方法は次のとおりです。パスを保存し、逆にしてパスファインダーを再度実行しますが、元のパスリストにあるかどうかを確認し、リストにある場合は追加することで、隣接するノードを取得します。

この方法の問題点は、ときどき奇妙なパスが表示されることです。

A* アルゴリズムを考えてみましょう。

Google では、適切な疑似コードを見つけることができます。

よくわからないことが 1 つあります。次のような状況を考えてみてください。

A* はどのようにして a->b->c から a->d... に変更できますか? ??? つまり、A* はノードから開始し、ノード間を移動します。ある時点で、ノードには複数の隣接ノードがあり、A* は隣接ノードによって生成されたパスをたどることができますが、ある時点で切り替えることができます...そして、前のステップから始まるそのステップに戻ることができます放棄された道がその道を横切らなかったとしても...

コードでは、この環境を有効にする条件は何ですか?

PHP でA* アルゴリズムを実装している人はいますか? ウィキペディアに疑似コードと C++ へのリンクがあることは知っていますが、既に PHP で記述されているものを見つけることができないようです。

また、効率的な書かれた A* アルゴリズムも探しています

四分木についていくつか読んだことがありますが、それらを経路探索に利用しようとしています。この目的のために、四分木を使用して接続グラフを作成しようとしています。このグラフでは、各「最小四角形」(子のないノード) が隣接する最小四角形に直接接続されています。説明すると... http://en.wikipedia.org/wiki/File:Point_quadtree.svgの右下の四角形を見ると、その四角形はツリー内の子のないノードであり、直接子のないノードでもある、それを囲む 3 つの四角形に接続されています。

四分木を作成するのは非常に簡単ですが、それとの接続を検出する方法がわかりません。誰かが私に洞察を提供できますか？

前もって感謝します！

私の状況を理解するために少し時間を取ってください。わからない場合はコメントで教えてください。

ウェイポイントのArrayListがあります。これらのウェイポイントは順不同です。ウェイポイントには次のプロパティがあります。
{int type, float z, float y, float x, float rotation}

これは3次元の世界に適用されますが、私のパスファインディングは高さを気にする必要がないため（したがって、世界を2次元の世界として扱う）、y値は無視されます。この質問では、回転は重要ではありません。

• この2次元の世界では、xはx軸を表し、zはy軸を表します。
• xが増加すると、世界のオブジェクトは東に移動します。xが減少すると、世界のオブジェクトは西に移動します。
• zが大きくなると、世界のオブジェクトは北に移動します。zが減少すると、世界のオブジェクトは南に移動します。

したがって、これらの「新しい」ウェイポイントは次のように簡略化できますwaypoint = {float x, float y}。

現在、これらのウェイポイントは、オブジェクトのX軸（x）とY軸（z）の位置を表しています。さらに、現在の場所：curLocation = {float x, float y}とターゲットの場所：がありtarLocation = {float x, float y}ます。

これが私が取得したいものです：次の厳しい条件下でからに
つながるウェイポイント（別名：パスまたはルート）のすべての組み合わせ：curLocationtarLocation

1. 各ウェイポイント間の距離は、より大きくすることはできません(float) maxInbetweenDistance。これには、curLocation最初のウェイポイントからの最初の距離と、最後のウェイポイントからのまでの距離が含まれtarLocationます。そのようなウェイポイントの組み合わせが不可能な場合は、nullを返す必要があります。
2. ターゲットウェイポイントにつながるウェイポイントから複数のウェイポイントが見つかった場合maxInbetweenDistanceは、最も近いウェイポイントを選択する必要があります（少し離れた別のウェイポイントが、より長い距離の新しいパスになり、これも返される場合はさらに良いでしょう） ）。
3. 返されるウェイポイントの組み合わせ（パス）の順序は、最短ルート（最小距離）から最長ルート（最大距離）の順にする必要があります

最後に、次の点を考慮してください。

1. これは私がAI/パスファインディングを賢く行う必要がある唯一のことです。それが私が本格的なパスファインディングまたはAIフレームワークを使用したくない理由です。1つの関数で上記を処理できるはずだと思います。
2. ウェイポイントの可能なすべての組み合わせを返すとオーバーヘッドが大きくなりすぎる場合は、組み合わせの最大数を指定できれば問題ありません（ただし、最も近いものから最も遠いものの順に並べます）。例えば。最も近い5つのパス。

どうすればこれを達成できますか？フィードバックをいただければ幸いです。

ここで最短経路アルゴリズムについて質問しました： 2Dウェイポイントパスファインディング：curLocationからtargetLocationに移動するWPの組み合わせ

（私の状況を理解するために、この質問と同様にその質問を読んでください。）

ダイクストラ最短経路アルゴリズムは、私が必要とすることを実行できるようです。ただし、ルートマップには約500〜1000のノードがあります。

これまでに見た実装では、ノードの数が50未満に制限されていました。私の質問は、ダイクストラ最短経路アルゴリズムを使用する必要があるのか​​、それとも代替手段を使用するのかということです。Javaに実装はありますか？

最短経路アルゴリズム（2Dウェイポイントパスファインディング：curLocationからtargetLocationに移動するWPの組み合わせ）に関する一般的なアドバイスを求めた後、より具体的な実装（500以上のウェイポイント/ノードの最短経路アルゴリズム（例：Dijkstra））について尋ねた後I JUNGライブラリ（http://jung.sf.net/）を使用することを決定しました。

私の目標は、各ポイントがx距離内にあるすべてのポイントに直接接続されているポイントのリスト（サイズ〜1000）からのポイントの任意の組み合わせを使用して、ポイントAからポイントBへの最短経路を取得することです。

このために、ツリーマップを設定する必要があります。これはツリーマップの実装のリストだと思います：http：//jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics。 jung.algorithms.shortestpath

あれは正しいですか？現在、これらの実装はすべてスパースツリーマップに制限されていますが、かなり密度の高いツリーマップを作成する必要があります。

では、目標を達成するためにJUNGでどのツリーマップを使用する必要がありますか？

私は現在 A* パスファインディングに取り組んでいますが、いくつか問題があります。最後まで最善の道をたどる前に、間違った道をたどります。私は何を間違っていますか？

ソースコード: http://basic.apayostudios.com/AStar.zip

オンライン：

Game.cs http://pastie.org/1656955

Node.cs http://pastie.org/1656956

列挙型:

ありがとう！