/// Represents a span in a heightfield.

/// @see rcHeightfield

struct rcSpan

{

	unsigned int smin : RC_SPAN_HEIGHT_BITS; ///< The lower limit of the span. [Limit: < #smax]

	unsigned int smax : RC_SPAN_HEIGHT_BITS; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]

	unsigned int area : 6;                   ///< The area id assigned to the span.

	rcSpan* next;                            ///< The next span higher up in column.

};

/// A memory pool used for quick allocation of spans within a heightfield.

/// @see rcHeightfield

struct rcSpanPool

{

	rcSpanPool* next;					///< The next span pool.

	rcSpan items[RC_SPANS_PER_POOL];	///< Array of spans in the pool.

};

/// A dynamic heightfield representing obstructed space.

/// @ingroup recast

struct rcHeightfield

{

	rcHeightfield();

	~rcHeightfield();

	int width;			///< The width of the heightfield. (Along the x-axis in cell units.)

	int height;			///< The height of the heightfield. (Along the z-axis in cell units.)

	float bmin[3];  	///< The minimum bounds in world space. [(x, y, z)]

	float bmax[3];		///< The maximum bounds in world space. [(x, y, z)]

	float cs;			///< The size of each cell. (On the xz-plane.)

	float ch;			///< The height of each cell. (The minimum increment along the y-axis.)

	rcSpan** spans;		///< Heightfield of spans (width*height).

	rcSpanPool* pools;	///< Linked list of span pools.

	rcSpan* freelist;	///< The next free span.

private:

	// Explicitly-disabled copy constructor and copy assignment operator.

	rcHeightfield(const rcHeightfield&);

	rcHeightfield& operator=(const rcHeightfield&);

};

/// Represents a span of unobstructed space within a compact heightfield.

struct rcCompactSpan

{

	unsigned short y;			///< The lower extent of the span. (Measured from the heightfield's base.)

	unsigned short reg;			///< The id of the region the span belongs to. (Or zero if not in a region.)

	unsigned int con : 24;		///< Packed neighbor connection data.

	unsigned int h : 8;			///< The height of the span.  (Measured from #y.)

};

/// Provides information on the content of a cell column in a compact heightfield. 

struct rcCompactCell

{

	unsigned int index : 24;	///< Index to the first span in the column.

	unsigned int count : 8;		///< Number of spans in the column.

};

/// A compact, static heightfield representing unobstructed space.

/// @ingroup recast

struct rcCompactHeightfield

{

	rcCompactHeightfield();

	~rcCompactHeightfield();

	int width;					///< The width of the heightfield. (Along the x-axis in cell units.)

	int height;					///< The height of the heightfield. (Along the z-axis in cell units.)

	int spanCount;				///< The number of spans in the heightfield.

	int walkableHeight;			///< The walkable height used during the build of the field.  (See: rcConfig::walkableHeight)

	int walkableClimb;			///< The walkable climb used during the build of the field. (See: rcConfig::walkableClimb)

	int borderSize;				///< The AABB border size used during the build of the field. (See: rcConfig::borderSize)

	unsigned short maxDistance;	///< The maximum distance value of any span within the field. 

	unsigned short maxRegions;	///< The maximum region id of any span within the field. 

	float bmin[3];				///< The minimum bounds in world space. [(x, y, z)]

	float bmax[3];				///< The maximum bounds in world space. [(x, y, z)]

	float cs;					///< The size of each cell. (On the xz-plane.)

	float ch;					///< The height of each cell. (The minimum increment along the y-axis.)

	rcCompactCell* cells;		///< Array of cells. [Size: #width*#height]

	rcCompactSpan* spans;		///< Array of spans. [Size: #spanCount]

	unsigned short* dist;		///< Array containing border distance data. [Size: #spanCount]

	unsigned char* areas;		///< Array containing area id data. [Size: #spanCount]

};

struct rcRegion

{

   inline rcRegion(unsigned short i) :

		spanCount(0),

		id(i),

		areaType(0),

		remap(false),

		visited(false),

		overlap(false),

		connectsToBorder(false),

		ymin(0xffff),

		ymax(0)

	{}

	int spanCount;					// Number of spans belonging to this region

	unsigned short id;				// ID of the region

	unsigned char areaType;			// Are type.

	bool remap;

	bool visited;

	bool overlap;

	bool connectsToBorder;			// neighbor is border

	unsigned short ymin, ymax;

	rcIntArray connections;

