Posted on 2016-11-08 21:14
點點滴滴 閱讀(629)
評論(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是導(dǎo)航系統(tǒng)的主要數(shù)據(jù)模型。用戶只需要創(chuàng)建導(dǎo)航網(wǎng)格數(shù)據(jù)和維護數(shù)據(jù)狀態(tài)。需要使用導(dǎo)航的地方一般是進行尋路操作，偶爾也可以使用navmesh進行一些交互。
Core Class: Navmesh
核心類：Navmesh
The Data Model
數(shù)據(jù)模型
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(片區(qū))
Navmesh的核心概念之一就是Tile。Tiles存放了大多數(shù)的結(jié)構(gòu)信息和狀態(tài)信息。事實上，Navmesh類有點像一個TileManager。Navmesh可以由單個Tile構(gòu)成，也可以向網(wǎng)格一樣的平鋪開來，以便在運行期動態(tài)的替換其中的某個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.
節(jié)點元素
Tile的數(shù)據(jù)結(jié)構(gòu)是一個用于尋路的graph(圖)。它由兩種數(shù)據(jù)結(jié)構(gòu)組成：Polygons(多邊形集合)和off-mesh connections(分離的網(wǎng)格之間的連接關(guān)系集合)。
Off-mesh connections(分離的網(wǎng)格之間的連接關(guān)系集合)可以沒有。它由兩個相互連接的端點構(gòu)成，至少一邊在某個多邊形里。Off-mesh connections作為單獨的邊添加到圖的數(shù)據(jù)結(jié)構(gòu)里。它代表著一種特殊的行走路線，并且不是由原始場景的幾何體生成的。想象一下，一個角色跳過一個欄桿-欄桿可以阻礙普通的前進。
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.
狀態(tài)
Tile包括了一些狀態(tài)信息。狀態(tài)用來區(qū)分不同的Polygons和off-mesh connections。狀態(tài)數(shù)據(jù)包括areas(區(qū)域信息)和flags(標志位)。
Areas(區(qū)域)一般用來定義移動代價的。代價影響尋路。舉個例子，穿越被標記為沼澤的區(qū)域時的代價花費可能比穿越標記為草地的區(qū)域的代價要高。
Flags(標志位)可以用來控制一個節(jié)點的可行走屬性。舉個例子，一個作為'門'的多邊形，在門關(guān)閉的時候，可以給這個多邊形設(shè)置一個特殊的標志位，以表示它是不可通過的?；蛘咴O(shè)置一個特殊的標志位，只允許特定類型的角色通過。
Areas和Flags的意義不是由Navmesh定義的，這非常重要。這些特別指定的數(shù)字都是由導(dǎo)航系認的用戶系統(tǒng)自定義的NavmeshQueryFilter來解釋的。舉個例子：一個過濾器認為ID為5的區(qū)域具有10點路徑代價，而另一個過濾器則認為只有2的路徑代價。當一個關(guān)閉的門的標志位被設(shè)置后(1)，一種過濾器在尋路的時候就會考慮這種情況而將這個門視為不可通過，另外一種過濾器-可能是用于鬼魂的尋路-就會完全忽略這個標志位而將此節(jié)點認為是可通過的。
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...
結(jié)構(gòu)VS狀態(tài)
節(jié)點元素和狀態(tài)之間進行了分離，理解這點非常重要。
首先，這樣它們可以獨立的進行保存和加載。一個通常的情況是，加載一個預(yù)制的Navmesh數(shù)據(jù)后，其中的狀態(tài)可能都是默認值，而利用一個上一次運行時保存的串行化的狀態(tài)緩存，可以覆蓋原始的狀態(tài)信息。
不過這里有一個限制，狀態(tài)信息和節(jié)點自身是精確匹配的。你不能在更改完一個節(jié)點的信息后，又將一個老的狀態(tài)賦給它。
第二點則是對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，最后一點信息是關(guān)于Tile和Polygon的引用這個概念。這些引用是Navmesh為數(shù)不多的數(shù)據(jù)結(jié)構(gòu)之一，而不是由Tile定義的。理解引用是什么很重要，因為通過它可以實現(xiàn)當導(dǎo)航網(wǎng)格發(fā)生變化的時候，一些類似尋路功能的模塊能自動的將引用的多邊形置為無效。
本質(zhì)上來說，Tile和Polygon的引用是一個uint32(無符號整型)。Tile的引用很少被客戶代碼直接使用，因為使用場合基本上都可以被Polygon代替。Navmesh里的每個Polygon的引用都是唯一的，因此它們能夠非常方便的定位到指定的Polygon，而不需要知道這個Polygon屬于哪個Tile。
雖然名字差別比較大，Polygon的引用概念同時也涵蓋了off-mesh connections對象。
引用可以變成無效的。如果在無效之后還使用引用，函數(shù)會返回一個失敗信息。Polygon的引用有效性是基于Tile的引用的。因此當Tile的引用無效了，所有屬于Tile的Polygon的引用也會無效。
構(gòu)造的變化會影響引用的生命周期。改變Navmesh的配置或者Tile的內(nèi)部結(jié)構(gòu)會引起相關(guān)的引用全部失效。
引用會在Tile的狀態(tài)發(fā)生變化的時候進行保存，比如指定Area或Flag值的時候。在運行期動態(tài)的加載或卸載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.
創(chuàng)建一個Navigation Mesh
創(chuàng)建一個Navmesh有一些流程。如果你在使用Unity，那么CAI提供的Unity擴展會讓這件事情稍微簡單點。否則，基本流程如下：
生成打包好的Tile數(shù)據(jù).
使用NMGen生成PolyMesh和PolyMeshDetail。
創(chuàng)建個ConnectionSet(Off-mesh connections的容器)，這是可選的。
將這些數(shù)據(jù)(tile,PolyMesh,PolyMeshDetail,ConnectionSet)加載到NavmeshTileBuildData對象里。
創(chuàng)建一個NavmeshTileDatad數(shù)據(jù)。
現(xiàn)在Tile的構(gòu)成關(guān)系和默認狀態(tài)已經(jīng)都封裝到NavmeshTileData里了，并且為生成Navmesh而做了數(shù)據(jù)結(jié)構(gòu)的改變。
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這個工具函數(shù)提供了一種標準流程。
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.
創(chuàng)建一個Navmesh
如果創(chuàng)建只有個Tile的Navmesh,只需要調(diào)用一次Create(【NavmeshTileBuildData】, Navmesh)函數(shù)。
創(chuàng)建多Tile的Navmesh需要多次調(diào)用函數(shù)。使用Create(【NavmeshParams】, Navmesh)函數(shù)創(chuàng)建一個空的navmesh,然后使用AddTile函數(shù)將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轉(zhuǎn)成二進制數(shù)據(jù)。
它可以每Tile的、狀態(tài)和拓撲結(jié)構(gòu)分離的進行串行化。從mesh里取Tile使用GetTile(Int32)函數(shù)，然后使用GetState(Byte[])函數(shù)和SetState(Byte[])函數(shù)進行狀態(tài)的賦值。
(1)Tile數(shù)據(jù)有自己的生成流程，可以參考An Introduction to NMGen