初めに

今回は2回目です。初めて見る人は前回を見てください。

　前回はRecastNavigationのライブラリの導入と、デモ（エディタ）を動かすところまで行いました。現状はデモ（エディタ）が動いているだけなので、今回はエディタの中身を見ていくことにします。
※自分も解析しながらやっているので、間違っている箇所などがあればコメントください。

追記：第３回をあげました

RecastNavigationライブラリの関連サイト

開発者サイト
- http://digestingduck.blogspot.com/
（恐らく）公式のリファレンス
- http://www.stevefsp.org/projects/rcndoc/prod/index.html
- http://masagroup.github.io/recastdetour/index.html (こっちの方が見やすいと思います。)
CritterAI系（RecastNavigationをUnityへ導入する為のナビゲーションシステム）
- http://www.critterai.org/projects/cainav/doc/ (リファレンス)
- http://www.critterai.org/projects/cainav/doc/html/e72bd1ee-04b0-4bbb-a21d-d8d7ecaa11af.htm (ナビメッシュ生成手順)
- https://blog.csdn.net/you_lan_hai/article/details/77428858 (ナビメッシュ生成手順（中国のサイト))
- http://www.critterai.org/projects/cainav/doc/html/6fb3041b-e9be-4f03-868b-dcac944df19b.htm#seeAlsoToggle (地形の概要)

やりたいこと

自分が必要としているライブラリ機能を一覧にします。

必要な機能
ナビメッシュの自動生成
ナビメッシュによる経路探索
※ 群衆AI

群衆AIについて

RecastNavigationには「DetourCrowd」という群衆AIを担当するものがあるのですが、基本的なものしかないみたいです。なので、群衆AIについては別のライブラリを使おうと思います。　正確にはステアリングシステム(動的な障害物を避けるシステム)も混ざってくるのですが、候補としては「OpenSteer」か「SteerSuite」があります。今現在分かっている段階での情報です ↓ ・「OpenSteer」は比較的最近まで更新されているのですが、Recastを使っておらず独自のシステムで経路探索などを行っています。・「SteerSuite」は４年前から更新されていないのですが、RecastNavigationを使って経路探索などを行っています。

エディタを見ていく（Properties の共通部分）

1. 読み込みについて

まず起動時から見ていきます。右のウィンドウの「Properties」から操作していくことになります。

・Show Log

　これは名前の通り、ログウィンドウの表示・非表示を管理します。表示内容はナビメッシュ生成時などの進捗・警告・エラーを表示します。

・Show Tools

　これも名前の通り、ツールウィンドウの表示・非表示を管理します。表示内容は下にある「Sample」によって変化します。いわゆる「こんなことが出来るよー」という機能の一覧表示ですね。

・Sample

　前回、エディターを実行したときに「どう違うの？」という感じに気になった人が多いのではないでしょうか。
　一言で言うなら「RecastNavigationでのナビメッシュの使い方」です。

-Solo Mesh

1つの大きなメッシュを構築する
つまり一度に大きなメッシュを直接生成する
静的な世界を構築する場合に適している

-Tile Mesh

多くの小さなタイルから構築する
つまり小さな凸面ポリゴンを生成し、それらを接続する
動的な世界を構築する場合に適している

-Temp Obstacles

一時的な障害物を構築する

　上記の通り、ナビメッシュの生成には大きく分けて２種類が存在します¹。「Solo Mesh」は静的な地形に使い、「Tile Mesh」は動的な地形になると思います。
　「Temp Obstacles」は「Tile Mesh」でナビメッシュを生成していますが、一時的な障害物の設置がナビメッシュ構造に影響を与えているので「Sample」に存在すると思います²。

・Input Mesh

　現状、エディタでは「.Obj」と「.gset」ファイルの読み込みに対応しているようです。gsetファイルはメッシュの読み込み先・ナビメッシュ設定・Tool設定が保存されている内部で使うファイルです。あと、gestファイルは「9キー」で生成する事が出来ます。

2. ナビメッシュ生成設定