	rcIntArray floors;

}

struct rcContour

{

	int* verts;			///< Simplified contour vertex and connection data. [Size: 4 * #nverts]

	int nverts;			///< The number of vertices in the simplified contour. 

	int* rverts;		///< Raw contour vertex and connection data. [Size: 4 * #nrverts]

	int nrverts;		///< The number of vertices in the raw contour. 

	unsigned short reg;	///< The region id of the contour.

	unsigned char area;	///< The area id of the contour.

};

struct rcContourSet

{

	rcContourSet();

	~rcContourSet();

	rcContour* conts;	///< An array of the contours in the set. [Size: #nconts]

	int nconts;			///< The number of contours in the set.

	float bmin[3];  	///< The minimum bounds in world space. [(x, y, z)]

	float bmax[3];		///< The maximum bounds in world space. [(x, y, z)]

	float cs;			///< The size of each cell. (On the xz-plane.)

	float ch;			///< The height of each cell. (The minimum increment along the y-axis.)

	int width;			///< The width of the set. (Along the x-axis in cell units.) 

	int height;			///< The height of the set. (Along the z-axis in cell units.) 

	int borderSize;		///< The AABB border size used to generate the source data from which the contours were derived.

	float maxError;		///< The MaxEdgeError that this contour set was simplified with.

};

struct rcContourHole

{

	rcContour* contour;

	int minx, minz, leftmost;

};

struct rcContourRegion

{

	rcContour* outline;

	rcContourHole* holes;

	int nholes;

};

struct rcPotentialDiagonal

{

	int vert;

	int dist;

};

struct rcEdge

{

	unsigned short vert[2];

	unsigned short polyEdge[2];

	unsigned short poly[2];

};

enum SamplePolyFlags

{

	SAMPLE_POLYFLAGS_WALK		= 0x01,		// Ability to walk (ground, grass, road)

	SAMPLE_POLYFLAGS_SWIM		= 0x02,		// Ability to swim (water).

	SAMPLE_POLYFLAGS_DOOR		= 0x04,		// Ability to move through doors.

	SAMPLE_POLYFLAGS_JUMP		= 0x08,		// Ability to jump.

	SAMPLE_POLYFLAGS_DISABLED	= 0x10,		// Disabled polygon

	SAMPLE_POLYFLAGS_ALL		= 0xffff	// All abilities.

};

struct rcPolyMesh

{

	rcPolyMesh();

	~rcPolyMesh();

	unsigned short* verts;	///< The mesh vertices. [Form: (x, y, z) * #nverts]

	unsigned short* polys;	///< Polygon and neighbor data. [Length: #maxpolys * 2 * #nvp]

	unsigned short* regs;	///< The region id assigned to each polygon. [Length: #maxpolys]

	unsigned short* flags;	///< The user defined flags for each polygon. [Length: #maxpolys]

	unsigned char* areas;	///< The area id assigned to each polygon. [Length: #maxpolys]

	int nverts;				///< The number of vertices.

	int npolys;				///< The number of polygons.

	int maxpolys;			///< The number of allocated polygons.

	int nvp;				///< The maximum number of vertices per polygon.

	float bmin[3];			///< The minimum bounds in world space. [(x, y, z)]

	float bmax[3];			///< The maximum bounds in world space. [(x, y, z)]

	float cs;				///< The size of each cell. (On the xz-plane.)

	float ch;				///< The height of each cell. (The minimum increment along the y-axis.)

	int borderSize;			///< The AABB border size used to generate the source data from which the mesh was derived.

	float maxEdgeError;		///< The max error of the polygon edges in the mesh.

};

/// Contains triangle meshes that represent detailed height data associated 

/// with the polygons in its associated polygon mesh object.

/// @ingroup recast

struct rcPolyMeshDetail

{

	unsigned int* meshes;	///< The sub-mesh data. [Size: 4*#nmeshes] 

	float* verts;			///< The mesh vertices. [Size: 3*#nverts] 

	unsigned char* tris;	///< The mesh triangles. [Size: 4*#ntris] 

	int nmeshes;			///< The number of sub-meshes defined by #meshes.

	int nverts;				///< The number of vertices in #verts.

	int ntris;				///< The number of triangles in #tris.

};

struct rcHeightPatch

{

	inline rcHeightPatch() : data(0), xmin(0), ymin(0), width(0), height(0) {}

	inline ~rcHeightPatch() { rcFree(data); }

