A*ナビゲーション

概要と主要な概念

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

[一般]タブ

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

延長深度

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

スムース回転

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

ディバイダーをグリッドにスナップ

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

キャッシュパス

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

メンバー

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

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

[動作]タブ

パスを検索

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

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

衝突回避

チェックボックスをオンにすると、移動者がパスにノードを割り当て、通過後に割り当てを解除します。これにより、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. [完了率]トラッカーを調整し、進行中のルーティングアルゴリズムを参照してください。

ディバイダー/パスプロパティ

直接ダブルクリックするか、[クイックプロパティ]を使用してディバイダー/パスプロパティにアクセスできます。

条件

このチェックボックスをオンにするとバリアが条件付きバリアになり、バリアを適用するために必要な条件を定義できます。条件付きバリアの条件は、各移動タスクの開始時に再評価されます。条件がfalse(0)を返すと、バリアがルート計算アルゴリズムに適用されず、移動者はバリアを無視して移動しようとします。条件付きバリアを使用すると、適用対象を特定の移動者に限って、または特定のモデル条件に沿って、特定のバリアを定義できます。

双方向

このチェックボックスをオンにすると、ディバイダー/パスが一方向ではなく双方向に適用されます。

ポイント(ディバイダー/一方向ディバイダー/優先パス)

各点のx、yの位置を定義します。

アイコン 説明
終わりにポイントを追加します。
選択したポイントを削除します。
選択したポイントをリスト内で上または下に移動して並べ替えます。

パスの重み

優先パスのみ。これは、パスに関連付けられたノードに追加されたパスの重みです。

仮想距離

ブリッジのみ。チェックボックスをオンにすると、実際の距離ではなく、ブリッジを通過する距離になります。

障壁プロパティ

直接ダブルクリックするか、[クイックプロパティ]を使用してバリアのプロパティにアクセスできます。

条件

このチェックボックスをオンにするとバリアが条件付きバリアになり、バリアを適用するために必要な条件を定義できます。これは前述の「ディバイダー/パスプロパティ」の説明と同じ条件です。

位置とサイズ(バリア)

バリアのサイズと位置を指定します。

A*グリッド

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

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

ノード間隔

グリッド内のノード間の距離(モデル単位)です。間隔が狭くなると、移動メンバーはより円滑かつ直接的に移動できますが、ノードを増やすとパスを計算する処理時間が長くなります。

ビュー グリッド Z の設定

3Dビューの現在のグリッドZをこのグリッドのZ位置に設定します。