A*ナビゲーション

概要と主要な概念

A*（「A Star」と発音する）は、ポイント間のパスを見つけるための検索アルゴリズムです。このアルゴリズムは、タスク実行者オブジェクト（移動メンバー）が移動中に通過するノードのグリッドを使用します。各ノードは、移動メンバーが移動できる方向を指定します。このアルゴリズムは、ノード間を対角線方向に移動することを含め、移動方向でノードを見て、どの方向が最も速いかを決定します。ノードのグリッドは、移動メンバーが移動できる場所を制限するか、特定のパスに沿って移動するように誘導するバリアを作成することで変更できます。

［一般］タブ

［一般］タブには、次のプロパティがあります。

延長深度

この数値は、ナビゲータの最も外側のバリアの外側に配置されるノードの数を指定します。この数は整数で、0より大きくなければなりません。

ｽﾑｰｽ回転

チェックボックスをオンにすると、移動者は曲がるとき滑らかに回転します。

ﾃﾞｨﾊﾞｲﾀﾞｰをｸﾞﾘｯﾄﾞにｽﾅｯﾌﾟ

チェックボックスをオンにすると、ディバイダーはA*グリッドのポイント間でスナップします。

ｷｬｯｼｭﾊﾟｽ

チェックボックスをオンにすると、処理時間を節約する目的で、A*ナビゲータはパスをキャッシュして再利用します。

ﾒﾝﾊﾞｰ

左側にあるボックスでは、表示するメンバーリストを選択します。［プロパティ］ボタンをクリックすると、選択したメンバーのプロパティウィンドウが開きます。右側にあるボックスには、現在選択されている状態ですべてのオブジェクトが表示されます。

アイコン 説明
クリックするとモデル内の任意のオブジェクトがサンプリングされ、メンバーとして追加されます。
クリックしてオブジェクト選択ウィンドウを開き、メンバーとして追加するオブジェクトを選択します。
選択したメンバーを除外します。

［動作］タブ

ﾊﾟｽを検索

移動グリッド内のノードの検索方法を定義します。オプションは次のとおりです。

  • 直角のみ - A*パス検索では、垂直または水平方向に移動するパスのみを見つけます。対角線方向の移動は使用されません。
  • 対角 - A*パス検索では、対角線方向の移動が可能です。移動者は、1ユニットを垂直に、1ユニットを水平に同時に移動できます。
  • 深い対角 - A*パス検索では、深い対角線方向の移動が可能になります。移動者は同時に2ユニットを縦に移動し、1ユニットを横に移動する、またはその逆に移動できます。

制限付き対角

オンにすると、移動者は、グリッド移動方向によって「xの次にy」と「yの次にx」の両方の方向順序付けを使用して対角線方向の目的地に移動できる場合は、対角線方向にだけ移動します。このボックスをオンにすると、移動者が角を曲がるときにパスを短くしすぎないことが保証されます。

衝突回避

チェックボックスをオンにすると、移動者がパスにノードを割り当て、通過後に割り当てを解除します。これにより、2人の移動者が同じノードを同時に通過することはありません。

非アクティブなメンバーを無視する

チェックボックスをオンにすると、衝突回避アルゴリズムにより、非アクティブ移動者が行った割り当てが無視されます。移動者が目的地に到着してアクティブな移動が終わると、移動者は衝突検出アルゴリズムで認識されなくなります。これでは、移動者がアクティブな移動をしていない他の移動者にぶつかることになります。

移動者が互いをひいてしまう軌道で走る状態は望ましくないものの、目的地が同じ他の移動者との衝突を避けるためにアイドル状態の移動者に必要な対応は、やや複雑で簡単にはわかりません。移動者が人間の場合は、互いにぶつからないよう道を譲り合い、遅延ペナルティもそれほど出ないのが一般的です。この遅延ペナルティの観点から、アイドル状態の移動者どうしが互いを無視できるようにすると、人間どうしが自然に道を譲り合う望ましい動作のシミュレーションとなります。

割り当て解除時間のオフセット

追加の待機時間を定義します。この時間が過ぎたら、移動者が離れるグリッドノードの割り当てを解除します。デフォルト（0.00）では、移動者は次のノードへの移動を開始するのと同時にそのノードをリリースします。この値がゼロより大きい場合、移動者はこの追加時間だけ待機してからノードを解放します。

ﾀｰﾝ時に停止

チェックボックスをオンにすると、新しい方向に曲がる必要がある移動者は停止し、新しい方向に回転します。

ﾀｰﾝｽﾋﾟｰﾄﾞ

移動者がターンで停止し、回転するときに使用するターン速度を定義します。

ﾀｰﾝの遅延

ターン時の停止に関連付ける追加の遅延時間を定義します。移動者が停止し、回転しなければならないとき、新しい方向へのターンにかかる時間にこの遅延時間が追加されます。

ﾄﾗﾍﾞﾙ時間によるﾙｰﾄ検索