	unsigned short* data; // all poly xz-plane AABB maxhw,maxhh

	int xmin, ymin, width, height;

};

/// Defines a navigation mesh tile.

/// @ingroup detour

struct dtMeshTile

{

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

	unsigned int linksFreeList;			///< Index to the next free link.

	dtMeshHeader* header;				///< The tile header.

	dtPoly* polys;						///< The tile polygons. [Size: dtMeshHeader::polyCount]

	float* verts;						///< The tile vertices. [Size: dtMeshHeader::vertCount]

	dtLink* links;						///< The tile links. [Size: dtMeshHeader::maxLinkCount]

	dtPolyDetail* detailMeshes;			///< The tile's detail sub-meshes. [Size: dtMeshHeader::detailMeshCount]

	/// The detail mesh's unique vertices. [(x, y, z) * dtMeshHeader::detailVertCount]

	float* detailVerts;	

	/// The detail mesh's triangles. [(vertA, vertB, vertC, triFlags) * dtMeshHeader::detailTriCount].

	/// See dtDetailTriEdgeFlags and dtGetDetailTriEdgeFlags.

	unsigned char* detailTris;	

	/// The tile bounding volume nodes. [Size: dtMeshHeader::bvNodeCount]

	/// (Will be null if bounding volumes are disabled.)

	dtBVNode* bvTree;

	dtOffMeshConnection* offMeshCons;		///< The tile off-mesh connections. [Size: dtMeshHeader::offMeshConCount]

	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;						///< The next free tile, or the next tile in the spatial grid.

};

class dtNavMesh

{

public:

    //...

private:

	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;	///< Dimensions of each tile.

	int m_maxTiles;						///< Max number of tiles.

	int m_tileLutSize;					///< Tile hash lookup size (must be pot).

	int m_tileLutMask;					///< Tile hash lookup mask.

	dtMeshTile** m_posLookup;			///< Tile hash lookup.

	dtMeshTile* m_nextFree;				///< Freelist of tiles.

	dtMeshTile* m_tiles;				///< List of tiles.

}

/// Configuration parameters used to define multi-tile navigation meshes.

/// The values are used to allocate space during the initialization of a navigation mesh.

/// @see dtNavMesh::init()

/// @ingroup detour

struct dtNavMeshParams

{

	float orig[3];					///< The world space origin of the navigation mesh's tile space. [(x, y, z)]

	float tileWidth;				///< The width of each tile. (Along the x-axis.)

	float tileHeight;				///< The height of each tile. (Along the z-axis.)

	int maxTiles;					///< The maximum number of tiles the navigation mesh can contain. This and maxPolys are used to calculate how many bits are needed to identify tiles and polygons uniquely.

	int maxPolys;					///< The maximum number of polygons each tile can contain. This and maxTiles are used to calculate how many bits are needed to identify tiles and polygons uniquely.

};

struct dtNavMeshCreateParams

{

	/// @name Polygon Mesh Attributes

	/// Used to create the base navigation graph.

	/// See #rcPolyMesh for details related to these attributes.

	/// @{

	const unsigned short* verts;			///< The polygon mesh vertices. [(x, y, z) * #vertCount] [Unit: vx]

	int vertCount;							///< The number vertices in the polygon mesh. [Limit: >= 3]

	const unsigned short* polys;			///< The polygon data. [Size: #polyCount * 2 * #nvp]

	const unsigned short* polyFlags;		///< The user defined flags assigned to each polygon. [Size: #polyCount]

	const unsigned char* polyAreas;			///< The user defined area ids assigned to each polygon. [Size: #polyCount]

	int polyCount;							///< Number of polygons in the mesh. [Limit: >= 1]

	int nvp;								///< Number maximum number of vertices per polygon. [Limit: >= 3]

	/// @}

	/// @name Height Detail Attributes (Optional)

	/// See #rcPolyMeshDetail for details related to these attributes.

	/// @{

	const unsigned int* detailMeshes;		///< The height detail sub-mesh data. [Size: 4 * #polyCount]

	const float* detailVerts;				///< The detail mesh vertices. [Size: 3 * #detailVertsCount] [Unit: wu]

	int detailVertsCount;					///< The number of vertices in the detail mesh.

	const unsigned char* detailTris;		///< The detail mesh triangles. [Size: 4 * #detailTriCount]

	int detailTriCount;						///< The number of triangles in the detail mesh.

	/// @}

	/// @name Off-Mesh Connections Attributes (Optional)

