グリッドに沿って旋回する道順

Question

2dグリッド上の2点間の最短経路を見つける方法を見つけようとしている私の脳をスクラブしてしまった。私はLeeとA *アルゴリズムに関する記事を見たことがありますが、誰も私の最も顕著な質問に答えることができないようです。これらのアルゴリズムはどのように小数点座標で動作するように双曲線化できますか？

見た目はすべてシンプルな整数です。しかし、開始点（3.3,4）と終了点（5,6.6）の最短経路を見つけようとするとどうなりますか？

基本的には、ポイントに小数点が含まれる2つのポイントの間に最短のパスを見つける必要がありますが、それでも数字のグリッドラインに従わなければなりません。対角線上を移動することはできません。グリッドに沿って南北または西にしか移動できませんが、交差点（1,1など）では開始または終了しません。

グリッド線（各四角形）の間の各スペースは市区町村で、グリッド線はあなたが旅行できる道路です。

LeeまたはA *で間違ったツリーを吠えていますか？私はパスファインディングに非常に新しいです。私は完全に独学です。私はアルゴリズムの再発明が私の範囲を超えていることを知っていますが、私の80+のif文を見て、 "これが効率的に経路探索にアプローチする方法ではない"と考えています。 if文を使用してすべての可能性をテストすることはほとんど不可能です。

どのような考えやウェブサイトの記事も大歓迎です。事前に感謝

Answer 1

*検索はまだ本当にうまくいくはずです。まだグラフの概念に精通していないのであれば、まずそれらを探し、A *検索がグラフ上でどのように動作するかを理解することから始めます。 A *に関する多くのチュートリアルはグリッドに適用されるA *に焦点を当てていますが、アルゴリズムの仕組みの1つの特殊なケースです。一般的なグラフでも同様に機能します。

一般的なグラフ構造に精通したら、グリッドベースのA *またはDijkstraのアルゴリズムを自分の場合に適用するために必要な変更は比較的軽微です。基本的には、開始位置と終了位置を表す新しいノードを追加し、適切に重み付けされたエッジで4つの近傍の格子点に接続します。そこから、いつものようにA *を実行できます。

出発点を探していたら、基本的なデータ構造とグラフアルゴリズムに関するクラスを教えて、some slides on Dijkstra's algorithm and A* searchを入れて、トピックの紹介になるかもしれません。がんばろう！