RecastNavigationを使ってナビゲーションAIを学習していく 3

初めに

　今回は第３回です。初めての人は第一回を見てください。今回は左ウィンドウのTool欄になります。
　この記事を見てくれている皆様に向けて注意点が一つがひとつ。注意して書いているつもりですが、間違ってる可能性が十分にあるのでその点だけ注意してください¹。

第4回を上げました。
追記: 第5回を上げました。

エディタを見ていく（Tools欄(左ウィンドウ)）

Test Navmesh

　これは名前の通りナビメッシュによる経路探索を行う項目になります。左クリックでゴール地点・右クリックでスタート地点を設定します。なぜかこのようにしたかは知りませんが、シフトを押しながらクリックすると問答無用でスタート地点の設定しかできません。

・Pathfind Follow

　経路探索を行いますが「Follow」と書かれている通り「スペースキー」を押す度に、スタート地点からゴール地点までを徐々に辿っていきます。

・Pathfind Straight

　経路作成時に経路を綺麗にする設定（というよりは例？）です。
　「string pulling」アルゴリズムを実行している関数に影響しています。
　メッシュの中心（恐らく重心）に合わせて経路を作成すると、経路がおかしくなってしまうので、それを防ぐアルゴリズムです。下の図で説明すると、赤線から黄線にするアルゴリズムです。詳しい説明はこのサイトで説明されています。
　
※画像元

None

Noneなので下のように起伏がある地形だと、まずめり込みます。

Area

　正直なところ、「None」と変わっていない気がします。説明によると、「エリアが変わる場所で、全てのポリゴンの端に交差する頂点を追加します。²」になっています。恐らく「エリアの端と経路が重なっている部分に頂点を追加する」という事です。

※頂点→赤色の丸　ポリゴンの端→黄色の丸

　ここでいうエリアというのが、よく分からないのですが、使う先を辿っていくと「各ポリゴンに割り当てられたエリアID」となっているので、恐らく「各ポリゴンをひとまとめにしたエリア」の事だと思います。

例）

・ナビメッシュを構成するポリゴンは上図のようにねっていた場合

・それらをまとめたものを「ポリゴンエリア」からきていると思います³。
※上図の数値は適当です

All

　これが通常になると思います。説明によると、「ポリゴンのエッジが交差するたびに頂点を追加します。」となっています。恐らく「エリアの端・境目と経路が重なっている部分に頂点を追加する」という事です。

※頂点→赤色の丸　ポリゴンの端→黄色の丸　ポリゴンの端→緑色の丸

・Pathfind Sliced

　経路探索がどのように行われているかを視覚的に見えるようにしている機能です。ちなみに、NavMeshTesterToolでhandleUpdate関数を使っているのはこの機能のみです。

・Distance to Wall

　一番近いナビメッシュの端までの距離と場所とベクトルを求める機能です。

・Raycast

　開始位置と終了位置間のレイキャストを行う機能です。ゲーム次第ではよく使う機能になりそうです。

　ただし、この関数は一つ注意点があり、説明にも書いているのですが、短距離用のXZ平面の2Dレイキャストになっています。その為、結果がおかしい事になることがあります。その代わりかなり高速に処理できます。

・Find Polys in Circle

　ダイクストラ法で円内のポリゴンエリア⁴を検索する機能です。正確には、Start位置を基準にしたEnd位置までの円内に存在するポリゴンエリアをダイクストラ法で検索する機能になります。表示されている矢印は検索手順になっています。そして、これもXZ平面の2Dになっています。

・Find Polys in shape

　ダイクストラ法である形状内のポリゴンエリア⁴を検索する機能です。正確には、Start位置を基準にしたEnd位置までの形状内に存在するポリゴンエリアをダイクストラ法で検索する機能になります。表示されている矢印は検索手順になっています。そして、これもXZ平面の2Dになっています。
　ちなみに「形状」は四角形になっていますが、内部的には変更可能です。

・Find Local Neighbourhood

　ダイクストラ法で円内の重複しないポリゴンエリア⁴を検索する機能です。「Find Polys in Circle」と似ていて、Start位置を基準にした円内に存在するポリゴンエリアをダイクストラ法で検索する機能になります。検索範囲はAgentのRadiusによって変化します。表示されている矢印は検索手順になっています。そして、これもXZ平面の2Dになっています。
　この方法は、検索半径が小さく、結果のポリゴン数が少ない場合に最適化されます。

・Set Random Start/Set Random End

　これは、名前の通りランダムにスタート地点とゴール地点を設置します。ただし、ゴール地点設置時はスタート地点と接続されているポリゴンエリア内のみ設置されます。

・Make Random Points