	/// Used to define a custom point-to-point edge within the navigation graph, an 

	/// off-mesh connection is a user defined traversable connection made up to two vertices, 

	/// at least one of which resides within a navigation mesh polygon.

	/// @{

	/// Off-mesh connection vertices. [(ax, ay, az, bx, by, bz) * #offMeshConCount] [Unit: wu]

	const float* offMeshConVerts;

	/// Off-mesh connection radii. [Size: #offMeshConCount] [Unit: wu]

	const float* offMeshConRad;

	/// User defined flags assigned to the off-mesh connections. [Size: #offMeshConCount]

	const unsigned short* offMeshConFlags;

	/// User defined area ids assigned to the off-mesh connections. [Size: #offMeshConCount]

	const unsigned char* offMeshConAreas;

	/// The permitted travel direction of the off-mesh connections. [Size: #offMeshConCount]

	///

	/// 0 = Travel only from endpoint A to endpoint B.<br/>

	/// #DT_OFFMESH_CON_BIDIR = Bidirectional travel.

	const unsigned char* offMeshConDir;	

	/// The user defined ids of the off-mesh connection. [Size: #offMeshConCount]

	const unsigned int* offMeshConUserID;

	/// The number of off-mesh connections. [Limit: >= 0]

	int offMeshConCount;

	/// @}

	/// @name Tile Attributes

	/// @note The tile grid/layer data can be left at zero if the destination is a single tile mesh.

	/// @{

	unsigned int userId;	///< The user defined id of the tile.

	int tileX;				///< The tile's x-grid location within the multi-tile destination mesh. (Along the x-axis.)

	int tileY;				///< The tile's y-grid location within the multi-tile desitation mesh. (Along the z-axis.)

	int tileLayer;			///< The tile's layer within the layered destination mesh. [Limit: >= 0] (Along the y-axis.)

	float bmin[3];			///< The minimum bounds of the tile. [(x, y, z)] [Unit: wu]

	float bmax[3];			///< The maximum bounds of the tile. [(x, y, z)] [Unit: wu]

	/// @}

	/// @name General Configuration Attributes

	/// @{

	float walkableHeight;	///< The agent height. [Unit: wu]

	float walkableRadius;	///< The agent radius. [Unit: wu]

	float walkableClimb;	///< The agent maximum traversable ledge. (Up/Down) [Unit: wu]

	float cs;				///< The xz-plane cell size of the polygon mesh. [Limit: > 0] [Unit: wu]

	float ch;				///< The y-axis cell height of the polygon mesh. [Limit: > 0] [Unit: wu]

	/// True if a bounding volume tree should be built for the tile.

	/// @note The BVTree is not normally needed for layered navigation meshes.

	bool buildBvTree;

	/// @}

};

/// Provides high level information related to a dtMeshTile object.

/// @ingroup detour

struct dtMeshHeader

{

	int magic;				///< Tile magic number. (Used to identify the data format.)

	int version;			///< Tile data format version number.

	int x;					///< The x-position of the tile within the dtNavMesh tile grid. (x, y, layer)

	int y;					///< The y-position of the tile within the dtNavMesh tile grid. (x, y, layer)

	int layer;				///< The layer of the tile within the dtNavMesh tile grid. (x, y, layer)

	unsigned int userId;	///< The user defined id of the tile.

	int polyCount;			///< The number of polygons in the tile.

	int vertCount;			///< The number of vertices in the tile.

	int maxLinkCount;		///< The number of allocated links.

	int detailMeshCount;	///< The number of sub-meshes in the detail mesh.

	/// The number of unique vertices in the detail mesh. (In addition to the polygon vertices.)

	int detailVertCount;

	int detailTriCount;			///< The number of triangles in the detail mesh.

	int bvNodeCount;			///< The number of bounding volume nodes. (Zero if bounding volumes are disabled.)

	int offMeshConCount;		///< The number of off-mesh connections.

	int offMeshBase;			///< The index of the first polygon which is an off-mesh connection.

	float walkableHeight;		///< The height of the agents using the tile.

	float walkableRadius;		///< The radius of the agents using the tile.

	float walkableClimb;		///< The maximum climb height of the agents using the tile.

	float bmin[3];				///< The minimum bounds of the tile's AABB. [(x, y, z)]

	float bmax[3];				///< The maximum bounds of the tile's AABB. [(x, y, z)]

	/// The bounding volume quantization factor. 

