2dグリッドベースPathfinding：ロケーションが到達可能かどうかを調べるための最も安い方法/アルゴリズム

Question

私の主な経路探索は、aStarアルゴリズムの実装によって行われます。利用可能なパスがある限り、パフォーマンスは素晴らしいです。

しかし、存在しない場合は、パスがないという結論に達するまで、使用可能なすべてのノードが解析されます。

私が考えることができる最悪のシナリオは、それを取り囲むターゲットの場所に比較的近い障害物です。

全体的なパフォーマンス向上させることが、私は今のところ出ているいくつかのアイデア：

• 検索をし、それはそれであれば、ターゲットは、到達可能であるかどうかを確認するためにのみ実行されalgorithmn安い経路探索を実行し、 aStarを実行して実際のパスを取得します。

• ターゲットノードの周囲にあるすべての対処不能なノードを特定の半径に集め、それらがすべてリンクされているかどうかを確認します。そうであれば、ターゲットは到達不可能であり、到達できません。 ノードを収集するaStarsの方法は本質的にこれを行うので、startノードのための等価物を実行する必要はありません。

それでは、私はここのために求めていることは、私は私のリストに追加することができ、いくつかのbulletpoints /アイデアを持っているそこに誰かがあるかどうかである、または私が利用できる安価な経路探索アルゴリズムの方向に私を指しますパスがあるかどうかを確認する

Answer 1

最初のアイデアは、洗練されている必要があります！

あなたのヒューリスティックのために、A *はターゲットの周りに多くの時間を費やすので、 の周りに「訪問した」壁を作成します。

ターゲットが含まれている閉じた連続したパスが見つかった場合は、訪問先の「壁」を確認できますが、ソースではないので、さらに検索する必要はありません。

第二アイデア、完全ではないが、おそらく、「LOST」の時間を短縮
使用双方向A *、ソースが先に実行されているが、同じ時間先に、それはソースへの道だ見つけます。

https://qiao.github.io/PathFinding.js/visual/を見て、どのように振る舞うか考えてください。