チェックボックスをオンにすると、A*検索アルゴリズムは、パスの望ましさを評価するコスト関数として移動距離の代わりに移動時間を使用します。これを使用する際の主な違いは、移動者が曲がるために止まると、曲がるのにかかる時間を計算し、それをコスト関数に適用することです。

ﾃﾞﾌｫﾙﾄ優先ﾊﾟｽの重み

優先パスにカスタムの重みを加えない場合に使用されるデフォルトの重みです。重みを0に設定したパスには、このデフォルト値が使用されます。

［ビジュアル］タブ

これらのプロパティを使用して、A*機能の表示をオンまたはオフにします。

バリア

チェックボックスをオンにすると、バリアが表示されます。

ｸﾞﾘｯﾄﾞの境界

チェックボックスをオンにすると、グリッドの境界を示す青色のボックスが描画されます。

ｸﾞﾘｯﾄﾞのﾉｰﾄﾞ

チェックボックスをオンにすると、グリッドの個々のノードが表示されます。

ﾒﾝﾊﾞｰ

チェックボックスをオンにすると、移動者の下に青色の円が表示され、A*ナビゲータに接続された固定リソースの下に青色の長方形が表示されます。

占有点

チェックボックスをオンにすると、移動者から（その移動者に）割り当てられたノードまで線が引かれます。

ヒートマップ

チェックボックスをオンにすると、ドロップダウンで選択したオプションに基づいてヒートマップが生成されます。［最大ヒート値］は選択されたドロップダウンオプションに対応し、ヒートマップを着色するためのしきい値を定義します。

ﾄﾗﾍﾞﾙの範囲

チェックボックスをオンにすると、3Dビューで強調表示されたオブジェクトの周りに赤と青のひし形が表示されます。移動者にこのオブジェクトに移動する移動タスクが与えられると、A*ナビゲータは、赤いひし形でマークされた任意のノードと移動者との間の最短経路を計算します。移動者はこの最短経路に沿って移動を開始します。移動者が青いひし形でマークされたノードのいずれかに到達すると、オブジェクトに到着となり、移動タスクは完了します。

ﾙｰﾄ検索ｱﾙｺﾞﾘｽﾞﾑのﾃﾞﾊﾞｯｸﾞまたは表示

このチェックボックスは主にデバッグ目的で使用します。チェックボックスをオンにすると、A*検索アルゴリズムは、各移動者の最終パス検索オペレーションを追跡する追加データを保存します。この情報を参照するには：

  1. ［ﾙｰﾄ検索ｱﾙｺﾞﾘｽﾞﾑのﾃﾞﾊﾞｯｸﾞまたは表示］チェックボックスをオンにします。
  2. ［適用］ボタンを押します。
  3. モデルを実行します。
  4. 移動者をクリックするかShiftキーを押して選択します。移動者を選択すると、その移動者の前回のパス検索オペレーションに関連付けられた一連の点がA*グリッド上に表示されます。
    • 緑色の点は、A*「開いたセット」内にあるノードを表します。
    • 赤い点は、「閉じたセット」内にあるノードを表します。
    • 青い点は、「開いたセット」から「閉じたセット」に解決されているノードを示します。
    • また、各ノードの横にテキストが表示され、「g + h = f」の式が表示されます。ここで、gはノードに到達するためのコスト、hはノードから目的地までのヒューリスティック計算、fは2つの合計です。
  5. ［完了率］トラッカーを調整し、進行中のルーティングアルゴリズムを参照してください。

［条件付きのﾙｰﾙ］タブ

このタブは、ルーティングアルゴリズムでバリア、ディバイダー、優先パス、またはブリッジを適用する条件付きルールを定義するために使用します。

A*グリッド

A*のパス検索では、移動パスを解決するためにグリッドが使用されます。グリッドとは、移動エリアを囲む2次元の平面です。モデル内にバリア、ディバイダーなどをドラッグした後でモデルをリセットすると、それらのオブジェクトを囲む青い長方形の境界で表されたグリッドが表示されます。グリッドはノードの2次元配列であり、ノード間の距離はユーザーが定義します。A*移動者は、グリッド内のあるノードから別のノードに移動します。隣接ノード間で移動ができるかどうかは、バリアとディバイダーによって決まります。

どのA*モデルにも、少なくとも1つのグリッドがあります。A*モデルに含まれるバリア、ディバイダー、優先パスなどすべてを囲むために、グリッドは自動的に大きくなります。さらに、左側のライブラリからグリッドをドラッグすることで、グリッドを追加することもできます。グリッドは、他のオブジェクトと同様に、3Dビューで移動やサイズ変更ができます。また、その［ﾌﾟﾛﾊﾟﾃｨ］ペインを通して、グリッドのノード間隔やz位置を定義することもできます。

グリッドオブジェクトは、次のプロパティパネルを使用します。

［ﾃﾞｨﾊﾞｲﾀﾞｰ / ﾊﾟｽ］プロパティパネル

ディバイダーオブジェクトとパスオブジェクトは、次のプロパティパネルを使用します。

［ﾊﾞﾘｱ］プロパティパネル

バリアオブジェクトは、次のプロパティパネルを使用します。