　これも、名前の通りナビメッシュ上に一定数のランダムなポイントを設置します。デモでは64個設置するようになっています。

・Make Random Points Around

　これは、スタート地点から一定範囲の円内に存在するポリゴンエリア上に一定数のランダムなポイントを設置します。これも同じく、デモでは64個設置するようになっています。

・Include Flags/Exclude Flags

　クエリフィルターの設定を行います。詳細は「Create Convex Volumes」で紹介します。

Prune Navimesh

　これはナビメッシュの「選択・解除」を行う機能です。シンプルにそれだけの機能です。内部的な話になるのですが、「class NavmeshFlags」で選択されたかどうかの確認をしているみたいです。

・Clear Selection

　全ての選択を解除します。正確には「class NavmeshFlags」の選択を解除します。

・Prune Unselected

　選択されていない全てのナビメッシュのフラグを解除します。正確にはnavmeshのsetPolyFlags関数でナビメッシュを無効化しています。

Create Off-Mesh Connection

　接触していないナビメッシュ同士を**One Way（一方通行）かBidirectional（双方向通行）**で接続します。
　注意点が一つ、ナビメッシュを再生成しないと適用されません。つまり動的ではないわけです。

Create Convex Volumes

　読み込んだジオメトリに凸型形状を作成する機能で、経路探索に影響を及ぼします。この機能を使えば、このエリアは「海なので通さない」などの設定を可能にします。経路探索でいう「コスト」をどこに設定するかの機能になります。これも上記と同じようにナビメッシュを再生成しないと適用されないので注意が必要です。
　あと、凸型形状の確定には、形を確定したい時に最後クリックした頂点の場所をもう一度クリックする必要があります。
　この機能には数種類のタイプがあって、そのタイプによって経路探索に様々な影響が出ます。

　コストの設定は別の場所で行っています。RecastNavigationでは凸型形状の各種類をコストと能力(機能)で切り離して扱っているので、通さない場合などはコストをバカ高くするのではなく、Include Flags/Exclude Flagsで能力(機能)の設定を行います。

内部の話

フラグ[^7]管理：Recast.h/class rcAreaModification フラグ[^7]とナビメッシュの関連付け：Recast.h/rcMarkConvexPolyArea() コストの設定：DetourNavMeshQuery.h/class dtQueryFilter/setAreaCost() エリアの色を設定：Sample.h/class SampleDebugDraw/areaToCol()

・Shape Height

　凸型形状の高さの設定です。「ナビメッシュ表面にしか影響しないだろ」と思って適当に大きくしすぎないようにしてください。実はこの凸型形状内のナビメッシュ全てに影響するので、不意な形でナビメッシュに影響が出ます。

・Shape Descent/Poly Offset

1. 凸型形状の位置を下げる設定です。
2. 凸型形状を外側に大きくするオフセット量の調整です。

Create Crowds

　群衆AIを司る機能です。ある意味、RecastNavigationの最終形態です。少し特殊な操作の説明↓

1. スペース：動作の停止/続行
2. 数字キーの１：１フレームのみ続行
   
   ※ 内部を見ていると所々で「neighbour」という単語が出てきますが、これは「付近のエージェント」のことです。

・Create Agents

　エージェント⁵の設置と削除を行う機能です。削除はシフトを押しながら左クリックです。

・Move Target

　通常はエージェントの目的地を設定します。これはクリックした座標を目的地にします。
　シフトを押しながら左クリックor右クリックで、押した地点の方向へ向かって進みます⁶。これは、「各エージェント座標から押した瞬間の座標へのベクトル」を決めて、目的地を決めません。

・Select Agent

　エージェントを一体選びます。これを行うと、選択された一体のみを動かします。なお、これを行わないと「Selected Debug Draw」欄が適用されません。

・Toggle Polys

　エージェントが通過出来るポリゴンエリアの有効/無効を設定します⁷。
　ただし、ポリゴンエリア上にエージェントが存在する場合に注意が必要です。基本は別のポリゴンエリアにかなりの速度で弾き出されますが⁸、たまに、無効になったポリゴンエリアに残ったままのエージェントがいる事があります。こうなると、再び有効にしても全く動かなくなります。
　なので、無効にする際はそのポリゴンエリア上にエージェントが存在しない事を確認してから、無効にする必要がありそうです。

・Options

1.Optimize Visibility

　指定されたポイントがエージェントから見える場合、エージェントのパスの最適化を試みる機能です⁹。
　不正確な移動¹⁰or動的障害物回避¹¹は元のコライダーから大きく外側に位置を強制する可能性があり、時間経過で最適でないコライダーが形成される可能性があります。それにより最適でないパスが形成される事もあります。そういう場合にこの関数を使います。なお、エージェントの動きが不正確であるほどこの機能は有益になります。ただし、長距離検索の場合は適していません。
　結局、一言で言うと「次のポイントが直視出来たら、既存のパスよりも直接ポイントに向かって移動する方が良いじゃん」ということです。
　因みに、最適化された経路を表示するには、Show Path Optimizationで表示可能です。

