Unreal Engine 3的Navigation框架
目的
导航这边UE3底层写的满庞杂和细碎的，软件工程做的也并不太好，下面简单写写框架，方便快速抓住系统主干和定位问题。
导航点系统NavigationPoint
存储结构：
NavigationPoint：导航点，整个导航网Graph的Node，属性PathList存储邻接的ReachSpec对象引用
ReachSpec：导航点之间的边，整个导航网Graph的Edge，包含起始Start和终止End导航点引用
ULevel::NavListStart、ULevel::NavListEnd，一个关卡层中的导航点链表起止
UWorld::NavigationOctree，所有可见关卡中的导航点与边信息，全部通过Octree组织
BuildTime相关（根据NavigationPoint形成连通图）:
AScout::DefinePaths()，整个导航点构建过程，形成双向连通图，算法是UE自定的，最终形成的结果是图上所有点互相连通，并且点到点之间只有最短路径的边被保留，地图中多余NavigationPoint被标记出来。
Runtime相关（根据连通图导航）
PathFinding：
生成路径：APawn::GeneratePath()，算法A*，计算结果存在Controller::RouteCache中，是路径中要经过的NavigationPoint列表
UPathConstraint，修改A*的f函数（f=g+h，g是当前cost，h是启发估计消耗）的基类，子类实现可以改变连通图A*时的f函数评估从而支持各种特殊寻路行为，例如Path_AlongLine改变指定直线周围的评估结果、Path_WithinDistanceEnvelope改变特定环行区域内的f评估。
UPathGoalEvaluator，修改A*的目标函数的基类，子类实现用来重定义A*目标。
PathFollowing：
Unreal自带的是FSM + LatentFunction（Controller::MoveTo()），简单而言就是挨个走向PathFinding计算出来的路经点。LatentFunction是UnrealScript在State中带的一个类似协程的概念，方便AI书写。
NavigationMesh相关，导航网格系统：
上图所示的绿色部分，分别是俯视和正常透视的NavigationMesh
存储结构（层级结构）：
世界UWorld
UWorld::NavMeshWorld，所有可见关卡的NavMesh信息汇总，内部通过Octree管理全部的Pylon
世界内一块区域的导航网格APylon
Pylon，标记一个区域内的NavMesh，也是NavMesh在关卡内的对象表征
UNavigationMeshBase* APylon::NavMeshPtr，存储NavMesh（即可行走表面），存储了凸多边形化的关卡地表连通图。如上面图的绿色部分。
UNavigationMeshBase* APylon::ObstacleMesh，存储ObstacleMesh（即可行走表面的边缘），常用来为导航做粗略的碰撞检测、某个点是否直接可达测试。上面图的红色边缘部分。
导航网网格内部结构UNavigationMeshBase
UNavigationMeshBase，导航网格信息，包含以下信息：
TArray<FNavMeshPolyBase> Polys，组成导航网格的凸多边形
TArray<FNavMeshEdgeBase*> EdgePtrs，凸多边形的邻接边信息
FPolyOctreeType* PolyOctree，通过Octree管理的凸多边形，建立在世界原点
NavMeshKDOPTree KDOPTree，凸多边形通过Triangle Fan的形式Triangulate形成的三角形KDOP Tree管理结构
P.S. 上面的Octree和KDOP Tree同时用来实现关于NavMesh的各种碰撞检测和查询接口，接口内优先选择KDOP Tree的Object Space碰撞结构，没有KDOP Tree即选择Octree，个人认为是Octree建立在世界原点而一块NavMesh可能分布在任何地方，Octree碰撞效率并不高的原因。
BuildTime(生成NavMesh，即生成整个可行走平面的凸多边形连通图)：
UE3原带的NavMeshGenerator[1]：至今未找到用哪篇论文实现的，后来也被Epic抛弃了，软件工程方面比较混乱，算法简单描述，引擎内实现再此AScout::GenerateNavMesh()，有兴趣可以去读。
Recast[2]：UE3后期版本和UE4的NavMesh生成算法，源自一个Crysis的程序员做的开源工程，作者尝试了大量生成算法最终自己确定的生成方案，用在了BulletStorm、KillZone3等等很多游戏内。现在GitHub链接中的工程里只有Doxygen生成的API文档，如果想学习推荐critterai[3]的仿写Recast的实现，有详尽的流程讲解和算法问题讨论，还是满好玩的。（算法关键字：体素化、德劳内三角剖分、分水岭算法）。UNavigationMesh::GenerateNavMesh()为调用接口。
下面是一个简单过程，首先是原始的碰撞场景Mesh。
然后Voxcelization体素化整个场景如下所示。
Voxcel过的结果通过Filter标记出来行走平面与平面边界。
根据某个Voxel到边缘的最短距离形成距离场描述。
在距离场应用分水岭算法，形成连通区域。
连通区域边缘从Voxel的锯齿状化简成直线描述，从而形成区域Poly。
全部Poly凸包化形成NavMesh，这个也是传回UE3用于Navigation的部分。
可以看到上面的NavMesh并没有很好的描述可行走平面，NavMesh内部增加采样形成对地表的详尽三角化描述，Recast内叫DetailMesh，用于Recast的Detour（寻路、群体系统）的AI实体行走，如下图所示。
Interface_NavMeshPathObject，接口，其实现用于在BuildTime把一些特殊的边引入NavMesh，例如墙上的梯子、特殊的自定义NavMesh边等等。
Runtime相关（在凸多边形上应用寻路算法）：
PathFinding：
Interface_NavigationHandle，接口，Runtime整个寻路管理器，包含了寻路参数设置、寻路请求管理功能
UNavigationHandle::GeneratePath，A*实现在Graph的搜索，生成结果在UNavigationHandle::PathCache中，是从起始到目标点需要经过的凸多边形邻接边列表
NavMeshPathConstraint 决定某些凸多边形是否可以放入A*的Open表进行测试
PathGoalEvaluator RunTime评估某个目标点是否是Goal
Interface_NavMeshPathObstacle，寻路时动态改变NavMesh的凸多边形原始划分、动态加入障碍物等等
PathSmoothing：
可以看到上面提及A*结果是可行走的邻接边列表，而实际上游戏中AI需要走向某个具体点，这个从边生成目标点过程是用的PathSmoothing方法，UE3里用了一个并不常用的简单String Pulling算法，一般常用Funnel算法处理，两个算法见下面引用[4]
下面简单说说用的最多的Funnel Algorithm：
PathFollowing：
Unreal自带的是FSM + LatentFunction（Controller::MoveTo()），战争机器扩展的AICommand系统，是把FSM封装成类并用栈管理。另外，UE4上层框架全是BehaviorTree的描述框架了，介绍见引用[5]
Crowd人群系统：
这边只是粗略看过，有几点比较有意思：
1、基于Archetype的Behavior系统，自己的项目里由Kevinshan同学参考这个系统结合项目需求做了一个自己的Behavior系统。
2、基于NavMesh的怪物行走PhysNavMeshWalking，用NavMesh这个简化的场景地表描述替换场景碰撞，提高行走CPU效率
3、基于RVO（Reciprocal Velocity Obstacles）的群体避障策略算法，论文原作者[6]的演示很清晰。算法应用了相对速度和相对位置的概念，非常简单的实现了躲避障碍物，还是满有意思的。
引用
[1]Unreal Developer Network, “Navigation mesh reference”, http://udn.epicgames.com/Three/NavigationMeshReference.html
[2] https://github.com/memononen/recastnavigation
[3] http://critterai.org/projects/nmgen_study/
[4] DIRECTION ORIENTED PATHFINDING IN VIDEO GAMES
[5] http://blog.csdn.net/akara/article/details/6084786
[6] http://gamma.cs.unc.edu/RVO/