9


1

私は単純な2次元グリッドベースのシムゲームを開発中で、完全に機能的なパス検索があります。

A *パス検索を実装するための基礎として、私は前の質問で見つけた答えを使用しました。 ( Pathfinding 2D Javaゲーム?)。

私が求めていることを本当にあなたに見せるために、私はあなたが私が作ったこのビデオスクリーンキャプチャをあなたに見せる必要があります。 私はただ、その人がどのようにしてある場所に移動したり戻ったりするのかを確認するためのテストをしていましたが、これが結果です…​

方向によって道の選択が異なる、予想外の結果。 何か案は?

9 回答


3


あなたが単純なような解決策を探しているなら、私は少しランダム化を提案することができますか?

つまり、cokeandcodeのコード例では、「後継者状態」を生成する(AIという用語を使用するための)入れ子になったforループがあります。 私はそれが「現在の」状態を囲む3x3の四角形をループしている点を参照して、考慮すべき新しい場所を山に追加します。

比較的簡単な修正方法は、そのコードを少し分離して、残りの処理ステップの前にノードのリンクリストを生成するようにすることです。 その後、Containers.Shuffle(またはGenerics.Shuffleですか?)そのリンクリストをクリックし、そこで処理を続行します。 基本的に、LinkedList = \ {(node.x-1、node.y)、(node.x、node.y-1)を返す "createNaiveNeighbors(node)"というルーチンを使用します。 (pidgin Javaをご容赦ください。私は簡潔にしようとしています(そして常に失敗します)。

ただし、リンクリストを作成した後は、リンクリストの代わりに "for(Node n:myNewLinkedList)"を実行することができます。

for(int x = -1; x <2; x){

for(int y = -1; y <2; y){

それでも、まったく同じボディコードを使用してください。

これが行うことは、理想的には、考慮されるノードの順序を「揺さぶる」ようなもので、ヒューリスティックを変更することなく対角線に近いパスを作成することです。 パスは依然として最も効率的ですが、通常は対角線に近くなります。

欠点は、もちろん、AからBに何度も行った場合、別の道が取られる可能性があることです。 それが受け入れられない場合は、もっと抜本的な修正を検討する必要があります。

お役に立てれば! - アゴール


2


両方のパスは同じ長さなので、アルゴリズムはその仕事をしています - 最短パスを見つけています。 しかし、A *アルゴリズムでは、WHICHの最短パスは指定されていません。 実装は通常「最初の」最短経路をたどります。 自分のことを見なくてもその理由を正確に知ることは不可能ですが、毎回同じ結果を得たい場合は何らかの優先順位の規則を追加する必要があります(目的のパスが検索の最初に来るように)。


2


その理由は、あなたがアルゴリズムを実行したいパスです。 A *が使っているヒューリスティックはわかりませんが、最初の場合は最初にトンネルの終わりまで進み、次にトンネルの終わりからターゲットまでの道のりを計画する必要があります。

2番目のケースでは、最も単純なターゲットへの移動が壁にぶつかるまで下降してから、壁からターゲットへの道を計画します。

ほとんどA *ブロックワールドの場合、ヒューリスティックな見通し線または Manhattan Distanceで作業することを私は知っています。 このヒューリスティックは最短の方法を提供しますが、障害物がある場合は、見通し線とは異なる方法で移動することを余儀なくされます。 アルゴリズムは可能な限り長く見通し線上に進みます。


2


その理由は、実際には非常に単純です。パスは、欲張りな方法で検索するため、常に可能な限り低いヒューリスティックを得ようとします。 目標に近づくことが最適な方法です。

あなたが斜めの動きを許したならば、これは起こらないでしょう。


1


最も可能性の高い答えは、真っ直ぐ南に進むと最初に目標に近づくことです。逆に言えば、これは選択ではないので、サブパスを区分的に最適化します。その結果、上下に交互に移動するのが最良と見なされます。

対角線に沿って戻るようにしたい場合は、パスに沿っていくつかの関心点(たとえばトンネルの入り口)を特定し、それらをヒューリスティックで考慮する必要があります。 あるいは、関心点を通過するサブパスを再計算することで、それらをアルゴリズムで考慮に入れることもできます。

当時、彼らは地図の事前に編集された静的分析を行っていて、経路探索マーカーをチョークポイントに置いていました。 あなたの最終目標が何であるかに応じて、それはここでも良い考えかもしれません。

何が起こっているのかを知りたいのであれば、A *検索のステップをレンダリングすることをお勧めします。 あなたの質問を考えると、それはあなたにとって非常に目を見張るものかもしれません。


1


いずれの場合も、目標ノードに早く到達するパスを優先します。これがA *の目的です。


0


私が右を見た場合、球は目標に向かって直接得ることができないので(経路はブロックされている)、直線で最初に右に動いています。 それから目標に向かって直線的に進みます。 斜めに見えるだけです。


0


あなたの検索は最初に「下」の方向に見えますか? これはアルゴリズムを説明するかもしれません。 最初に「見上げる」ように変更してみてください。そうすれば、反対の動作になるでしょう。


0


あなたのastarの実装次第で、あなたは同じヒューリスティックで異なる結果を見るでしょう、多くの人々が言及したように。 これは、2つ以上のパスがオープンセットの順序を結ぶときに、最終パスの外観が決まるためです。 許容可能なヒューリスティックがある場合は、常に最適なパスを取得できますが、アクセスするノードは、持つネクタイの数とともに増えます(ヒューリスティックが生成するネクタイの数と比べて)

あなたがより多くのノードを訪れることが問題であるとは思わないならば、私はランダム化(これはあなたの現在受け入れられている答えです)提案を使うことを提案するでしょう。 より多くのノードを検索することが問題であり、最適化したいと思う場合は、ある種のタイブレーカーを使用することをお勧めします。 マンハッタン距離を使用しているように見えます。2つのノードがタイブレーカーとして結ぶときにユークリッド距離を使用すると、ゴールへの直線パスが増え、アクセスするノードが少なくなります。 これはもちろん、ゴールへの罠や視線のブロックが与えられていないからです。

視線経路上にブロッキング要素を有するノードを訪問することを回避するために、これらのブロッキング要素を考慮に入れる発見的方法を見つけることを提案する。 もちろん、新しいヒューリスティックは通常のスターサーチよりも多くの作業を行うべきではありません。

私は 私の質問を見ることをお勧めします。それはこの問題に対するいくつかのアイデアと解決策を生み出すかもしれないからです。