	float bvQuantFactor;

};

/// Defines a polygon within a dtMeshTile object.

/// @ingroup detour

struct dtPoly

{

	/// Index to first link in linked list. (Or #DT_NULL_LINK if there is no link.)

	unsigned int firstLink;

	/// The indices of the polygon's vertices.

	/// The actual vertices are located in dtMeshTile::verts.

	unsigned short verts[DT_VERTS_PER_POLYGON];

	/// Packed data representing neighbor polygons references and flags for each edge.

	unsigned short neis[DT_VERTS_PER_POLYGON];

	/// The user defined polygon flags.

	unsigned short flags;

	/// The number of vertices in the polygon.

	unsigned char vertCount;

	/// The bit packed area id and polygon type.

	/// @note Use the structure's set and get methods to acess this value.

	unsigned char areaAndtype;

	/// Sets the user defined area id. [Limit: < #DT_MAX_AREAS]

	inline void setArea(unsigned char a) { areaAndtype = (areaAndtype & 0xc0) | (a & 0x3f); }

	/// Sets the polygon type. (See: #dtPolyTypes.)

	inline void setType(unsigned char t) { areaAndtype = (areaAndtype & 0x3f) | (t << 6); }

	/// Gets the user defined area id.

	inline unsigned char getArea() const { return areaAndtype & 0x3f; }

	/// Gets the polygon type. (See: #dtPolyTypes)

	inline unsigned char getType() const { return areaAndtype >> 6; }

};

/// Defines a link between polygons.

/// @note This structure is rarely if ever used by the end user.

/// @see dtMeshTile

struct dtLink

{

	dtPolyRef ref;					///< Neighbour reference. (The neighbor that is linked to.)

	unsigned int next;				///< Index of the next link.

	unsigned char edge;				///< Index of the polygon edge that owns this link.

	unsigned char side;				///< If a boundary link, defines on which side the link is.

	unsigned char bmin;				///< If a boundary link, defines the minimum sub-edge area.

	unsigned char bmax;				///< If a boundary link, defines the maximum sub-edge area.

};

/// Defines the location of detail sub-mesh data within a dtMeshTile.

struct dtPolyDetail

{

	unsigned int vertBase;			///< The offset of the vertices in the dtMeshTile::detailVerts array.

	unsigned int triBase;			///< The offset of the triangles in the dtMeshTile::detailTris array.

	unsigned char vertCount;		///< The number of vertices in the sub-mesh.

	unsigned char triCount;			///< The number of triangles in the sub-mesh.

};

/// Bounding volume node.

/// @note This structure is rarely if ever used by the end user.

/// @see dtMeshTile

struct dtBVNode

{

	unsigned short bmin[3];			///< Minimum bounds of the node's AABB. [(x, y, z)]

	unsigned short bmax[3];			///< Maximum bounds of the node's AABB. [(x, y, z)]

	int i;							///< The node's index. (Negative for escape sequence.)

};

/// Defines an navigation mesh off-mesh connection within a dtMeshTile object.

/// An off-mesh connection is a user defined traversable connection made up to two vertices.

struct dtOffMeshConnection

{

	/// The endpoints of the connection. [(ax, ay, az, bx, by, bz)]

	float pos[6];

	/// The radius of the endpoints. [Limit: >= 0]

	float rad;		

	/// The polygon reference of the connection within the tile.

	unsigned short poly;

	/// Link flags. 

	/// @note These are not the connection's user defined flags. Those are assigned via the 

	/// connection's dtPoly definition. These are link flags used for internal purposes.

	unsigned char flags;

	/// End point side.

	unsigned char side;

	/// The id of the offmesh connection. (User assigned when the navigation mesh is built.)

	unsigned int userId;

};

/// Gets neighbor connection data for the specified direction.

///  @param[in]		s		The span to check.

///  @param[in]		dir		The direction to check. [Limits: 0 <= value < 4]

///  @return The neighbor connection data for the specified direction,

///  	or #RC_NOT_CONNECTED if there is no connection.

/// RC_NOT_CONNECTED == 0X3F

inline int rcGetCon(const rcCompactSpan& s, int dir)

{

	const unsigned int shift = (unsigned int)dir*6;

	return (s.con >> shift) & 0x3f;

}

///dir: 0~4 左前右后

/// 0：x-1

/// 1：z+1

/// 2：x+1

/// 3：z-1

offset[4] = { -1, 1, 1, -1 };