Detour 学习记录之零：总览

序

施工中…

Recast 负责构建导航网格，而根据导航网格进行寻路就是 Detour 要做的事情了。

这篇文章主要讲一下 detour 的代码结构，navmesh 和 tile 如何组织，poly link 是什么关系，navmeshquery 和 queryfilter 是什么用途一类的东西。

dtNavMesh: 主要是对 tile 的管理
    dtNavMeshParams
    dtMeshTile

dtMeshTile:
    dtMeshHeader
    dtPoly                  tile 内所有的多边形
    dtLink                  tile 内所有多边形的邻接信息
    verts                   tile 内的所有顶点坐标
    dtPolyDetail            tile 内的细节网格
    detailVerts             细节网格顶点坐标
    detailTris              细节网格三角形顶点序号
    dtBVNode                bvTree
    dtOffMeshConnection    
    dtMeshTile              空闲链表

dtPoly
    verts                   顶点在 dtMeshTile::verts 中的序号
    
dtLink

dtFindNearestPolyQuery
dtCollectPolysQuery

在 Detour 中，导航网格的数据结构就是 dtNavMesh，一个 dtNavMesh 就代表了一张地图上的一个导航网格实例。

class dtNavMesh {
    // ...
    dtNavMeshParams m_params;           //< Current initialization params. TODO: do not store this info twice.
    float m_orig[3];                    //< Origin of the tile (0,0)
    float m_tileWidth, m_tileHeight;    // tile 的长宽
    int m_maxTiles;                     // 导航网格内的最大 tile 数量
    int m_tileLutSize;                  // tile 哈希表大小（必须为 2 的幂）
    int m_tileLutMask;                  // tile 查找时所用的掩码

    dtMeshTile** m_posLookup;           // tile 哈希表
    dtMeshTile* m_nextFree;             // 空闲 tile 链表
    dtMeshTile* m_tiles;                // 使用中的 tile 数组
    // ...
};

struct dtMeshTile
{
    unsigned int salt;                  ///< Counter describing modifications to the tile.

    unsigned int linksFreeList;         // 指向 links 数组中的第一个未使用位置
    dtMeshHeader* header;               // header 数据
    dtPoly* polys;                      // tile 内的多边形数组
    float* verts;                       // tile 内的所有顶点坐标数组
    dtLink* links;                      // tile 内的所有邻接信息数组

    dtPolyDetail* detailMeshes;         // tile 对应的细节网格
    float* detailVerts;    
    unsigned char* detailTris;    

    dtBVNode* bvTree;                   // tile 内的 bvh 树

    dtOffMeshConnection* offMeshCons;   // off-mesh connections

    unsigned char* data;                ///< The tile data. (Not directly accessed under normal situations.)
    int dataSize;                       ///< Size of the tile data.
    int flags;                          ///< Tile flags. (See: #dtTileFlags)
    dtMeshTile* next;                   // 当 tile 不在使用中时，指向下一个空闲 tile；
                                        // 当 tile 在使用中时，指向垂直方向上的下一个 tile
    // ...
};

struct dtPoly
{
    unsigned int firstLink;             // 多边形的第一条边的邻接信息在 dtMeshTile::links 数组中的序号

	/// The indices of the polygon's vertices.
	/// The actual vertices are located in dtMeshTile::verts.
	unsigned short verts[DT_VERTS_PER_POLYGON]; // 多边形顶点在 dtMeshTile::verts 数组中的序号

	/// Packed data representing neighbor polygons references and flags for each edge.
	unsigned short neis[DT_VERTS_PER_POLYGON];  // 多边形每条边的邻接信息，低 8 位存储方向（0~7）
	unsigned short flags;                       // 用户自定义的多边形标记
	unsigned char vertCount;                    // 多边形顶点数量
	unsigned char areaAndtype;                  // 高 2 位存储多边形类型，低 6 位存储 area id
                                                // 目前多边形类型只有两种：普通多边形、offmesh 多边形
};