2.Optimize Topology

　ローカルエリアパス検索を使用して、エージェントのパスの最適化を試みる機能です⁹。
　不正確な移動¹⁰or動的障害物回避¹¹は、エージェントの位置をかなり外側に変更する可能性があり、時間経過で最適でないコライダーが形成される可能性があります。そういう場合にこの関数を使います。なお、エージェントの動きが不正確であるほどこの機能は有益になります。

3.Anticipate Turns

　書いてある通り、エージェントの予想される回転方向をスムーズにする機能です。少なくとも、RecastNavigationでは「予想される回転方向と移動方向」も合わせて２回スムージングしていることになりますね。
　
※予想される回転方向→青色の丸　移動方向→黒色の丸

4.Obstacle Avoidance

　これも名前の通り、障害物（付近のエージェント）を回避する機能です。ただ、これをオフにするだけでは「付近のエージェントを無視して進む」にはなりません。イメージとしては「回避する」から「重ならないようにする」という感じでしょうか。

5.Avoidance Quality

　上記の回避具合を変更する機能です。これは、あらかじめ設定された「障害物回避パラメーター」の設定を変更します。初期化時にいくつかのパターンが設定されています。

内部の話

・障害物回避パラメーター：DetourObstacleAvoidance.h/struct dtObstacleAvoidanceParams ・設定場所：CrowdTool.cpp/void CrowdToolState::init()内

6.Separation

　エージェント同士を分散¹²させる機能です。

7.Separation Weight

　上記の分離具合を変更する機能です。0にすると上記をOFFにした時と変わらなくなります。

・Selected Debug Draw

　１体のみを対象とした、デバッグ描画欄です。Select Agentでエージェントを選択しないといけません。

1.Show Corners

　エージェントが通る経路上の「角」を表示します。有効な（表示されている）コーナーは群衆AIの動作により「最大コーナー数－1」になります。

内部の話

・最大コーナー数：DetourCrowd.h/DT_CROWDAGENT_MAX_CORNERS ・群衆AI(マネージャー)の動作：DetourPathCorridor.h/class dtPathCorridor/int findCorners()


2.Show Collision Segs

　円内・円上に存在する壁の境界線に描画します。円の半径は「ステアリング動作を開始する距離」になっています。なお、「エージェントの座標・セグメントの始点・終点」でナビメッシュ上に三角形を形状出来ない場合は、矢印の色が暗くなります。
　エージェントが通った後に存在するクロスポイントは、一定距離ごとに更新されます。

内部の話

・ステアリング動作を開始する距離：DetourCrowd.h/struct dtCrowdAgentParams/float collisionQueryRange ・セグメントを追加している場所：DetourLocalBoundary.h/class dtLocalBoundary/void update()


3.Show Path

　経路上に存在するポリゴンエリアを明るく描画します。

4.Show VO

　これについては理解が微妙なんですが、恐らく、ペナルティーを四角形の色で描画したものだと思います。その為、円の半径が「エージェントの最大速度」になっています。ペナルティーの表現として白がペナルティー無しで、赤色がペナルティー最大です。

内部の話

　ペナルティーといっても、表示しているペナルティーは２種類あって、「合計ペナルティー」・「はみ出た分のペナルティー」になっています。色の表現は「合計ペナルティー：**白→最小**、茶色→最大」、「はみ出た分のペナルティー：合計ペナルティーの色→最小、赤色→最大」になっています。 ・ペナルティーの管理：DetourObstacleAvoidance.h/class dtObstacleAvoidanceDebugData

※余談ですが、「VO」って何の略ですかね？教えて詳しい人～。

5.Show Path Optimization

　最適化された経路を表示します。正確には「エージェントの位置」から「Optimize Visibilityで最適化された次の位置」になります。

6.Show Neighbours

　円内・円上に存在する「付近のエージェントの距離」と「付近のエージェントとエージェントまでの線」を描画します。円の半径は「ステアリング動作を開始する距離」で、「ステアリングを考慮する付近のエージェント最大数」分だけ表示します。

内部の話

・ステアリングを考慮する付近のエージェント最大数：DetourCrowd.h/DT_CROWDAGENT_MAX_NEIGHBOURS ・ステアリング動作を開始する距離：DetourCrowd.h/struct dtCrowdAgentParams/float collisionQueryRange


・Debug Draw