　今から紹介するのは、ナビメッシュ生成設定の共通部分になるのでSampleの三つ全部に当てはまる設定になります³。

・Rasterization

※ ナビメッシュの事です。

-Cell Size

　その名の通りセルのサイズで、分かりやすく言うとナビメッシュのサイズになります。ナビメッシュのサイズなのでナビメッシュの綺麗さ・生成時間に大きな影響を与えます。

-Cell Height

これは、ナビメッシュの地形メッシュ⁴ からの高さになります。余りにも大きい数値にするとナビメッシュが分離するので注意が必要です。これも生成時間に多少の影響を与えます。

-Voxels

　ナビメッシュのサイズ（面積）を表していて、「X軸 x Z軸」の平面になっています。

・Agent

※ 値をいじれば分かるのですが、「Agent」は経路探索を行う対象のことです。

-Height・Radius

　その名の通りです。現状、円柱以外は想定していないので注意してください。

-Max Climb

　地形メッシュを登れる最大の高さの事で、これに合わせてナビメッシュも生成されます。そのため階段等で威力を発揮しますが、実は「Height」の値も影響するので注意してください。

-Max Slope

　歩ける最大勾配の事で、これに合わせてナビメッシュも生成されます。そのため坂道等で威力を発揮します。

-生成時間との関係

　どのパラメータもナビメッシュが増えるような設定にすると、生成時間が増加し、逆も同じです。ただし、地形メッシュに依存するので必ずとは言えませんし、増加したところで少ししか増加しないので「気にしない」もありな気がします。

例

「nav_test.obj」を地形メッシュとして「Max Climb」を最大にすると、階段部分等のナビメッシュが増え、その結果、生成時間が増加します。

・Region

※ ナビメッシュ領域の事です。

-Min Region Size

　ナビメッシュ領域の最低サイズの事で、これに合わせてナビメッシュも生成されます。不用意に大きくすると必要な領域が削除される可能性があり、僅かに生成時間に影響があります。

-Merged Region Size

　付近のナビメッシュ領域とマージするサイズの事で、これに合わせてナビメッシュも生成されます。不必要に小さい領域を減らす為で、少しナビメッシュ生成に影響があります。

・Partitioning

※ ナビメッシュの分割方法の事です。

-分水界分割(Watershed partitioning)

メリット
- 綺麗なナビメッシュを生成
- 最も良いテッセレーションを作成
デメリット
- 最も遅い
- メモリを多く消費する
ナビメッシュを事前計算する場合は一般的に最良の選択

-モノトーン分割(Monotone partioning)

メリット
- 最速
- 地形を穴や重複のない領域に分割（保証）
デメリット
- 無駄に迂回する経路を作成する可能性がある
高速なナビメッシュ生成が必要な場合はこれを選択

-レイヤー分割(Layer partitoining)

メリット
- かなり速い（分水界分割より早い）
- 地形を重複しない領域に分割する
デメリット
- モノトーン分割より遅い
中型および小型でタイル張りされたナビメッシュに使用する場合はこれを選択

※グーグル先生による翻訳なので多少の誤訳は気にしないでください。
　上記のようなことをソース上のコメントで書かれています⁵ が、細かい説明は省いています。

-計測結果

　試しに「nav_test.obj」をデフォルト設定で10回計測して平均を求めました。

\	分水界分割	モノトーン分割	レイヤー分割
Solo Mesh	486.5	379.1	686.4
Tile Mesh	729.8	603.7	633.0
※単位はms、CPUはCorei7-9750Hです。

　予想はしていましたけど、説明されているようにはなっていないので「速い」系の話は余りあてにならないので、理論上の速さなのでしょう。しかも「nav_test.obj」での速さなので、さらに広くなると凄いことになりますね...。実際に販売されているゲームではどう最適化されているんでしょう？

・Filtering

※ 歩行可能な面のフィルターし、不要なオーバーハング・キャラが立つことができないフィルタスパンを削除する事が目的になっています。簡単に言うならナビメッシュを綺麗にする機能です。

-Low Hanging Obstacles

