建物への経路探索（複数の座標を持つA *）？

Question

1）たくさんのタイルを取る建物を作ることができるゲームについて考えています。たとえば3x3です。

ビルドを開始する前に、隣接するタイルに文字を移動する必要があります。だから、建物の最短経路を見つけるアルゴリズムがありますか？

エリアの建物のタイルごとにA *を使用することを義務付けられていますか？

EDIT、exemple：

マップ：このexempleため

、（0; 0）座標がアップ左このランドマークとイメージのである： あなたのキャラクターはである想像（0; 0）

画像の左側に文字を移動するアルゴリズムを探しています。

ターゲットは「通常」のような単一の座標ではなく、4つの空白（4つのポイント）。

単一の開始座標[ここでは（0,0）]から領域[ここでは（1,2）、（8,2）、（8,0）]から最も近い位置（1,10）、（8,10）]？

私は解決策の選択肢ではなく、この例のような複数の方法の場合、[（0,2）、（1,1）]のように、すべての等価な解を与えます。

2）タイルのないマップのシステムと同じ質問ですが、座標だけですか？

Answer 1

エリアの建物のタイルごとにA *を使用する必要がありますか？最短を選択しますか？

*がある必要はありません述語、「現在は座標ときは、この座標に等しい」という目標を取ることができない、それは簡単に現在の座標がいくつかでに含まれているとき」することができset/area "に設定します。これはアルゴリズムのグローバルな構造については何も変えず、exit-testだけを変更します。

当然のことながら、あなたはヒューリスティックを容認する必要があります。あなたはこれを持つことができます

current := the node in openSet having the lowest fScore[] value 
    if current = goal 
     return reconstruct_path(cameFrom, current) 

（ウィキからコピー）：

current := the node in openSet having the lowest fScore[] value 
    if current ∈ goals 
     return reconstruct_path(cameFrom, current) 

またはこの：

ではなく、この "狭い" *のための擬似コードを、明確にするために、

current := the node in openSet having the lowest fScore[] value 
    if satisfiesGoalCondition(current) 
     return reconstruct_path(cameFrom, current) 

「現在の座標が目標の矩形の内側にあります」などのテストになります。

Answer 2

井戸array/grid version of A*は、目標地点でのヒットで停止することができるので、出発地点から目的地の座標に当たるまで増加し、次にbacktrackになります。

はい、これはノードとして障害物を設定したグラフ/ベクターバージョンでも実行できます。

あなたのタイルが（半）歩行可能な場合は、グリッドバージョンA*の方がよいでしょう。 2Dあなたのタイルマーキングのそれぞれの歩行可能なエリアと壁エリアを表すだけです。このような何か：あなたも、あなたの建物をナビゲートすることができます

• Algorithm Trax Winning Condition

私の賭けは、あなたがこの考えていなかったということですので...私はしかし、あなたの建物の内側に表示されません今まで。私は3Dグリッドを使用しています

• いくつかの内部の建物のアイデアのための2D Diamond (isometric) map editor

ので、私は3D地形や建物にもレベルを持つことができます...あなただけに必要ました：見てみましょうあなたはタイル得た場合