私は単純な2Dグリッドベースのシミュレーションゲームを開発中であり、完全に機能するパスファインディングを持っています。
前の質問で見つかった回答を、A*パスファインディングを実装するための基礎として使用しました。（パスファインディング2D Javaゲーム？）。
私が本当に求めていることをあなたに示すために、私が作ったこのビデオスクリーンキャプチャをあなたに示す必要があります。私はちょうどその人がどのように場所に移動して戻ってくるかをテストしていました、そしてこれは結果でした...
http://www.screenjelly.com/watch/Bd7d7pObyFo
方向によってパスの選択が異なり、予期しない結果になります。何か案は？
両方のパスが同じ長さであるため、アルゴリズムはその仕事をうまく行っています-最短パスを見つけています。ただし、A *アルゴリズムは、どの最短パスを取るかを指定しません。実装は通常、「最初の」最短経路を取ります。あなたのものを見ずに、正確に理由を知ることは不可能ですが、毎回同じ結果が必要な場合は、何らかの優先ルールを追加する必要があります（そのため、検索で最初に目的のパスが表示されます）。
その理由は、アルゴリズムが進むパスです。
あなたのA*が使用するヒューリスティックはわかりませんが、最初のケースでは、最初にトンネルの終わりに行き、次にトンネルの終わりからターゲットまでの道を計画する必要があります。
2番目のケースでは、ターゲットへの最も単純な移動は、壁にぶつかるまで下降し、壁からターゲットへの道を計画します。
ほとんどのA*は、ブロックワールドの場合、視線ヒューリスティックまたはマンハッタン距離での作業を知っています。このヒューリスティックは最短の道を提供しますが、視線とは異なる道を強制的に進む障害物の場合、道は出発点によって異なります。
アルゴリズムは可能な限り視線を移動します。
その理由は実に単純です。貪欲な方法で検索するため、パスは常に可能な限り最小のヒューリスティックを使用しようとします。ゴールに近づくことが最適な道です。
斜めの動きを許可すれば、これは起こりません。
最も可能性の高い答えは、まっすぐ南に行くと最初に目標に最も近づくというものです。逆に、これは選択ではないため、サブパスを部分的に最適化し、その結果、上/横の動きを交互に行うことが最善と見なされます。
斜めに戻るようにしたい場合は、パスに沿っていくつかの関心のあるポイント (トンネルの入り口など) を特定し、ヒューリスティックでそれらを考慮に入れる必要があります。または、関心のあるポイントを通過するサブパスを再計算することにより、アルゴリズムでそれらを考慮することができます。
昔は、事前にコンパイルされたマップの静的分析を行い、チョークポイントにパスファインディング マーカーを配置していました。最終的なターゲットが何であるかにもよりますが、ここでも良い考えかもしれません。
何が起こっているのかを知りたい場合は、A* 検索の手順をレンダリングすることをお勧めします。あなたの質問を考えると、それはあなたにとって非常に目を見張るものかもしれません。
私が右を見た場合、球はゴールに直接到達できないため（パスがブロックされているため）、最初に直線で右に移動しています。その後、ゴールに向かって直線的に進みます。斜めに見えるだけです。
多くの人が言及しているように、astar の実装に応じて、同じヒューリスティックで異なる結果が表示されます。これは同点のためです。2 つ以上のパスが結合している場合、オープン セットの順序によって、最終的なパスの外観が決まります。許容できるヒューリスティックがある場合は常に最適なパスが得られますが、訪問するノードは、(それほど多くのタイを生成しないヒューリスティックと比較して) 持っているタイの数に応じて増加します。
より多くのノードにアクセスすることが問題であると思わない場合は、ランダム化（現在受け入れられている回答）の提案を使用することをお勧めします。より多くのノードを検索することが問題であり、最適化したい場合は、ある種のタイブレーカーを使用することをお勧めします。マンハッタン距離を使用しているようです.2つのノードがタイブレーカーとして結ばれているときにユークリッド距離を使用すると、ゴールへのより多くの直線的なパスが得られ、アクセスするノードが少なくなります. これにはもちろん、トラップやゴールへの視線のブロックはありません。
視線パスにブロック要素があるノードにアクセスしないようにするには、これらのブロック要素を考慮したヒューリスティックを見つけることをお勧めします。もちろん、新しいヒューリスティックは、通常のスター検索よりも多くの作業を行うべきではありません。
この問題に対するいくつかのアイデアと解決策が得られる可能性があるため、私の質問を見ることをお勧めします。
あなたの検索は最初に「下」方向に見えますか? これはアルゴリズムを説明するかもしれません。最初に「上」を参照するように変更してみてください。逆の動作が見られると思います。