　縁石などの低層の物体や階段などの構造物の上を歩行可能領域の形成を可能にするフィルターです。その為、低層の物体などの構造物が多いほど生成時間に影響を及ぼします。

-Ledge Spans

　出張りの部分を削るフィルターです。主に「Agent」の「Radius」によって大幅に変わり、生成時間にそこそこ影響があります。

-Walkable Low Height Spans

　指定された高さよりも低い場合、歩行可能スパンを歩行不可とするフィルターです。ナビメッシュ生成時間に僅かに影響あります。

・Polygonization

※ ポリゴン化を行う際の設定です。

-Max Edge Length

　メッシュの境界に沿った輪郭エッジの最大許容長です。メッシュの境界の長さなので、短くすればするほど境界部分が「ガクガク」になってしまいます。

-Max Edge Error

　輪郭のエッジが元の輪郭から逸脱する最大距離で、ナビメッシュを「どれだけ地形メッシュに合わせるか」を調整する機能です。その為、短くすればするほど端が「カクカク⁶」になります。

-Verts Per Poly

　輪郭からポリゴンへの変換時に生成する頂点の最大数です。一定数を超えると全くナビメッシュが生成されなくなるので注意が必要です。

・Detail Mesh

※ ナビメッシュの詳細設定です。

-Sample Distance

　地形をサンプリングするときに使用する距離で、少ないほど生成時間が増加し、ナビメッシュが綺麗になります。
※ 0にすると生成途中でお亡くなりになるので注意してください。⁷

-Max Sample Error

　ナビメッシュ表面が地形データから逸脱する最大距離で、少ないほど生成時間が増加しナビメッシュが綺麗になります。逆に大きくするとナビメッシュから地形がはみ出てしまいます。

ソースコードを見ていく（Properties の共通部分）

※ ここからはソースコードになってくので、「エディタ部分だけで十分！」「ソースは自分で見ていきたい！」人はとばしてください。
　今回は触り部分を見ていきますが、見ていくたびにコードを書き換えたくなる衝動にかられます(笑)。コードの注意点は、コード部分に書かれている行数はあくまで自分の環境での行数なので参考程度です。更には、色々と書き換えているので初期状態と異なる場合があります。

前提

　以降、紹介するにあたって「ポリモーフィズム」を理解していると、コードの理解・解析に役に立ちます。

関係図はこのようになってます↓

　「class Sample」を「class Sample_SoloMesh」「class Sample_TileMesh」「class Sample_TempObstacles」が継承しています。

※ コードを「見える化」してくれるソフトがあると便利です。自分は「Sourcetail」を使っています。⁸

ナビメッシュ生成設定

main.cpp

682		sample->handleSettings();

　ここで設定を行っており、ポリモーフィズムによって「Sample」で設定した各々の「handleSettings」関数へ移行します。そして、中で別々の処理を行います。

各Sampleの共通部分の設定を行う関数

Sample.cpp

