超シンプルナビメッシュを作る
はじめに
ナビゲーションメッシュを１から自作した経験が全くなかったのでナビゲーションメッシュ（以降ナビメッシュと呼ぶ）の自作にチャレンジしてみました。
- はじめに
- 用語について
- 結果
- プロジェクトはこちら
- プロジェクトの使い方
- Blenderを利用してナビメッシュジオメトリを作成する
- ナビメッシュの構築からレベルの移動
- 改良できそうな点
- おわりに
- 参考資料
UE4を利用して作成しましたが、これは「普段自分が使い慣れているツールである」「D&Dでメッシュが即座に表示できる」「デバッグ表示が豊富」「数学系機能も十分」であるためです。いくつかの翻訳作業は必要ですが純粋なOpenGLやDirectXのプロジェクトでも通用する仕組みになっていると思います。
用語について
この記事ではナビメッシュについての用語を以下のように定義しています。
- ナビメッシュジオメトリ
この記事では最初の手順としてDCCツールを用いたゲーム中にナビメッシュとして扱われるモデルを作成するのですが、このDCCツールにてモデリングしたナビメッシュのことを「ナビメッシュジオメトリ」と呼びます。
- ナビメッシュ
ナビメッシュジオメトリを読み込み、ゲーム中のナビメッシュとして機能する状態になったデータのことを「ナビメッシュ」と呼びます。
結果
ブログ用 pic.twitter.com/RSTt1FYAMQ
— PavilionDV7 (@Dv7Pavilion) 2020年6月20日
プロジェクトはこちら
使用ゲームエンジン：Unreal Engine 4 バージョンUE4.25.1
プロジェクトの使い方
プロジェクトを開くと十字型のメッシュが置かれているレベルが表示されます。
右手にあるWorldOutlinerタブの中から「BP_MyOwnNavMeshActor」を選択しDetailsタブにある「Draw Nav Mesh」と書かれたチェックボックスをクリックすると構築したナビメッシュが表示されます。
続いて同じくDetailsタブにあるDebugという項目の下に「Draw Default Path」と「Draw Straight Path」と書かれたチェックボックスがあるのでそれらにチェックを入れます。チェックを入れたら１つ上にある「Search Path」というチェックボックスをクリックすると経路探索の結果が表示されます。
Sample_4_Pレベルは実際にエージェントを構築したナビメッシュを使用して移動するサンプルです。 Playボタンを押すと現在エージェントがいる位置からランダムに選択された位置に向かって経路探索＆移動を行います。エージェントの移動が完了すると再度ランダムに選択された位置に向かって移動を開始します。
新しくナビメッシュジオメトリをモデリングしナビメッシュとして構築する場合はモデリングしたナビメッシュジオメトリが保存されているディレクトリパスとファイル名を設定する必要があります。
Blenderを利用してナビメッシュジオメトリを作成する
今回紹介する超シンプルナビメッシュでは多くのゲームエンジンに搭載されている「自動ナビメッシュ生成」といった便利機能はありません。よってDCCツールを利用してナビメッシュジオメトリをモデリングし、出力したファイルを読み込むことでナビメッシュを構築する仕様になっています。
モデリングするDCCツールはOBJファイルが出力できるものであれば何でも良いです。自分は使い慣れているBlenderを利用してナビメッシュジオメトリをモデリングしました。
モデリングの手順は以下の通りになります。
- レベルジオメトリを作る
- レベルジオメトリからナビメッシュとしたい面を選択し別パーツとする
- ポリゴン数を適切なところまで削減する
ナビメッシュジオメトリ作成手順
DCCツールを利用してモデリングやOBJファイルを出力する際にはいくつかの注意点と制約があります。 注意点は以下の３つです。
- 使用するグラフィックスライブラリによる座標系の差異
OpenGLは右手座標系でありDirectXは左手座標系です。UE4とUnityは両者ともに左手座標系ですが上方向を示す軸が異なります。Blenderでは出力時に前方軸と上方軸を選択できるので使用するグラフィックスライブラリやゲームエンジンに合わせた設定で出力する必要があります。
軸を間違えたナビメッシュ
- 出力時のスケール
UE4では距離の単位が「1cm」とされ、それに対しBlenderは「1m」です。Blenderで10m x 10mの板をモデリングしたとするとUE4にインポートした際には10cm x 10cmと解釈されてしまいます。そのような単位の違いに対応するためにBlenderで出力する際にはスケールを100倍する必要があります。
UnityではBlenderと同様に距離の単位は「1m」なので特に意識してスケールする必要はありません。OpenGLやDirectXではプロジェクトごとに想定する単位が異なるため注意したほうが良いでしょう。
スケールを間違えたナビメッシュ
- 頂点数は破綻しない程度に減らす
モデリングするときは下地となるレベルジオメトリがあるはずです。レベルジオメトリの上面だけを取り出してナビメッシュとすることも出来ますがそれでは解像度が高すぎて余計な負荷を生み出してしまうのである程度レベルに沿った粗いものに修正するべきです。UE4やUnityを使っている方は自動で生成されるナビメッシュの解像度を見てみることをおすすめします。レベルジオメトリと比べて非常に粗い物となっていることがわかります。
Blenderの場合、Decimateモディファイアというポリゴン数削減のための機能がありますので破綻の無い程度にポリゴン数を減らしておいたほうが良いでしょう。
ポリゴン数の削減を行ったナビメッシュ
続いて制約についてですが、ここで述べられる制約は主にUE4に対して課されるものでありUE4以外で動作させる場合には特に意識する必要の無いものもあります。
- スケールは100倍
注意点で説明したとおりUE4では単位が「1cm」なので1mを想定したメッシュがUE4では1cmと解釈されものすごく小さくなります。この問題を回避するため、出力時にはスケールを100倍にする必要があります。
- Forwardを「X Forward」、Upを「Z Up」にする
UE4ではX軸が前後方向を表し、Z軸が上下方向を表す独自のものとなっているので、この差異を吸収するために出力時には前方の軸と上方の軸を改めて設定します。UnityやOpenGL、DirectXでは都度設定を変更する必要があるかもしれません。
- 「Write Normals」、「Include UVs」、「Write Materials」のチェックを外す
BlenderではOBJファイルに含める情報を選択することができます。デフォルトでは挙げた「Write Normals」「Include UVs」「Write Materials」にチェックが入っていますがナビメッシュでは３つ全て不要なのでチェックを外します。これにより若干のデータ量削減と読み込み処理の単純化が出来ます。
- 面は必ず三角ポリゴン
プロジェクトのナビメッシュやOBJファイル読み込み処理は三角ポリゴンであることを前提とした処理が組まれており、四角ポリゴンを三角ポリゴンに変換するような事もしません。よってナビメッシュは 必ず三角形化 する必要があります。
BlenderではOBJファイル出力時の設定で「Triangulate Faces」のチェックを入れるか「Triangulateモディファイア」を適用することで三角形化することが出来ます。
ナビメッシュの構築からレベルの移動
ここからはUnreal C++を利用したプログラム部分を説明していきます。
ナビメッシュを利用してレベルを移動するまでには以下の手順を踏む必要があります。
- OBJファイルの読み込み
- ナビゲーションセルの作成
- 隣接するナビゲーションセルへのリンク
- 経路探索
- 得られた経路の整形
- 移動
OBJファイルの読み込み
OBJファイルを読み込むのはMyOwnNavMeshLoaderクラスの役割です。このクラスは読み込むOBJファイルのフルパスを渡すと参照型の引数に頂点バッファとインデックスバッファを渡します。ここの実装はUE4のエンジンソースにあるnDisplayプラグインにあるOutputRemapMeshクラスを参考にしました。
void MyOwnNavMeshLoader::CreateNavMeshDataFromOBJ(FString FullPathFileName, TArray<FVector>& NavMeshVertices, TArray<TArray<int32>>& NavMeshIndices) { if (FPaths::FileExists(FullPathFileName)) { TArray<FString> TextData; if (FFileHelper::LoadANSITextFileToStrings(*FullPathFileName, nullptr, TextData)) { for (FString Line : TextData) { Line.TrimStartAndEndInline(); // 「v 」から始まる行（これは頂点座標を表す） if (Line.StartsWith(TEXT("v "))) { TArray<FString> ParseData; if (Line.ParseIntoArray(ParseData, TEXT(" ")) == 4) { float X = FCString::Atof(*ParseData[1]); float Y = FCString::Atof(*ParseData[2]); float Z = FCString::Atof(*ParseData[3]); NavMeshVertices.Add(FVector(X, Y, Z)); } } // 「f 」から始まる行（これは頂点インデックスを表す） if (Line.StartsWith(TEXT("f "))) { TArray<FString> ParseData; if (Line.ParseIntoArray(ParseData, TEXT(" ")) == 4) { int32 A = (FCString::Atoi(*ParseData[1]) - 1); int32 B = (FCString::Atoi(*ParseData[2]) - 1); int32 C = (FCString::Atoi(*ParseData[3]) - 1); NavMeshIndices.Add(TArray<int32>{A, B, C}); } } } } } }
UE4を利用しない方についてはGitHubや個人ブログにOBJファイル読み込みを実装しているリポジトリがたくさんあるためそちらを参考にすることをおすすめします。自分がザッと調べてみた中では以下のプロジェクトがかなり単純でわかりやすかったです。
GitHub - tek-nishi/Obj-loader-samples: Wavefront OBJ file loader with GLFW and C++
ナビゲーションセルの作成
MyOwnNavMeshLoaderクラスによって手に入れた頂点バッファとインデックスバッファを利用してナビゲーションセルを作成します。ここの処理はOpenGLやDirectXで簡単なポリゴン描画をされたことがある方なら既視感のある部分だと思います。ナビゲーションセルの作成処理はAMyOwnNavMeshActorクラスのCreateNavMeshDataFromOBJ関数が行います。
// OBJファイルからナビメッシュデータを読み込み、頂点座標配列と頂点インデックス配列を取得する MyOwnNavMeshLoader NavMeshLoader; NavMeshLoader.CreateNavMeshDataFromOBJ(NavMeshDataDirectoryPath + NavMeshFileName, NavMeshVertices, NavMeshIndices); NavMeshCells.Empty(); // 得たデータからNavMeshCellを作成 for (int32 I = 0; I < NavMeshIndices.Num(); ++I) { const FVector& VertA = NavMeshVertices[NavMeshIndices[I][0]] * NavMeshScale; const FVector& VertB = NavMeshVertices[NavMeshIndices[I][1]] * NavMeshScale; const FVector& VertC = NavMeshVertices[NavMeshIndices[I][2]] * NavMeshScale; NavMeshCells.Add(MakeShared<MyOwnNavMeshCell>(this, I, VertA, VertB, VertC)); }
newされたMyOwnNavMeshCellクラスのコンストラクタは以下の処理になっています。
MyOwnNavMeshCell::MyOwnNavMeshCell(const AMyOwnNavMeshActor* NavMeshActor, int32 InCellID, const FVector& PointA, const FVector& PointB, const FVector& PointC) : CellID(InCellID) , NavMeshRef(NavMeshActor) { Vertices.SetNum(3); Edges.SetNum(3); Link.SetNum(3); Vertices[(uint8)ECellVert::VERT_A] = PointA; Vertices[(uint8)ECellVert::VERT_B] = PointB; Vertices[(uint8)ECellVert::VERT_C] = PointC; Edges[(uint8)ECellSide::SIDE_AB] = FCellEdge(PointA, PointB); Edges[(uint8)ECellSide::SIDE_BC] = FCellEdge(PointB, PointC); Edges[(uint8)ECellSide::SIDE_CA] = FCellEdge(PointC, PointA); Link[(uint8)ECellSide::SIDE_AB] = INDEX_NONE; Link[(uint8)ECellSide::SIDE_BC] = INDEX_NONE; Link[(uint8)ECellSide::SIDE_CA] = INDEX_NONE; Center = (PointA + PointB + PointC) / 3.f; Normal = FVector::CrossProduct((PointB - PointA), (PointC - PointA)); Normal.Normalize(); CellPlane = FPlane(PointA, Normal); CellPlane.Normalize(); }
FCellEdge構造体は文字通りナビゲーションセルを構成するエッジのことです。FCellEdgeにはLeft、Rightという２つの座標を保持しており常に左から右方向へと頂点座標が指定されます。よってナビゲーションセルは右回りが表と扱われます。
ナビゲーションセルの法線を表すNormalや平面を表すCellPlaneはある地点から最も近いナビゲーションセルを見つける時やナビメッシュを利用した移動時に活躍します。法線を持つことで上下に重なるセルがあったとしても正しく望ましい最近セルを見つけることが出来、平面情報によってある地点から垂直にセルに下ろしたときの地点（つまりその地点でのセルの高さ）を得ることが出来ます。セルの高さを得られるようになることでナビメッシュで移動するエージェントが確実にセルの上に立つことができるようになります。
ナビゲーションセルをリンクする
経路探索時に近傍セルを探す手間を省くため初期化処理時点であるセルから見た近傍セルを見つけておきます。この作業はAMyOwnNavMeshActorクラスのLinkCells関数で行われます。リンク作業が完了するとBlenderで作成したナビメッシュは立派なナビメッシュデータとしてゲーム内で活躍することになります。
近傍セルを見つける方法は、取り出したセルとそれ以外のセルを順次照らし合わせ取り出したセルの辺ABが未だリンクしているセルがなく、それ以外のセルとのリンクが可能であるかを確認します。無事に条件を満たしたセル同士は対応する辺方向へのリンク先セルを記録します。これを３辺全て行います。
void AMyOwnNavMeshActor::LinkCells() { // 調査対象のセルとリンク候補セルとの共有辺の有無を調べ共有辺が存在した場合にはリンクする for (auto Current : NavMeshCells) { for (auto Other : NavMeshCells) { if (Current == Other || Current->AlreadyLinkCell(Other->GetCellID())) continue; if (Current->ValidLinkCount() == 3) break; MyOwnNavMeshCell::ECellSide Side; // Currentセルは辺AB側にリンクしているセルが無い かつ // Otherセルは辺AB側でCurrentセルとのリンクが可能である if (Current->GetLink(MyOwnNavMeshCell::ECellSide::SIDE_AB) == INDEX_NONE && Other->CheckSharedEdge(Current->GetEdge(MyOwnNavMeshCell::ECellSide::SIDE_AB), Current->GetCellID(), Side)) { Current->SetLink(MyOwnNavMeshCell::ECellSide::SIDE_AB, Other->GetCellID()); Other->SetLink(Side, Current->GetCellID()); continue; } // ~~~ 各辺に続く ~~~ } } }
CheckSharedEdge関数では調査対象のセルとの共有辺の有無を調べます。共有辺の有無を調べる方法は単純です。引数で与えられたEdgeのLeftと自身のセルを構成する各頂点の座標とを比較し、等しければ続いてEdgeのRightと他２点の頂点との座標を比較します。EdgeのLeft、Rightと合致する頂点があれば合致した辺方向と見つけたことを表すTRUEを返します。
bool MyOwnNavMeshCell::CheckSharedEdge(const FCellEdge& Edge, int32 Other, ECellSide& SideType) { // Edgeの始端と終端と自身の頂点位置とを照らし合わせ該当した辺方向にセルを記録する if (Vertices[(uint8)ECellVert::VERT_A] == Edge.Left) { if (Vertices[(uint8)ECellVert::VERT_B] == Edge.Right) { SideType = ECellSide::SIDE_AB; return true; } else if (Vertices[(uint8)ECellVert::VERT_C] == Edge.Right) { SideType = ECellSide::SIDE_CA; return true; } } // ~~~ 各辺に続く ~~~ return false; }
ここまででOBJファイルからナビゲーションセルを作成しナビゲーションセル同士を接続したことでナビメッシュを無事構築することが出来ました。UE4でプロジェクトを開いている方はWorld OutlinerにあるBP_MyOwnNavMeshActorを選択しDetailsタブにあるDrawNavMeshチェックボックスを押すとこれまで説明した３工程を経たナビメッシュが描画されます。
作成されたナビメッシュ
ナビメッシュを使って経路探索
経路探索はMyOwnNavMeshPathfinderクラスによって実行されます。経路探索は馴染み深いA＊アルゴリズムです。ナビメッシュだからといって特別にA*アルゴリズムをカスタマイズするということはありません。ネットに多くある擬似コードやサンプルをそのまま適用出来ます。
bool MyOwnNavMeshPathfinder::FindPath(MyOwnNavMeshPath& NavPath, int32 StartCellIndex, const FVector& StartPos, int32 GoalCellIndex, const FVector& EndPos) { TSharedPtr<FNavNode> Current = nullptr; TArray<TSharedPtr<FNavNode>> Open, Close; TSharedPtr<FNavNode> StartNode = MakeShared<FNavNode>(GoalCellIndex); StartNode->GCost = 0.f; Open.HeapPush(StartNode, FNavNodePredecator()); int32 LoopCount = 0; INT_MAX; const int32 LoopLimit = 1000000; while (Open.Num() || LoopCount < LoopLimit) { LoopCount++; Open.HeapPop(Current, FNavNodePredecator()); if (Current->CellIndex == StartCellIndex) break; Close.Add(Current); auto CurrentCell = NavMeshRef->GetNavMeshCells()[Current->CellIndex]; for (int32 NeighborIndex : CurrentCell->GetNeighbor()) { TSharedPtr<FNavNode> NeighborNode = MakeShared<FNavNode>(NeighborIndex); bool ContainsInCloseList = Close.ContainsByPredicate([&](const TSharedPtr<FNavNode> Lhs) { return Lhs->CellIndex == NeighborNode->CellIndex; }); if (NeighborIndex == INDEX_NONE || ContainsInCloseList) continue; auto NeighborCell = NavMeshRef->GetNavMeshCells()[NeighborNode->CellIndex]; float TotalCost = Current->GCost + FVector::DistSquared(CurrentCell->GetCenter(), NeighborCell->GetCenter()); bool ContainsInOpenList = Open.ContainsByPredicate([&](const TSharedPtr<FNavNode> Lhs) { return Lhs->CellIndex == NeighborNode->CellIndex; }); if (ContainsInOpenList) { if (TotalCost < NeighborNode->GCost) { NeighborNode->Parent = Current; NeighborNode->GCost = TotalCost; } } else { NeighborNode->Parent = Current; NeighborNode->GCost = TotalCost; NeighborNode->HCost = CalcHeuristic(NeighborCell->GetCenter(), EndPos); Open.HeapPush(NeighborNode, FNavNodePredecator()); Open.Heapify(FNavNodePredecator()); } } } if (LoopCount >= LoopLimit) return false; // パスが見つかった NavPath.AddWaypoint(StartPos); while (Current->Parent != nullptr) { auto CurrentCell = NavMeshRef->GetNavMeshCells()[Current->CellIndex]; auto ParentCell = NavMeshRef->GetNavMeshCells()[Current->Parent->CellIndex]; NavPath.AddWaypoint(CurrentCell, ParentCell); Current = Current->Parent; } NavPath.AddWaypoint(EndPos); return true; }
通過するセルの中心を通るギザギザとした経路
求めた経路をきれいに整形する
求まった経路はギザギザしており大変見栄えが悪いため出来るだけ真っ直ぐな経路へと修正する必要があります。求まった経路の中で必ず必要なウェイポイントは曲がり角に該当するウェイポイントですので、曲がり角に該当しない位置にあるウェイポイントというのは全て不要なウェイポイントと言えます。
求まった経路から不要なウェイポイントを取り除き真っ直ぐな経路に整形する仕組みをString Pullingと呼びます。String Pullingで最も有名なアルゴリズムにSimple Stupid Funnel Algorithm（略してFunnel Algorithm）があります。Funnel Algorithmについては以下の記事をオススメします。図を多く用いて解説されているので非常にわかりやすいです。
【Unity】3次元でのFunnelアルゴリズム - Qiita
このFunnel Algorithmはオープンソースのナビメッシュプロジェクトで有名なRecast Navigationの著者であるMikko Mononen氏のブログが初出だと思われます。
Digesting Duck: Simple Stupid Funnel Algorithm
Recast NavigationのString PullingにもFunnel Algorithmが利用されています。Recast Navigationでは離れたセルとの接続を可能にするOff-mesh Link機能があるため若干複雑にはなっていますが概ねMikko Mononen氏が紹介するコードと同じです。UE4のナビゲーションシステムもベースにRecast Navigationが用いられているのでString Pullingにて同じコードが確認出来ます。
recastnavigation/DetourNavMeshQuery.cpp at master · recastnavigation/recastnavigation · GitHub
プロジェクトではFunnel AlgorithmをMyOwnNavMeshPathクラスのGetStraightPath関数で実装しています。GetStraightPath関数の引数にCornerOffsetRatioというfloat型の引数がありますが、これは曲がり角に該当するウェイポイントをどれほどの割合で壁から離すかを決定します。0.0fでは両端のいずれかの壁にピッタリと沿うようなウェイポイントになり、0.5fではエッジの中心あたりにウェイポイントが設定されます。
この実装はGuerrilla GamesのBeyond Killzone: Creating New AI Systems for Horizon Zero Dawnというスライドを参考にしました。（54ページから）
Beyond Killzone: Creating New AI Systems for Horizon Zero Dawn
Funnel Algorithmにより最適化された経路
セルの中心を通る経路（赤線）とFunnel Algorithm適用後の経路（緑線）の比較
ナビメッシュで移動する
エージェントがナビメッシュを利用して移動する際には常にナビメッシュに立った状態で無ければいけません。単に得られたウェイポイントへ移動するだけでは途中にある凸凹な地形を無視してしまうからです。
凸凹な地形に沿った移動をするにはエージェントの足元にあるナビゲーションセルを取得し平面と線分の交点を求めてエージェントをその高さにスナップしてあげる必要があります。これらの処理はUMyOwnNavMeshMovementComponentクラスのTickComponent関数で実装されています。
void UMyOwnNavMeshMovementComponent::TickComponent(float DeltaTime, ELevelTick TickType, FActorComponentTickFunction* ThisTickFunction) { Super::TickComponent(DeltaTime, TickType, ThisTickFunction); if (!bNavMeshWalking) return; FVector TargetWaypoint = ResultPath[CurrentWaypointIndex]; // 1フレームごとの移動ベクトルを計算 FVector DesiredMovementThisFrame = (TargetWaypoint - GetOwnerFootLocation()).GetClampedToMaxSize(1.0f) * DeltaTime * MaxSpeed; if (!DesiredMovementThisFrame.IsNearlyZero()) { // 移動先 FVector NewLocation = GetOwner()->GetActorLocation() + DesiredMovementThisFrame; // 移動先へと向かう回転 FRotator DesiredRotate = UKismetMathLibrary::FindLookAtRotation(GetOwnerFootLocation(), NewLocation); DesiredRotate.Roll = 0.f; DesiredRotate.Pitch = 0.f; // RInterpTo で少しづつDesiredRotateへ回転させる GetOwner()->SetActorRotation(FMath::RInterpTo(GetOwner()->GetActorRotation(), DesiredRotate, DeltaTime, TurnRate)); // ClosestCellにスナップする const TSharedPtr<MyOwnNavMeshCell> ClosestCell = NavMeshRef->FindClosestCell(GetOwnerFootLocation(), true); if (ClosestCell == nullptr) { UE_LOG(LogTemp, Error, TEXT("ERROR: Couldn't find the closest cell to NewLocation")); return; } FVector SnapPoint = ClosestCell->ProjectPoint(GetOwnerFootLocation()); NewLocation.Z = SnapPoint.Z + PawnOwnerHeight; // 移動 GetOwner()->SetActorLocation(NewLocation); } // ~~ 移動先に到達したときの処理 ~~ }
足元にあるナビゲーションセルの高さを求める際に移動先の座標ではなく移動前の座標を使っています。このようにした理由は単に見栄えが良いからです。平面の地形であれば移動先の座標を使っても問題はありませんがスロープの途中だと移動前と移動先の高さの差分だけエージェントが浮いているように見えてしまいます。10cm地面から浮いているより、10cm地面に埋まっている、もしくはつま先が埋まっている方が自然です。
改良できそうな点
ここまででナビメッシュの生成とナビメッシュを利用した移動について説明をしました。しかしこのプロジェクトは超シンプルというだけあって必要最低限の機能しかありません。そこでいくつかこのプロジェクトの改良できそうな点を紹介します。
- 最近セルの検索
ある地点から最も近いナビゲーションセルを探すFindClosestCell関数は線形探索のため必ず全てのナビゲーションセルとの比較処理を実行しなければなりません。プロジェクトの中で最も多くナビゲーションセルを持つデータでも77個（ポリゴン数を削減していない）なので問題にはなりませんがお尻がムズムズする方も多いと思います。
このような問題を解決するには空間分割が最適です。単純なものとしてはkd木があり、GitHubや個人ブログにてたくさん紹介されていますので実装難易度は低いと思います。より3Dに特化したものとしてオクツリーもあります。
- ナビメッシュでの移動時の軌道
エージェントの軌道を確認してみるとウェイポイントからウェイポイントへの移動が非常に鋭く曲がってしまっています。エージェントは次のウェイポイントへゆっくりと時間をかけて振り向くため一見違和感無く見えますがよく見るとカニ歩きのような状態になっています。実際の人間が曲がり角を曲がるときは外側に膨らみつつ曲がります。角度を付けずにゆったりと曲がるようにするためにはスプライン曲線を使うと良いでしょう。
更に簡単な方法として移動時の計算を少し変更する方法もあります。現在は次のウェイポイントへ向かう方向ベクトルを求め移動速度でスケールしエージェントの座標に新しくセットしています。これを常にエージェントが向いている方向を移動速度でスケールしエージェントの座標に新しくセットしエージェントを回転させることで任意の方向に曲げるようにすると自然と滑らかな軌道になります。
文字だけだと理解が難しいと思いますのでこれを解説した記事を紹介します。
- ナビメッシュの自動生成
ナビメッシュを扱えるエンジンは恐らく全てナビメッシュを自動生成するようになっているはずです。ナビメッシュの自動生成についてはそれだけで巨大なトピックのため今回は真っ先に実装を見送りました。しかしナビメッシュの自動生成について解説するブログや資料はいくつかあるので紹介しておきます。
The High Level Process | CritterAI
おわりに
自分はナビメッシュのシステムを自分で構築したことが無かったため今回挑戦してみることにしました。自動生成についてはかなり困難な道のりになってしまうことがわかっていたので心が折れて放り出してしまうよりはバサッと切り捨ててBlenderでナビメッシュをモデリングする方法を取りました。
ここで紹介したナビメッシュはゲームエンジンに搭載されているそれと比べるとかなり融通の利かないものですが、何らかの理由でゲームエンジンを使わずにゲームを作っている方には有用ではないかと思います。
参考資料
Game Programming Gems | Mark DeLoura, 川西 裕幸, 狩野 智英 |本 | 通販 | Amazon
3.6 ナビゲーションメッシュによる3D移動とパスの発見の単純化 Greg Snook
Digesting Duck: Simple Stupid Funnel Algorithm
Mikko Mononen氏によるFunnel Algorithmの解説（英語）
【Unity】3次元でのFunnelアルゴリズム - Qiita
skanmera氏によるFunnel Algorithmの解説（日本語）
Navigation Meshes and Pathfinding - Artificial Intelligence - Tutorials - GameDev.net
Funnel Algorithmの解説（英語）。String Pullingの由来についても解説されている。
The High Level Process | CritterAI
ナビメッシュについての勉強を目的とした個人プロジェクト。ナビメッシュの自動生成手順について詳細な説明がある。
