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

# 初めに
　この記事はOffMesh Linkの自動生成の後半です。見ていない人は[前半の記事](https://qiita.com/HnniTns/items/8189beabbab3fe841ac6)を見て下さい。

# 目次

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

以降は予定です。[^0]

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

[^0]: 近日中に上げたいと思います。※順番は前後する可能性があります。

# 方法
## 4. 決定した仮リンクに調整・修正する
　さて...ここまでくれば、煮るなり焼くなり自由です。仮リンクはこれ以上は増えないので、後はユーザー定義で色々なオプションを付けたりする事で更なる改造・削除が可能になります。とりあえず、今回は

+ <font color="red">仮リンクの被りチェック</font>
+ 「横跳び」の有無の設定

の設定をしようと思います。

### <font color="red">仮リンクの被りチェック</font>
![仮リンク　被り.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/734522f3-ae3e-79c7-a724-804f87613fd9.png "恐らくこのパターンが一番多いと思います。")
　このように、自動生成した際にどうしても被る可能性があるのでその仮リンクの削除を行います。更に、**双方向通行**に設定しなければなりません。
![仮リンク 被り解消.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/b4afeec8-7234-1bcc-b379-06f9d7e85a30.png)
この項目は仮リンクが無駄に多く密集してしまうのを防ぐ為に必須です。

+ <font color="blue">**青矢印**</font>：仮リンク
+ <font color="Magenta">**紫丸**</font>　：垂直上のポイント
+ <font color="LimeGreen">**緑線**</font>　：ナビメッシュ
+ **白丸**</font>　：分割点

---
　ここで、前回の最後に書いた「**垂直ベクトルを構築する際に「高さ」を考慮する**」についての補足をしておきます。上記のように「高さ」を考慮すると今まで「一方通行」だったのが、「双方向通行」になる可能性があります。逆に「高さ」を考慮していないと、「一方通行で登る事が出来ない」や「構築時のレイに当たらず、地形を通り越して構築される」のような事態が発生します。
![垂直ベクトルの高さ２.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/1a4884a5-b628-5dd9-bc7c-31cb970ab360.png)
　この場合だと下の地形側で構築する際に、上に地形があるにもかかわらず、ベクトルが貫通してしまい、結果「**貫通**」する事態に陥ります。なお、上下間の地形にはエージェントが通過できるほどの高さはありません。
![垂直ベクトルの高さ３.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/3e2005a5-9c73-d34f-241f-c14410db3034.png)
　このように「高さ」を考慮する事で、下の地形側で構築する際に「貫通」はしません。

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

上記の仮リンク構築の結果としては下図になります。
![垂直ベクトルの高さ４.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/15b3f676-c018-e860-6551-d978bdd0112e.png)

### 「横跳び」の有無の設定
　この「横跳びの有無」というのは「仮リンクの始点～終点間の高さが指定範囲以内の仮リンクを構築可能にするかどうか」という事です。つまり、水平方向に仮リンクを構築出来ないようにします。ただ、必要な場合もあるので、構築時にフラグで切り替えできるようにしておきます。
![横跳び.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/b32f0d9e-7f54-7881-da8f-47fa91138352.png)

+ <font color="blue">**青矢印**</font>：仮リンクを構築可
+ <font color="Brown">**茶矢印**</font>：仮リンクを構築不可
+ <font color="Magenta">**紫丸**</font>　：垂直上のポイント
+ <font color="LimeGreen">**緑線**</font>　：ナビメッシュ
+ **白丸**</font>　：分割点

## 5. ``OffMesh Link``を作成する
　さて、あとは実際に構築するだけです。
![自動構築完了１.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/dcb07844-4841-883c-44eb-4769d23f52d7.png)
　ただし、ここで注意しなければならない点は「既に自動構築された``OffMesh Link``は削除しなければならない」事です。でないと、何重にも``OffMesh Link``が構築されてしまいます。
　実際に構築するのは任意のタイミングでも構わないと思います。正直、お試しで何度も実際に構築するのは、プログラマーとしては気に入りません。その為の「**仮リンク**」なので...。
![2021-02-08_04-14-33-1-3](https://user-images.githubusercontent.com/52647796/107695456-f2b91280-6cf3-11eb-8c0b-41b71fb17f24.gif)
※ 試しに群衆エージェントを動かしている図です。

# 調整
　実はこれだけでは自動作成自体はいけるのですが、「仮リンクが地形にめり込む」「余計な仮リンクが作成される」「Temp Obstacleを貫通して仮リンクが作成される」などが発生します。なので、その修正を行います。

## 例１ ``Temp Obstacle``を貫通
　``Temp Obstacle``との判定は行っていないので、ここで削除するようにします。
![Temp Obstacleを貫通1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/3ba43f31-15ee-09ce-c328-037ccd1589ce.png "処理前")

## 例２ 双方向通行にならない
これは現状２パターンが存在します。

### 1. 優先順位の関係で不可
　これは、終点を探す過程で手前側から検索している為に発生します。先に下の方にあるナビメッシュにレイが当たり、一方通行になっている状態です。これを解決するには仮リンクの始点・終点で別途確認しなければなりません。
![双方向通行にならない-パターン１-1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/d651a2df-2aa3-4d43-5baf-12731894d611.png)
![双方向通行にならない-パターン１-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/cbee34c8-b269-8816-c1c4-31840d7af669.png)

### 2. 開始地点が存在しない
　これは、一見正常なのですが、空中に浮いているような地形に「ジャンプ」や「崖つかまり」などの場合に必要になります。というのも、仮リンクの終点がナビメッシュのエッジ近くに存在せず、例え登れる高さだとしても、「始点」が無い事には仮リンクを作成する事が不可能だからです。これも、仮リンクの始点・終点で別途確認しなければなりません。
![双方向通行にならない-パターン２-1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/2d941403-3afc-d523-815b-ef079e83b2a2.png)
![双方向通行にならない-パターン２-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/36b1108e-3862-8956-ae73-14b565377dea.png)

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

## 例３ 余計な仮リンクが生成される
![余計なリンク.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/e37f66e3-462c-71b3-f6f7-b51b158439d2.png)
　例えば上図のようなリンクが発生します。このリンクは始点・終点付近のナビメッシュエッジが向き合っておらず、始点のナビメッシュエッジに対し、終点のナビメッシュエッジが90°近くずれている為です。なのでナビメッシュエッジ角度に制限を設定します。

# 追加実装&修正
　これだけでも、出来ているといえば出来ているのですが、人間は欲深いものです。あれやこれやと「追加しろ～」と言われるのは目に見えています。なので、以降は「プラスα」として実装します。

## 自動構築不可エリアの設定
　自動生成で生成出来るのはいいのですが、例えば「家の周囲」など、ある特定の部分を構築したくない場合もあるのでその設定を行います。簡易的なエリアなのでAABBで十分でしょう[^1]。
![自動構築不可エリア.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/4594c7d2-14b2-213f-1c39-f63b28815c50.png)

[^1]: OBBだと計算が面倒くさいとは言ってはいけません。

## 仮リンクが存在するタイルのナビメッシュを自動で再構築する
　これはどうしようもないのですが、``OffMesh Link``が動的でないので、追加したらナビメッシュを再生成する必要があります。なので、``OffMesh Link``付近に存在するタイルのナビメッシュを自動生成するようにします。これを行わないと変更するたびに**全て**のナビメッシュを再構築しなければなりません。
![付近のタイルのナビメッシュを自動生成.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/3abadb9e-121e-dc8a-2660-56dc37d7138e.png)
　この<font color="red">**赤のタイル**</font>のみ再生成します。少しでもナビメッシュの再構築時間を短くする狙いです。

# 最後に
　これで、一旦終わりになります。追加で色々するかもしれませんが、落ち着いてからになると思います。次回は先に「複数のメッシュによるナビメッシュ生成」をしようと思います。