Posted on 2016-11-08 21:14
点点滴滴 阅读(601)
评论(0) 编辑 收藏 引用 所属分类:
19 源码收集
The Navigation Mesh
翻译：kun 2014.12.4
The navigation mesh is the primary data model for the navigation system. The only user component that deals directly with the mesh on a regular basis is the component that is responsible for creating the mesh and managing its state. Normal navigation clients, the one's needing to perform pathfinding and such, rarely if ever interact directly with the navigation mesh.
NavigationMesh是导航系统的主要数据模型。用户只需要创建导航网格数据和维护数据状态。需要使用导航的地方一般是进行寻路操作，偶尔也可以使用navmesh进行一些交互。
Core Class: Navmesh
核心类：Navmesh
The Data Model
数据模型
Tiles
At the core of the navigation mesh is the tile. Tiles hold the vast majority of structural and state information. In fact, the Navmesh class is little more than a tile manager. It may consist of a single tile, or many tiles laid out in a grid that can be swapped in and out at runtime.
The tile based structure of the navigation mesh adds a lot of flexibility. As mentioned, tiles can be swapped in and out at runtime. This means that the mesh can represent a large area, but not all tiles have to be loaded and active, reducing the mesh's memory footprint. This also allows for a situation where individual tiles can be rebuilt without the need to rebuild the entire mesh.
Tiles(片区)
Navmesh的核心概念之一就是Tile。Tiles存放了大多数的结构信息和状态信息。事实上，Navmesh类有点像一个TileManager。Navmesh可以由单个Tile构成，也可以向网格一样的平铺开来，以便在运行期动态的替换其中的某个Tile。
Structural Elements
The tile's structural data is what defines the navigation graph used for pathfinding. It consists of two types of elements: Polygons and off-mesh connections.
The core of the structure is a mesh of convex polygons with between three and MaxAllowedVertsPerPoly vertices. This mesh is in the same format as NMGen's PolyMesh structure, and usually represents an abstraction of a scene's static geometry.
Off-mesh connections are optional. They consist of two connected endpoints, at least one of which resides within a polygon in the polygon mesh. Off-mesh connections are added to the navigation graph as a single edge and represent special travel routes not defined by scene geometry. Think: The route an agent travels if it jumps over a railing that normally blocks movement.
节点元素
Tile的数据结构是一个用于寻路的graph(图)。它由两种数据结构组成：Polygons(多边形集合)和off-mesh connections(分离的网格之间的连接关系集合)。
Off-mesh connections(分离的网格之间的连接关系集合)可以没有。它由两个相互连接的端点构成，至少一边在某个多边形里。Off-mesh connections作为单独的边添加到图的数据结构里。它代表着一种特殊的行走路线，并且不是由原始场景的几何体生成的。想象一下，一个角色跳过一个栏杆-栏杆可以阻碍普通的前进。
State Data
Tiles also contain state data. This data is associated with individual polygons and off-mesh connections. State data includes area and flags.
Areas are used to associate traversal cost to structural elements. This effects pathfinding. For example, the area representing swampland can have a higher cost than the area representing smooth surfaces such as meadowland.
Flags can be used to control when a structural element is traversable. For example, a flag can be set on the polygon below a door to indicate that it is closed and locked. Or a flag can indicate that only agents of a particular type are allowed to traverse the element.
It is important to note that areas and flags have no meaning within the navigation mesh itself. The interpretation of the values is dependant on the NavmeshQueryFilter used by each navigation client. For example: One filter may define a cost of 10 for area id 5, while another may define a cost of 2 for the same area. One flag may be set when a door is closed with one filter checking for the flag during pathfinding, while another filter, used by a ghost, ignores the flag completely.
状态
Tile包括了一些状态信息。状态用来区分不同的Polygons和off-mesh connections。状态数据包括areas(区域信息)和flags(标志位)。
Areas(区域)一般用来定义移动代价的。代价影响寻路。举个例子，穿越被标记为沼泽的区域时的代价花费可能比穿越标记为草地的区域的代价要高。
Flags(标志位)可以用来控制一个节点的可行走属性。举个例子，一个作为'门'的多边形，在门关闭的时候，可以给这个多边形设置一个特殊的标志位，以表示它是不可通过的。或者设置一个特殊的标志位，只允许特定类型的角色通过。
Areas和Flags的意义不是由Navmesh定义的，这非常重要。这些特别指定的数字都是由导航系认的用户系统自定义的NavmeshQueryFilter来解释的。举个例子：一个过滤器认为ID为5的区域具有10点路径代价，而另一个过滤器则认为只有2的路径代价。当一个关闭的门的标志位被设置后(1)，一种过滤器在寻路的时候就会考虑这种情况而将这个门视为不可通过，另外一种过滤器-可能是用于鬼魂的寻路-就会完全忽略这个标志位而将此节点认为是可通过的。
Structure Versus State
Why is it important to know the difference between structural elements and state data?
The first reason is that it is possible to save and load state separately from structure. One common use case is to have a serialized version of the full navigation mesh that represents its default state. Then serialized versions of various states, such as the last runtime state, are used to overwrite the default state as needed.
The main limitation is that a state is only valid for a particular structure. So you can't, for example, save the state, change the tile structure, then load the original state into the new structure.
The second reason for understanding the difference between structure and state has to to with tile and polygon references...
结构VS状态
节点元素和状态之间进行了分离，理解这点非常重要。
首先，这样它们可以独立的进行保存和加载。一个通常的情况是，加载一个预制的Navmesh数据后，其中的状态可能都是默认值，而利用一个上一次运行时保存的串行化的状态缓存，可以覆盖原始的状态信息。
不过这里有一个限制，状态信息和节点自身是精确匹配的。你不能在更改完一个节点的信息后，又将一个老的状态赋给它。
第二点则是对Tile和Polygon的引用方式。
Tile and Polygon References
The last bit of information needed to understand the navigation mesh is the concept of tile and polygon references. These values are one of the few data types that are defined by the navigation mesh rather than the tiles within the mesh. It is important to understand what references are because they are used by various classes to automatically invalidate pathfinding data if the structure of a navigation mesh changes.
Essentially, tile and polygon references are unsigned integer 'handles' to structural elements within a navigation mesh. Tile references are rarely used by navigation clients, while polygon references are all over the place. Polygon references are unique for the navigation mesh, so they are useful for easily identifying a polygon without needing to know which tile it belongs to.
Despite the name, polygon references can refer to a either a polygon or an off-mesh connection.
References can become invalid. If they are used after they are invalidated, then methods will return a failure status. Polygon references are based on the tile reference. So they will be invalidated whenever their associated tile reference is invalidated.
Structural changes govern the life of a reference. Changing the configuration of a navigation mesh or the internal structure of a tile will invalidate all associated references.
References are preserved during tile state changes such as changes flags and areas. They are also preserved during normal runtime loading and unloading of tiles, and during normal serialization/de-serialization of a navigation mesh.
Tile和Polygon的引用方式
要完全理解Navmesh，最后一点信息是关于Tile和Polygon的引用这个概念。这些引用是Navmesh为数不多的数据结构之一，而不是由Tile定义的。理解引用是什么很重要，因为通过它可以实现当导航网格发生变化的时候，一些类似寻路功能的模块能自动的将引用的多边形置为无效。
本质上来说，Tile和Polygon的引用是一个uint32(无符号整型)。Tile的引用很少被客户代码直接使用，因为使用场合基本上都可以被Polygon代替。Navmesh里的每个Polygon的引用都是唯一的，因此它们能够非常方便的定位到指定的Polygon，而不需要知道这个Polygon属于哪个Tile。
虽然名字差别比较大，Polygon的引用概念同时也涵盖了off-mesh connections对象。
引用可以变成无效的。如果在无效之后还使用引用，函数会返回一个失败信息。Polygon的引用有效性是基于Tile的引用的。因此当Tile的引用无效了，所有属于Tile的Polygon的引用也会无效。
构造的变化会影响引用的生命周期。改变Navmesh的配置或者Tile的内部结构会引起相关的引用全部失效。
引用会在Tile的状态发生变化的时候进行保存，比如指定Area或Flag值的时候。在运行期动态的加载或卸载Tile也会使引用自动保存，还有当正常串行化/反串行化一个Navmesh的时候。
Creating a Navigation Mesh
There are various pipelines for creating a navigation mesh. If you are using Unity, the Unity extensions make it easier. Otherwise, the basic steps are as follows:
Generate packed tile data:
Generate PolyMesh and PolyMeshDetail data using NMGen.
Optionally create a ConnectionSet. (Off-mesh connections.)
Load the data into a NavmeshTileBuildData object.
Create a NavmeshTileData object from the build data.
The tile's structure and default state is now locked into a packed data format that is ready to be loaded into a navigation mesh.
创建一个Navigation Mesh
创建一个Navmesh有一些流程。如果你在使用Unity，那么CAI提供的Unity扩展会让这件事情稍微简单点。否则，基本流程如下：
生成打包好的Tile数据.
使用NMGen生成PolyMesh和PolyMeshDetail。
创建个ConnectionSet(Off-mesh connections的容器)，这是可选的。
将这些数据(tile,PolyMesh,PolyMeshDetail,ConnectionSet)加载到NavmeshTileBuildData对象里。
创建一个NavmeshTileDatad数据。
现在Tile的构成关系和默认状态已经都封装到NavmeshTileData里了，并且为生成Navmesh而做了数据结构的改变。
Note Note:
Using the NavmeshTileBuildData class directly can be a bit daunting. The GetBuildData(BuildContext, Int32, Int32, PolyMeshData, PolyMeshDetailData, ConnectionSet, Boolean) utility method provides a standard way of
creating the build data.
注意：
直接使用NavmeshTileBuildData类可能有点难搞。GetBuildData这个工具函数提供了一种标准流程。
Create a navigation mesh:
Single tile navigation meshes are created using the the single step Create(NavmeshTileBuildData, Navmesh) method.
Multi-tile navigation meshes are created then loaded using multiple methods. Use the Create(NavmeshParams, Navmesh) method to initialize an empty mesh. then add tile data using the AddTile(NavmeshTileData, UInt32, UInt32) method.
创建一个Navmesh
如果创建只有个Tile的Navmesh,只需要调用一次Create(【NavmeshTileBuildData】, Navmesh)函数。
创建多Tile的Navmesh需要多次调用函数。使用Create(【NavmeshParams】, Navmesh)函数创建一个空的navmesh,然后使用AddTile函数将Tile添加进去(1)。
Navigation Mesh Serialization
The Navmesh class supports byte serialization using the GetSerializedMesh() method. This saves the entire mesh.
It is possible to serialize state separately from structure on a tile-by-tile basis. Get the tile from the mesh using the GetTile(Int32) method, then use the GetState(Byte[]) and SetState(Byte[]) methods.
Navmesh的串行化
Namvesh类支持二进制串行化，使用GetSerializedMesh来完成。这会将整个mesh转成二进制数据。
它可以每Tile的、状态和拓扑结构分离的进行串行化。从mesh里取Tile使用GetTile(Int32)函数，然后使用GetState(Byte[])函数和SetState(Byte[])函数进行状态的赋值。
(1)Tile数据有自己的生成流程，可以参考An Introduction to NMGen