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


# 最初に
　今回は４回目になります。なので、初見の人は[第一回](https://qiita.com/HnniTns/items/c76dcef212e36455b87e)を見るようにしてください。といっても、第１～３回とは独立しているので問題ないと思います[^0]。

　今後のRecastNavigation記事関係の方針はUnityのナビゲーションシステムと同等もしくはそれ以上の機能を実装していきたいと思っています。
　今回の内容は「``OffMesh Link``を自動生成する事で、群衆エージェントに段差を一方通行で移動したい」という内容です。Unityの機能としては[この記事](https://gametukurikata.com/navigation/offmeshlink)と同等になるかと思います。

[^0]: そもそも、初見の人がこの記事に辿り着く可能性は非常に低い疑惑はあります(笑)

# 目次

+ 第１回：**``OffMesh Link``の自動生成（前半）（この記事）**
+ 第２回：[``OffMesh Link``の自動生成（後半）](https://qiita.com/HnniTns/items/aed13aa99f7a0310e2b1)

以降は予定です。（早めに上げたいと思います。なお、順番は前後する可能性があります。）

+ 第３回：移動エリアの可・不可・コストの設定
+ 第４回：複数のメッシュによるナビメッシュ生成
+ 第５回：動的なナビメッシュ生成

現状、これ以降は考えていません。（といっても追加するかもしれませんが…）

# そもそも
　この記事を見ている皆様なら、分かっているとは思いますが、念の為に説明をしておきます。
![2021-01-08-14-32-05.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/a2aeafe9-9c3e-b322-40f2-a60e9212be19.gif)
といった感じで、物理的にナビメッシュが接続されていない場所に、始点と終点を任意に設置して「接続」を可能とする機能です。一言で言うと「橋」ですね。

# 目的
　上記にも記述していますが、「段差を一方通行で移動（降りたい）」を目的としています。通常、ゲームでは段差や崖では降りることは出来ますが、登る事が出来ません[^1]。分かり易く言うと、ポケモンの「段差？」が分かり易いと思います。
![段差.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/ef958a82-963f-2784-0868-3e6334e86d1f.jpeg)
　要するに、この事を群衆AIで行いたいわけです。他にも、作品を作成中にこの機能が必要だと思ったのもありますし、RecastNavigationライブラリに自分の手で追加機能を実装したいという目的もあります。
　この機能を実装するにあたっては、群衆エージェントの``Max Climb``の項目をいじれば、ナビメッシュ生成時に高さを上げれることで出来なくもないのですが、これでは登れてしまいます。
![Max Climb.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/d034546f-b712-66d9-7368-a7148a911617.gif)

となると``OffMesh Link``を使う事になると思います。
![OffMeshLink 段差.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/60974180-c601-c909-e713-a0c598d16b5d.gif)
　この通り、希望通りの動きをしてくれるのですが、その為には地形ごとに**毎回**人力で設置しなければならず、更に地形に変更が加わった際には``OffMesh Link``を変更しなければなりません。となると、今後の為にも自動化するべきだと思います。

[^1]: 勿論、ブレスオブザワイルドや原神といった崖を登れるゲームもあります。

# 方法
　ここで紹介する方法はあくまで一例なので、そこだけご了承ください。


　``OffMesh Link``の自動生成については、似たような方法が[このサイト](http://digestingduck.blogspot.com/2011/07/paris-gameai-conference-2011-slides-and.html)の「AIGD11_MikkoMononen_AutoAnnotations.zip」をダウンロードして「paris2011_presentation\bin\slides」フォルダーにある画像で紹介されています。更にサンプルコードもあるのでかなり参考になると思います。紹介するにしても、画像をそのまま載せるのは色々とまずい気がするので、詳しい内容はその画像を参照してください。
　ですが、文字だけだと味気ないので、デモの画像を使って説明します。

## 1. ナビメッシュのエッジを作成
<font color="red">**ナビメッシュを生成している前提で話します**</font>
　今回は``OffMesh Link``の始点を「ナビメッシュのエッジを分割した地点」とします。なのでエッジを計算しなければなりません。ですが、``DetourDebugDraw.cpp``にある``static void drawPolyBoundaries(~)``関数でエッジを計算している箇所があるので、そのコードをベースにすれば問題ありません。
![NavMeshのEdge.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/ae1f1201-e220-9007-e114-48e5f38317e5.png)
　上の画像が計算した結果になっています。といっても、計算で求まるのは赤い縦線だけなのですが、エッジの始点と終点が分かりにくいので、<font color="gold">**黄色い矢印君**</font>を召喚しています。エッジの始点と終点が必要な理由は次の見出しで紹介します。

## 2. ナビメッシュのエッジを分割
　エッジの始点と終点の間にいくつかの分割ポイントを作成し、構築可能な場合に``OffMeshLink``の始点として決定します。
![NavMeshのEdgeの分割点.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/13a3dd70-6506-2785-8a0c-f9dee5cf1011.png)
　上の画像の緑の縦線が分割点になっています。

### 説明
　エッジを分割するのは、``OffMesh Link``があくまで「**ライン**」なので移動するポイントを複数用意しなければならないからです。そのポイントを基準にして``OffMesh Link``を構築していきます。
![NavMeshのEdgeの分割の説明 イラスト.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/42a80545-7111-edb1-a13b-cdf9c5403d00.png)
上から見た図になっています。

+ <font color="blue">**青矢印**</font>：``OffMesh Link``を構築可
+ <font color="Chocolate">**茶矢印**</font>：``OffMesh Link``を構築不可
+ <font color="Chocolate">**茶線**</font>　：ナビメッシュのエッジ
+ <font color="Red">**赤丸**</font>　：エッジの始点・終点
+ **白丸**　：分割点
+ <font color="Gold">**黄矢印**</font>：エッジの始点から終点へのベクトル

このように``OffMesh Link``の終点上にナビメッシュが存在し、障害物等が無い場合に「始点・終点」を確定出来ます。

## 3. 終点を計算し仮リンクを作成する
 ``OffMesh Link``の終点になるであろう場所を決定し、仮リンクとして記録します。ここが一番難しいポイントになります。ですが、ここをクリアーしてしまえば、あとは調整や不要ポイントの削除などを独自に設定して修正する事が可能になります。[^2]
　更にはここの処理をマルチスレッド化する事によって、高速化する事も可能になります。
![仮リンク.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/e539c857-484b-1b27-5032-06250c3fe8ee.png)

[^2]: 例えば、エリアを別で決定して、このエリアは「降りるのみ」にするといったことや、水平上にある別のナビメッシュに対しては無効にするといった事が出来ます。

### 1. 垂直ベクトルを求めポイントを計算
　上記の通りに、エッジの始点から終点へのベクトルの垂直ベクトル（XZ平面上）を求め、分割点から垂直ベクトル方向へ指定する距離分を移動したポイントを求めます。これを<font color="red">**水平上のポイント**</font>とします。
　水平上のポイントまでに地形などが存在するなら、その接触点付近をポイントとして再決定します。ポイントを確定できない状態になれば、その分割点からは``OffMesh Link``は構築不可になります。
![NavMeshの終点計算 水平上のポイント イラスト.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/ef66649a-00a9-5e65-a4d8-6f6fbd263dc7.png)
横から見た図になっています。

+ <font color="blue">**青矢印**</font>　　：垂直ベクトル
+ <font color="Gold">**黄丸**</font>　　　：水平上のポイントを構築可
+ <font color="Gold">**黄丸(点線)**</font> ：水平上のポイントを構築不可
+ <font color="LimeGreen">**茶線**</font>　　　：ナビメッシュ
+ **白丸**</font>　　　：分割点

### 2.ナビメッシュ上のポイントを計算
　分割点付近から直下へのベクトルを求め、地形と直下ベクトル(レイ)の判定を行い、衝突する場合に限りその地点を<font color="red">**垂直上のポイント**</font>として決定します。逆に、一定距離内に地形と衝突しない場合は、**一時的に**構築不可と判断します。
　次に、垂直上のポイントがナビメッシュ上に存在するかを判定し、計算結果を垂直上のポイントとして確定します。その地点は``OffMesh Link``の終点になります。逆に確定出来ない場合は**一時的に**構築不可と判断します。
　なぜ、「構築不可」ではなく「一時的に構築不可」にしたかというと、水平上のポイントまでの距離はあくまでも最大距離なので、短い分には問題ないからです。なので、「[1.垂直ベクトルを求めポイントを計算](#1-垂直ベクトルを求めポイントを計算)」の**垂直ベクトル**方向に一定距離進めます。これを水平上のポイント付近になるまで繰り返し、確定できない場合はその分割点からは仮リンクは構築不可になります。
![NavMeshの終点計算 垂直上のポイント イラスト.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/4273c13b-1da7-5ad6-8a2e-a42969692fd0.png)

---
　なお、垂直ベクトルを構築する際に「**高さ**」を考慮するべきで、高さが異なる地形同士でも双方向通行として処理が出来るからです。所謂「**登れる高さ**」の設定になります。詳細は次回で説明します。
![垂直ベクトルの高さ１.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/4b0ced4e-0aac-f327-264e-52bf56917164.png)
横から見た図になっています。

+ <font color="blue">**青矢印**</font>　　：垂直ベクトル
+ <font color="GreenYellow">**黄緑矢印**</font>　：直下ベクトルを構築可
+ <font color="SandyBrown">**茶矢印**</font>　　：直下ベクトルを構築不可
+ <font color="Gold">**黄丸**</font>　　　：水平上のポイント
+ <font color="Magenta">**紫丸**</font>　　　：垂直上のポイント
+ **白丸**</font>　　　：分割点
+ <font color="LimeGreen">**緑線**</font>　　　：ナビメッシュ
+ <font color="red">**赤線**</font>　　　：垂直ベクトルを構築する時の高さ

# 次回へ続きます
　本当は分けるつもりは無かったのですが、後半の部分も含むとかなりの量になってしまったので、[次回の記事](https://qiita.com/HnniTns/items/aed13aa99f7a0310e2b1)へと分割します。次は「**4. 決定した仮リンクに調整・修正する**」からです。