最初に
今回は４回目になります。なので、初見の人は第一回を見るようにしてください。といっても、第１～３回とは独立しているので問題ないと思います1。
今後のRecastNavigation記事関係の方針はUnityのナビゲーションシステムと同等もしくはそれ以上の機能を実装していきたいと思っています。
今回の内容は「OffMesh Linkを自動生成する事で、群衆エージェントに段差を一方通行で移動したい」という内容です。Unityの機能としてはこの記事と同等になるかと思います。
目次
- 第１回：
OffMesh Linkの自動生成（前半）（この記事） - 第２回：
OffMesh Linkの自動生成（後半）
以降は予定です。（早めに上げたいと思います。なお、順番は前後する可能性があります。）
- 第３回：移動エリアの可・不可・コストの設定
- 第４回：複数のメッシュによるナビメッシュ生成
- 第５回：動的なナビメッシュ生成
現状、これ以降は考えていません。（といっても追加するかもしれませんが…）
そもそも
この記事を見ている皆様なら、分かっているとは思いますが、念の為に説明をしておきます。
といった感じで、物理的にナビメッシュが接続されていない場所に、始点と終点を任意に設置して「接続」を可能とする機能です。一言で言うと「橋」ですね。
目的
上記にも記述していますが、「段差を一方通行で移動（降りたい）」を目的としています。通常、ゲームでは段差や崖では降りることは出来ますが、登る事が出来ません2。分かり易く言うと、ポケモンの「段差？」が分かり易いと思います。
要するに、この事を群衆AIで行いたいわけです。他にも、作品を作成中にこの機能が必要だと思ったのもありますし、RecastNavigationライブラリに自分の手で追加機能を実装したいという目的もあります。
この機能を実装するにあたっては、群衆エージェントのMax Climbの項目をいじれば、ナビメッシュ生成時に高さを上げれることで出来なくもないのですが、これでは登れてしまいます。
となるとOffMesh Linkを使う事になると思います。
この通り、希望通りの動きをしてくれるのですが、その為には地形ごとに毎回人力で設置しなければならず、更に地形に変更が加わった際にはOffMesh Linkを変更しなければなりません。となると、今後の為にも自動化するべきだと思います。
方法
ここで紹介する方法はあくまで一例なので、そこだけご了承ください。
OffMesh Linkの自動生成については、似たような方法がこのサイトの「AIGD11_MikkoMononen_AutoAnnotations.zip」をダウンロードして「paris2011_presentation\bin\slides」フォルダーにある画像で紹介されています。更にサンプルコードもあるのでかなり参考になると思います。紹介するにしても、画像をそのまま載せるのは色々とまずい気がするので、詳しい内容はその画像を参照してください。
ですが、文字だけだと味気ないので、デモの画像を使って説明します。
1. ナビメッシュのエッジを作成
ナビメッシュを生成している前提で話します
今回はOffMesh Linkの始点を「ナビメッシュのエッジを分割した地点」とします。なのでエッジを計算しなければなりません。ですが、DetourDebugDraw.cppにあるstatic void drawPolyBoundaries(~)関数でエッジを計算している箇所があるので、そのコードをベースにすれば問題ありません。
上の画像が計算した結果になっています。といっても、計算で求まるのは赤い縦線だけなのですが、エッジの始点と終点が分かりにくいので、黄色い矢印君を召喚しています。エッジの始点と終点が必要な理由は次の見出しで紹介します。
2. ナビメッシュのエッジを分割
エッジの始点と終点の間にいくつかの分割ポイントを作成し、構築可能な場合にOffMeshLinkの始点として決定します。
上の画像の緑の縦線が分割点になっています。
説明
エッジを分割するのは、OffMesh Linkがあくまで「ライン」なので移動するポイントを複数用意しなければならないからです。そのポイントを基準にしてOffMesh Linkを構築していきます。
上から見た図になっています。
-
青矢印：
OffMesh Linkを構築可 -
茶矢印：
OffMesh Linkを構築不可 - 茶線 ：ナビメッシュのエッジ
- 赤丸 ：エッジの始点・終点
- 白丸 ：分割点
- 黄矢印：エッジの始点から終点へのベクトル
このようにOffMesh Linkの終点上にナビメッシュが存在し、障害物等が無い場合に「始点・終点」を確定出来ます。
3. 終点を計算し仮リンクを作成する
OffMesh Linkの終点になるであろう場所を決定し、仮リンクとして記録します。ここが一番難しいポイントになります。ですが、ここをクリアーしてしまえば、あとは調整や不要ポイントの削除などを独自に設定して修正する事が可能になります。3
更にはここの処理をマルチスレッド化する事によって、高速化する事も可能になります。
1. 垂直ベクトルを求めポイントを計算
上記の通りに、エッジの始点から終点へのベクトルの垂直ベクトル（XZ平面上）を求め、分割点から垂直ベクトル方向へ指定する距離分を移動したポイントを求めます。これを水平上のポイントとします。
水平上のポイントまでに地形などが存在するなら、その接触点付近をポイントとして再決定します。ポイントを確定できない状態になれば、その分割点からはOffMesh Linkは構築不可になります。
横から見た図になっています。
- 青矢印 ：垂直ベクトル
- 黄丸 ：水平上のポイントを構築可
- 黄丸(点線) ：水平上のポイントを構築不可
- 茶線 ：ナビメッシュ
- 白丸 ：分割点
2.ナビメッシュ上のポイントを計算
分割点付近から直下へのベクトルを求め、地形と直下ベクトル(レイ)の判定を行い、衝突する場合に限りその地点を垂直上のポイントとして決定します。逆に、一定距離内に地形と衝突しない場合は、一時的に構築不可と判断します。
次に、垂直上のポイントがナビメッシュ上に存在するかを判定し、計算結果を垂直上のポイントとして確定します。その地点はOffMesh Linkの終点になります。逆に確定出来ない場合は一時的に構築不可と判断します。
なぜ、「構築不可」ではなく「一時的に構築不可」にしたかというと、水平上のポイントまでの距離はあくまでも最大距離なので、短い分には問題ないからです。なので、「1.垂直ベクトルを求めポイントを計算」の垂直ベクトル方向に一定距離進めます。これを水平上のポイント付近になるまで繰り返し、確定できない場合はその分割点からは仮リンクは構築不可になります。
なお、垂直ベクトルを構築する際に「高さ」を考慮するべきで、高さが異なる地形同士でも双方向通行として処理が出来るからです。所謂「登れる高さ」の設定になります。詳細は次回で説明します。
横から見た図になっています。
- 青矢印 ：垂直ベクトル
- 黄緑矢印 ：直下ベクトルを構築可
- 茶矢印 ：直下ベクトルを構築不可
- 黄丸 ：水平上のポイント
- 紫丸 ：垂直上のポイント
- 白丸 ：分割点
- 緑線 ：ナビメッシュ
- 赤線 ：垂直ベクトルを構築する時の高さ
次回へ続きます
本当は分けるつもりは無かったのですが、後半の部分も含むとかなりの量になってしまったので、次回の記事へと分割します。次は「4. 決定した仮リンクに調整・修正する」からです。