DetourStatNavMesh.h 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235
  1. //
  2. // Copyright (c) 2009 Mikko Mononen memon@inside.org
  3. //
  4. // This software is provided 'as-is', without any express or implied
  5. // warranty. In no event will the authors be held liable for any damages
  6. // arising from the use of this software.
  7. // Permission is granted to anyone to use this software for any purpose,
  8. // including commercial applications, and to alter it and redistribute it
  9. // freely, subject to the following restrictions:
  10. // 1. The origin of this software must not be misrepresented; you must not
  11. // claim that you wrote the original software. If you use this software
  12. // in a product, an acknowledgment in the product documentation would be
  13. // appreciated but is not required.
  14. // 2. Altered source versions must be plainly marked as such, and must not be
  15. // misrepresented as being the original software.
  16. // 3. This notice may not be removed or altered from any source distribution.
  17. //
  18. #ifndef DETOURSTATNAVMESH_H
  19. #define DETOURSTATNAVMESH_H
  20. // Reference to navigation polygon.
  21. typedef unsigned short dtStatPolyRef;
  22. // Maximum number of vertices per navigation polygon.
  23. static const int DT_STAT_VERTS_PER_POLYGON = 6;
  24. // Structure holding the navigation polygon data.
  25. struct dtStatPoly
  26. {
  27. unsigned short v[DT_STAT_VERTS_PER_POLYGON]; // Indices to vertices of the poly.
  28. dtStatPolyRef n[DT_STAT_VERTS_PER_POLYGON]; // Refs to neighbours of the poly.
  29. unsigned char nv; // Number of vertices.
  30. unsigned char flags; // Flags (not used).
  31. };
  32. struct dtStatPolyDetail
  33. {
  34. unsigned short vbase; // Offset to detail vertex array.
  35. unsigned short nverts; // Number of vertices in the detail mesh.
  36. unsigned short tbase; // Offset to detail triangle array.
  37. unsigned short ntris; // Number of triangles.
  38. };
  39. const int DT_STAT_NAVMESH_MAGIC = (('N'<<24) | ('A'<<16) | ('V'<<8) | 'M');
  40. const int DT_STAT_NAVMESH_VERSION = 3;
  41. struct dtStatBVNode
  42. {
  43. unsigned short bmin[3], bmax[3];
  44. int i;
  45. };
  46. struct dtStatNavMeshHeader
  47. {
  48. int magic;
  49. int version;
  50. int npolys;
  51. int nverts;
  52. int nnodes;
  53. int ndmeshes;
  54. int ndverts;
  55. int ndtris;
  56. float cs;
  57. float bmin[3], bmax[3];
  58. dtStatPoly* polys;
  59. float* verts;
  60. dtStatBVNode* bvtree;
  61. dtStatPolyDetail* dmeshes;
  62. float* dverts;
  63. unsigned char* dtris;
  64. };
  65. class dtStatNavMesh
  66. {
  67. public:
  68. dtStatNavMesh();
  69. ~dtStatNavMesh();
  70. // Initializes the navmesh with data.
  71. // Params:
  72. // data - (in) Pointer to navmesh data.
  73. // dataSize - (in) size of the navmesh data.
  74. // ownsData - (in) Flag indicating if the navmesh should own and delete the data.
  75. bool init(unsigned char* data, int dataSize, bool ownsData);
  76. // Finds the nearest navigation polygon around the center location.
  77. // Params:
  78. // center - (in) The center of the search box.
  79. // extents - (in) The extents of the search box.
  80. // Returns: Reference identifier for the polygon, or 0 if no polygons found.
  81. dtStatPolyRef findNearestPoly(const float* center, const float* extents);
  82. // Returns polygons which touch the query box.
  83. // Params:
  84. // center - (in) the center of the search box.
  85. // extents - (in) the extents of the search box.
  86. // polys - (out) array holding the search result.
  87. // maxPolys - (in) The max number of polygons the polys array can hold.
  88. // Returns: Number of polygons in search result array.
  89. int queryPolygons(const float* center, const float* extents,
  90. dtStatPolyRef* polys, const int maxPolys);
  91. // Finds path from start polygon to end polygon.
  92. // If target polygon canno be reached through the navigation graph,
  93. // the last node on the array is nearest node to the end polygon.
  94. // Params:
  95. // startRef - (in) ref to path start polygon.
  96. // endRef - (in) ref to path end polygon.
  97. // path - (out) array holding the search result.
  98. // maxPathSize - (in) The max number of polygons the path array can hold.
  99. // Returns: Number of polygons in search result array.
  100. int findPath(dtStatPolyRef startRef, dtStatPolyRef endRef,
  101. const float* startPos, const float* endPos,
  102. dtStatPolyRef* path, const int maxPathSize);
  103. // Finds a straight path from start to end locations within the corridor
  104. // described by the path polygons.
  105. // Start and end locations will be clamped on the corridor.
  106. // Params:
  107. // startPos - (in) Path start location.
  108. // endPos - (in) Path end location.
  109. // path - (in) Array of connected polygons describing the corridor.
  110. // pathSize - (in) Number of polygons in path array.
  111. // straightPath - (out) Points describing the straight path.
  112. // maxStraightPathSize - (in) The max number of points the straight path array can hold.
  113. // Returns: Number of points in the path.
  114. int findStraightPath(const float* startPos, const float* endPos,
  115. const dtStatPolyRef* path, const int pathSize,
  116. float* straightPath, const int maxStraightPathSize);
  117. // Finds intersection againts walls starting from start pos.
  118. // Params:
  119. // startRef - (in) ref to the polygon where the start lies.
  120. // startPos - (in) start position of the query.
  121. // endPos - (in) end position of the query.
  122. // t - (out) hit parameter along the segment, 0 if no hit.
  123. // endRef - (out) ref to the last polygon which was processed.
  124. // Returns: Number of polygons in path or 0 if failed.
  125. int raycast(dtStatPolyRef startRef, const float* startPos, const float* endPos,
  126. float& t, dtStatPolyRef* path, const int pathSize);
  127. // Returns distance to nearest wall from the specified location.
  128. // Params:
  129. // centerRef - (in) ref to the polygon where the center lies.
  130. // centerPos - (in) center if the query circle.
  131. // maxRadius - (in) max search radius.
  132. // hitPos - (out) location of the nearest hit.
  133. // hitNormal - (out) normal of the nearest hit.
  134. // Returns: Distance to nearest wall from the test location.
  135. float findDistanceToWall(dtStatPolyRef centerRef, const float* centerPos, float maxRadius,
  136. float* hitPos, float* hitNormal);
  137. // Finds polygons found along the navigation graph which touch the specified circle.
  138. // Params:
  139. // centerRef - (in) ref to the polygon where the center lies.
  140. // centerPos - (in) center if the query circle
  141. // radius - (in) radius of the query circle
  142. // resultRef - (out, opt) refs to the polygons touched by the circle.
  143. // resultParent - (out, opt) parent of each result polygon.
  144. // resultCost - (out, opt) search cost at each result polygon.
  145. // maxResult - (int) maximum capacity of search results.
  146. // Returns: Number of results.
  147. int findPolysAround(dtStatPolyRef centerRef, const float* centerPos, float radius,
  148. dtStatPolyRef* resultRef, dtStatPolyRef* resultParent, float* resultCost,
  149. const int maxResult);
  150. // Returns closest point on navigation polygon.
  151. // Params:
  152. // ref - (in) ref to the polygon.
  153. // pos - (in) the point to check.
  154. // closest - (out) closest point.
  155. // Returns: true if closest point found.
  156. bool closestPointToPoly(dtStatPolyRef ref, const float* pos, float* closest) const;
  157. // Returns height of the polygon at specified location.
  158. // Params:
  159. // ref - (in) ref to the polygon.
  160. // pos - (in) the point where to locate the height.
  161. // height - (out) height at the location.
  162. // Returns: true if oer polygon.
  163. bool getPolyHeight(dtStatPolyRef ref, const float* pos, float* height) const;
  164. // Returns pointer to a polygon based on ref.
  165. const dtStatPoly* getPolyByRef(dtStatPolyRef ref) const;
  166. // Returns polygon index based on ref, or -1 if failed.
  167. int getPolyIndexByRef(dtStatPolyRef ref) const;
  168. // Returns number of navigation polygons.
  169. inline int getPolyCount() const { return m_header ? m_header->npolys : 0; }
  170. // Rerturns pointer to specified navigation polygon.
  171. inline const dtStatPoly* getPoly(int i) const { return &m_header->polys[i]; }
  172. // Returns number of vertices.
  173. inline int getVertexCount() const { return m_header ? m_header->nverts : 0; }
  174. // Returns pointer to specified vertex.
  175. inline const float* getVertex(int i) const { return &m_header->verts[i*3]; }
  176. // Returns number of navigation polygons details.
  177. inline int getPolyDetailCount() const { return m_header ? m_header->ndmeshes : 0; }
  178. // Rerturns pointer to specified navigation polygon detail.
  179. const dtStatPolyDetail* getPolyDetail(int i) const { return &m_header->dmeshes[i]; }
  180. // Returns pointer to specified vertex.
  181. inline const float* getDetailVertex(int i) const { return &m_header->dverts[i*3]; }
  182. // Returns pointer to specified vertex.
  183. inline const unsigned char* getDetailTri(int i) const { return &m_header->dtris[i*4]; }
  184. bool isInClosedList(dtStatPolyRef ref) const;
  185. int getMemUsed() const;
  186. inline unsigned char* getData() const { return m_data; }
  187. inline int getDataSize() const { return m_dataSize; }
  188. inline const dtStatNavMeshHeader* getHeader() const { return m_header; }
  189. inline const dtStatBVNode* getBvTreeNodes() const { return m_header ? m_header->bvtree : 0; }
  190. inline int getBvTreeNodeCount() const { return m_header ? m_header->nnodes : 0; }
  191. private:
  192. // Copies the locations of vertices of a polygon to an array.
  193. int getPolyVerts(dtStatPolyRef ref, float* verts) const;
  194. // Returns portal points between two polygons.
  195. bool getPortalPoints(dtStatPolyRef from, dtStatPolyRef to, float* left, float* right) const;
  196. // Returns edge mid point between two polygons.
  197. bool getEdgeMidPoint(dtStatPolyRef from, dtStatPolyRef to, float* mid) const;
  198. unsigned char* m_data;
  199. int m_dataSize;
  200. dtStatNavMeshHeader* m_header;
  201. class dtNodePool* m_nodePool;
  202. class dtNodeQueue* m_openList;
  203. };
  204. #endif // DETOURSTATNAVMESH_H