"方向に依存する"障害物を含む経路探索アルゴリズム？

Question

私は以下の問題を抱えています。私はゲームをプログラミングしていましたが、部屋探知ミーンズのトンネルを作る方法を決定するために、経路探索アルゴリズムを使用します。しかし、私は接近方向がである障害物コースを通る経路を見つけるアルゴリズムが必要です。私。障害物を水平に通過する経路はOKであり、垂直に進む経路は障害ではない経路であってもよい。

Aは一例を図解：我々は

..... 
a.|.b 
..... 

をお持ちの場合は

. = free space 
X = path 
| = vertical-blocking obstacle 
a = start point 
b = end point 

その後、我々は

..... 
XXXXX 
..... 

ようなパスを取得する必要があります。しかし、私たちは

..a.. 
..|.. 
..b.. 

を持っている場合

その後、我々はこれを行うだろうアルゴリズムのどのような

..XX. 
..|X. 
..XX. 

ようなパスを取得する必要がありますか？それを行うために「A *」を修正することはできますか？

Answer 1

A *はの問題を修正なしで解決します。

グリッド上の経路探索を検討していますが、（少なくともdiscrete work spacesでは）その問題はグラフの計画と同じです。その結果、グリッドを適切なグラフに変換できれば、完全なグラフ検索でこの問題は解決され、最適なグラフ検索では、要求した計画（または同等のコストのパス）が得られます。

グリッドからグリッドを定式化することになります。上記で指定したグリッドの無向グラフは、次のようになります。