　群衆AI全体のデバッグ表示を行う欄なので、特定のエージェントを選択する必要はありません。

1.Show Labels

　これはエージェントを管理するラベルを表示します。ラベルというより配列の添え値なんですけどね。動的配列（初期化時にサイズを決めているので、実際のところ固定長配列みたいなもの）なんですが、添え値をキーにして、内部フラグのON/OFFで扱っています。動作だけ別で扱うので、こうなるのは仕方ないですね¹³。

2.Show Prox Grid

　エージェントの近接グリッドを表示します。これはエージェントがどれだけ「密」であるかを表しています。「密」であればあるほど濃くなっていきます。

3.Show Nodes

　経路探索に使用したノードとヒューリスティックコストを表示します。
　ON時は常に表示して欲しいのですが、「エージェント位置」から「物理的に接触していないポリゴンエリアの位置」に目的地を設置した時などにしか表示されません。その為、最初は「あれ？」となるので、注意して下さい。

4.Show Perf Graph

　群衆AI全体の処理時間を表します。

5.Show Detail All

　Selected Debug Drawでは選択したエージェントしか描画されませんでしたが、この項目をONにすると全てのエージェントにSelected Debug Drawの内容が描画されます。

Create Tiles

　これはタイル毎にナビメッシュを生成・削除する機能です。正確には「Tile Mesh」・「Temp Obstacles」のナビメッシュ生成法によるもので、ナビメッシュ生成する際に分割し、「タイル」として生成しています。これが動的にナビメッシュを生成出来る秘密です。
　タイル上に左クリックでナビメッシュ生成、右クリックでナビメッシュ削除します。「Properties」欄の「Tiling」欄に「TileSize」があるので、そこでタイルサイズを変更出来ます。

Create All

　全てのタイルを生成します。これは「Build」と同じです。

Remove All

　全てのタイルを削除します。

Highlight Tile Cache

　これはタイルの選択を行い、そのタイルの描画を変更する機能です。

デモの問題点

　今回は中身編ではなく、デモの問題点を述べたいと思います。
1.メッシュ同士でまとめてナビメッシュを生成出来ない
2.「offmesh links」が「TileMesh/TempObstacle」上だと上手く機能しない事が多い ※最新バージョンに更新したら治っていました。

・1 についてです。


　上の画像を見てもらえれば分かると思うのですが、Unityではメッシュ同士を近づけたら、自動的にナビメッシュがマージされます。ですが、デモ版は少しいじった程度では自動的にマージされるわけがないので、マージするように自分でどうにかしないといけません。この機能はゲーム製作上、必要になることが多いかもしれないので皆さんもやりましょう¹⁴。(｀･ω･´)

愚痴というか不満点なんで見なくてもOKです

1. 条件式でint型をbool値のように扱うのをやめてくれぇ～ 2. ヌルを表すのに0を使うのはやめてくれぇ～、せめてNULLを使ってくれぇ～ 以上。愚痴のような不満点でした（笑）

1. 流石に分かっていると思いますが、念の為書いておきます。 ↩

2. 圧倒的Google翻訳クオリティ... ↩

3. 上図の「ポリゴンエリア」は長いので、「ポリエリア」と書いています。 ↩

4. RecastNavigation上の説明では「ナビゲーショングラフ」となっているのですが、ここでは「ポリゴンエリア」としておきます。 ↩ ↩² ↩³

5. ここでいうエージェントとは、群衆内の一つという事です。つまり、エージェントをが集まったモノを「群衆」と解釈してください。にしても「Agent」の適切な日本語訳が思いつかない...。 ↩

6. 正直、あまり使わないと思いますが...。 ↩

7. 割と使える機能な気がします。 ↩

8. この時点で、ゲームとしてはダメな気がしますね...。 ↩

9. 正直、見た目は変わっていない気がします。 ↩ ↩²

10. 恐らく、他のエージェントの移動による影響のことですね。 ↩ ↩²

11. これはどの事を指しているのか分からないのですが、Temp Obstaclesではないと思います。設置・削除する度にパスを再計算しているからですね。となると、どの事を指しているのでしょう？ ↩ ↩²

12. Separationの辞書での意味は「分離・離別」なんですが、見た感じ どう見ても「分散」にしか見えないんです(笑) ↩

13. もしくは連想配列を使うという手もありますが、なにせ、ランダムアクセス性能が...。ハッシュテーブルを使えばマシにはなりますが、速度を優先するなら、添え値をキーとして扱う事になると思います。（個人としては多少気になりますがね...。） ↩

14. ナビメッシュのマージ機能をデフォルトでつけてほしかったですねぇ...。PolyMeshとPolyMeshDetailはあるんですがね...。 ↩