void Sample::handleCommonSettings()
{
	// 分類：ラスタライズ----------------------------------------------------------------------
	imguiLabel("Rasterization");

	imguiSlider("Cell Size"/* セルのサイズ */, &m_cellSize, 0.1f, 1.f, 0.01f);
	imguiSlider("Cell Height"/* セルの高さ */, &m_cellHeight, 0.1f, 1.f, 0.01f);

	// 地形メッシュが存在する
	if (m_geom)
	{
		const float* bmin = m_geom->getNavMeshBoundsMin();
		const float* bmax = m_geom->getNavMeshBoundsMax();
		int gw{}, gh{};
		std::array<char, 64u> text{};

		// グリットサイズの計算
		rcCalcGridSize(bmin, bmax, m_cellSize, &gw, &gh);

		snprintf(text.data(), text.size(), "Voxels  %d x %d", gw, gh);
		imguiValue(text.data());
	}

	// 分類：エージェント（経路探索を行う対象）情報---------------------------------------------
	// ※ ナビメッシュの生成に影響を及ぼす
	imguiSeparator();
	imguiLabel("Agent");

	imguiSlider("Height"/* 高さ */, &m_agentHeight, 0.1f, 5.0f, 0.1f);
	imguiSlider("Radius"/* 半径 */, &m_agentRadius, 0.0f, 5.0f, 0.1f);
	imguiSlider("Max Climb"/* 壁を登れる高さ */, &m_agentMaxClimb, 0.1f, 5.0f, 0.1f);
	imguiSlider("Max Slope"/* 歩ける最大勾配 */, &m_agentMaxSlope, 0.0f, 90.0f, 1.f);

	// 分類：ナビメッシュ領域-------------------------------------------------------------------
	imguiSeparator();
	imguiLabel("Region");

	// ナビメッシュ領域の最低サイズ（不必要に大きくすると必要な領域が削除される可能性がある）
	imguiSlider("Min Region Size", &m_regionMinSize, 0.0f, 150.0f, 1.f);

	// 付近のナビメッシュ領域とマージするサイズ（不必要に小さい領域を減らす為）(ただ、値を大きくすればするほど ナビメッシュ生成に時間がかかる)
	imguiSlider("Merged Region Size", &m_regionMergeSize, 0.0f, 150.0f, 1.f);

	// 分類：分割-------------------------------------------------------------------------------
	imguiSeparator();
	imguiLabel("Partitioning");

	// 分水界分割
	if (imguiCheck("Watershed", m_partitionType == SAMPLE_PARTITION_WATERSHED))
		m_partitionType = SAMPLE_PARTITION_WATERSHED;

	// モノトーン分割
	if (imguiCheck("Monotone", m_partitionType == SAMPLE_PARTITION_MONOTONE))
		m_partitionType = SAMPLE_PARTITION_MONOTONE;

	// レイヤー分割
	if (imguiCheck("Layers", m_partitionType == SAMPLE_PARTITION_LAYERS))
		m_partitionType = SAMPLE_PARTITION_LAYERS;

	// 分類：歩行可能な面のフィルター ---------------------------------------------------------
	// 不要なオーバーハングと、キャラが立つことができないフィルタスパンを削除 → いわゆるナビメッシュを綺麗にする機能
	imguiSeparator();
	imguiLabel("Filtering");

	// 縁石などの低層の物体や階段などの構造物の上を歩行可能領域の形成を可能にする（低層の物体などの構造物が多いほど、生成時間に影響が出てくる）
	if (imguiCheck("Low Hanging Obstacles", m_filterLowHangingObstacles))
		m_filterLowHangingObstacles = !m_filterLowHangingObstacles;

	// 説明を訳すなら出張り部分を削る（主にエージェントの幅によって大幅に変わる・ナビメッシュ生成時間にそこそこ影響あり）
	if (imguiCheck("Ledge Spans", m_filterLedgeSpans))
		m_filterLedgeSpans = !m_filterLedgeSpans;

	// 指定された高さよりも小さい場合、ウォーク可能スパンをウォーク不可としてマークする（ナビメッシュ生成時間に僅かに影響あり）
	if (imguiCheck("Walkable Low Height Spans", m_filterWalkableLowHeightSpans))
		m_filterWalkableLowHeightSpans = !m_filterWalkableLowHeightSpans;

	// 分類：ポリゴン化------------------------------------------------------------------------
	imguiSeparator();
	imguiLabel("Polygonization");
	/// 圧倒的語彙力不足！

	// メッシュの境界に沿った輪郭エッジの最大許容長(短くすればするほど端が「ガクガク」になる)
	imguiSlider("Max Edge Length", &m_edgeMaxLen, 0.0f, 50.0f, 1.f);

	// 輪郭のエッジが元の輪郭から逸脱する最大距離（ナビメッシュをどれだけ地形に合わせるか（短くすればするほど端が「カクカク」になる）） 
	imguiSlider("Max Edge Error", &m_edgeMaxError, 0.1f, 3.0f, 0.1f);

	// 輪郭からポリゴンへの変換時に生成する頂点の最大許可数（一定数を超えると全くナビメッシュが生成されなくなる）
	imguiSlider("Verts Per Poly", &m_vertsPerPoly, 3.0f, 12.0f, 1.f);

	// 分類：詳細メッシュ----------------------------------------------------------------------
	imguiSeparator();
	imguiLabel("Detail Mesh");

	// 地形をサンプリングするときに使用する距離(少なければ少ないほど生成時間が増加し、ナビメッシュが綺麗になる)※0だと生成途中でお亡くなりになるので注意
	imguiSlider("Sample Distance", &m_detailSampleDist, 0.1f, 16.0f, 1.f);

	// ナビメッシュ表面が地形データから逸脱する最大距離(少なければ少ないほど生成時間が増加し、ナビメッシュが綺麗になる)※多くするとナビメッシュから地形がはみ出てしまう
	imguiSlider("Max Sample Error", &m_detailSampleMaxError, 0.0f, 16.0f, 1.f);

	imguiSeparator();
}

## ナビメッシュ生成

main.cpp

689		if (!sample->handleBuild()) { ... }

　ここで生成を行っており、ポリモーフィズムによって「Sample」で設定した各々の「handleBuild」関数へ移行します。そして、中で別々の処理を行います。

経路探索

main.cpp

464		sample->handleClick(ray_start, pos, processHitTestShift);

　ここで経路探索を行っており、「class Sample」の「handleClick」関数へ移行します。行われる条件はマウスの左・右ボタンを離した瞬間、メッシュデータが存在し、「Sample」も選択している状態で、マウスの指すレイと読み込まれたメッシュが当たった時のみ行われます。

群衆AI

main.cpp

490		sample->handleUpdate(DELTA_TIME);

　ここで更新を行っており、「class Sample」の「handleUpdate」関数へ移行します。勿論、群衆AIも含まれていますが、全体的な更新（正確には「Tool」の更新）はここで行われます。

　「handleClick」と「handleUpdate」の詳しい説明は、関数内で「struct SampleTool」と「struct SampleToolState」のポインタを使っていて、話がややこしくなるので詳細は次回以降にします。

こいつらのせいですね ↓

Sample.h

167		SampleTool* m_tool;
168		SampleToolState* m_toolStates[MAX_TOOLS];

　とりあえず、「Properties」の自分に関係がある所を挙げて、基本は上記のエディタ部分に合った内容だけしています。なので、短くなってしまいました(笑)。いや、短いぐらいがいいのかな？

次回

　まだまだ説明できない様な謎ばかりなので、今回と同じくエディタとソースコードの解明をしていきます。次は「Tool」の説明をしようと思います。こっそり、自作ライブラリへ移植するためのクラス設計を模索中です。

（モチベーションってどうやってキープするんだろう...。）

参考サイト

https://groups.google.com/forum/#!topic/recastnavigation/c8L7CE4nyvU （Solo MeshとTile Meshの違い）
https://blog.csdn.net/u013272009/article/details/80281642 （Tile MeshのTileの説明（中国のサイトです ⁹））

調べれば他もあると思いますが、取り敢えず今はこの二つだけとします。 ↩
もしくは、RecastNavigationの作成者が強調したいがために、あえて「Tool」欄だけでなく「Sample」で紹介したかったのかもしれません。 ↩
RecastDemo/Source/Sample.cpp の 217行目付近（自分はコメントなど書いているので初期状態と比べると誤差あり）に書かれています。 ↩
いわゆる地形データ（objファイル）なのですが、こっちもメッシュとも言い、紛らわしいので以降は「地形メッシュ」と呼びます ↩
場所は「RecastDemo\Source\Sample_SoloMesh.cpp」の532行目付近にあります。 ↩
圧倒的語彙力不足...！ ↩
RecastNavigationの作成者が最小値を設定し忘れただけだと思います。他にもコメントのスペルミスもありますし、ライブラリ自体が大きいので仕方ないですね。 ↩
使い方は「 https://qiita.com/imasaaki/items/f24fc76fa3ea1d11813c 」を参考にして下さい。 ↩
なぜか「RecastNavigation」関係のサイトにはアメリカに続いて、中国が多いんですよね。（こんなに中国のサイトを訪れたのも初めてかもしれない。） ↩