1 // 2 // Copyright (c) 2009-2010 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 19 #ifndef DETOURNAVMESHQUERY_H 20 #define DETOURNAVMESHQUERY_H 21 22 #include "DetourNavMesh.h" 23 #include "DetourStatus.h" 24 25 26 // Define DT_VIRTUAL_QUERYFILTER if you wish to derive a custom filter from dtQueryFilter. 27 // On certain platforms indirect or virtual function call is expensive. The default 28 // setting is to use non-virtual functions, the actual implementations of the functions 29 // are declared as inline for maximum speed. 30 31 //#define DT_VIRTUAL_QUERYFILTER 1 32 33 /// Defines polygon filtering and traversal costs for navigation mesh query operations. 34 /// @ingroup detour 35 class dtQueryFilter 36 { 37 float m_areaCost[DT_MAX_AREAS]; ///< Cost per area type. (Used by default implementation.) 38 unsigned short m_includeFlags; ///< Flags for polygons that can be visited. (Used by default implementation.) 39 unsigned short m_excludeFlags; ///< Flags for polygons that should not be visted. (Used by default implementation.) 40 41 public: 42 dtQueryFilter(); 43 44 #ifdef DT_VIRTUAL_QUERYFILTER ~dtQueryFilter()45 virtual ~dtQueryFilter() { } 46 #endif 47 48 /// Returns true if the polygon can be visited. (I.e. Is traversable.) 49 /// @param[in] ref The reference id of the polygon test. 50 /// @param[in] tile The tile containing the polygon. 51 /// @param[in] poly The polygon to test. 52 #ifdef DT_VIRTUAL_QUERYFILTER 53 virtual bool passFilter(const dtPolyRef ref, 54 const dtMeshTile* tile, 55 const dtPoly* poly) const; 56 #else 57 bool passFilter(const dtPolyRef ref, 58 const dtMeshTile* tile, 59 const dtPoly* poly) const; 60 #endif 61 62 /// Returns cost to move from the beginning to the end of a line segment 63 /// that is fully contained within a polygon. 64 /// @param[in] pa The start position on the edge of the previous and current polygon. [(x, y, z)] 65 /// @param[in] pb The end position on the edge of the current and next polygon. [(x, y, z)] 66 /// @param[in] prevRef The reference id of the previous polygon. [opt] 67 /// @param[in] prevTile The tile containing the previous polygon. [opt] 68 /// @param[in] prevPoly The previous polygon. [opt] 69 /// @param[in] curRef The reference id of the current polygon. 70 /// @param[in] curTile The tile containing the current polygon. 71 /// @param[in] curPoly The current polygon. 72 /// @param[in] nextRef The refernece id of the next polygon. [opt] 73 /// @param[in] nextTile The tile containing the next polygon. [opt] 74 /// @param[in] nextPoly The next polygon. [opt] 75 #ifdef DT_VIRTUAL_QUERYFILTER 76 virtual float getCost(const float* pa, const float* pb, 77 const dtPolyRef prevRef, const dtMeshTile* prevTile, const dtPoly* prevPoly, 78 const dtPolyRef curRef, const dtMeshTile* curTile, const dtPoly* curPoly, 79 const dtPolyRef nextRef, const dtMeshTile* nextTile, const dtPoly* nextPoly) const; 80 #else 81 float getCost(const float* pa, const float* pb, 82 const dtPolyRef prevRef, const dtMeshTile* prevTile, const dtPoly* prevPoly, 83 const dtPolyRef curRef, const dtMeshTile* curTile, const dtPoly* curPoly, 84 const dtPolyRef nextRef, const dtMeshTile* nextTile, const dtPoly* nextPoly) const; 85 #endif 86 87 /// @name Getters and setters for the default implementation data. 88 ///@{ 89 90 /// Returns the traversal cost of the area. 91 /// @param[in] i The id of the area. 92 /// @returns The traversal cost of the area. getAreaCost(const int i)93 inline float getAreaCost(const int i) const { return m_areaCost[i]; } 94 95 /// Sets the traversal cost of the area. 96 /// @param[in] i The id of the area. 97 /// @param[in] cost The new cost of traversing the area. setAreaCost(const int i,const float cost)98 inline void setAreaCost(const int i, const float cost) { m_areaCost[i] = cost; } 99 100 /// Returns the include flags for the filter. 101 /// Any polygons that include one or more of these flags will be 102 /// included in the operation. getIncludeFlags()103 inline unsigned short getIncludeFlags() const { return m_includeFlags; } 104 105 /// Sets the include flags for the filter. 106 /// @param[in] flags The new flags. setIncludeFlags(const unsigned short flags)107 inline void setIncludeFlags(const unsigned short flags) { m_includeFlags = flags; } 108 109 /// Returns the exclude flags for the filter. 110 /// Any polygons that include one ore more of these flags will be 111 /// excluded from the operation. getExcludeFlags()112 inline unsigned short getExcludeFlags() const { return m_excludeFlags; } 113 114 /// Sets the exclude flags for the filter. 115 /// @param[in] flags The new flags. setExcludeFlags(const unsigned short flags)116 inline void setExcludeFlags(const unsigned short flags) { m_excludeFlags = flags; } 117 118 ///@} 119 120 }; 121 122 /// Provides information about raycast hit 123 /// filled by dtNavMeshQuery::raycast 124 /// @ingroup detour 125 struct dtRaycastHit 126 { 127 /// The hit parameter. (FLT_MAX if no wall hit.) 128 float t; 129 130 /// hitNormal The normal of the nearest wall hit. [(x, y, z)] 131 float hitNormal[3]; 132 133 /// The index of the edge on the final polygon where the wall was hit. 134 int hitEdgeIndex; 135 136 /// Pointer to an array of reference ids of the visited polygons. [opt] 137 dtPolyRef* path; 138 139 /// The number of visited polygons. [opt] 140 int pathCount; 141 142 /// The maximum number of polygons the @p path array can hold. 143 int maxPath; 144 145 /// The cost of the path until hit. 146 float pathCost; 147 }; 148 149 /// Provides custom polygon query behavior. 150 /// Used by dtNavMeshQuery::queryPolygons. 151 /// @ingroup detour 152 class dtPolyQuery 153 { 154 public: ~dtPolyQuery()155 virtual ~dtPolyQuery() { } 156 157 /// Called for each batch of unique polygons touched by the search area in dtNavMeshQuery::queryPolygons. 158 /// This can be called multiple times for a single query. 159 virtual void process(const dtMeshTile* tile, dtPoly** polys, dtPolyRef* refs, int count) = 0; 160 }; 161 162 /// Provides the ability to perform pathfinding related queries against 163 /// a navigation mesh. 164 /// @ingroup detour 165 class dtNavMeshQuery 166 { 167 public: 168 dtNavMeshQuery(); 169 ~dtNavMeshQuery(); 170 171 /// Initializes the query object. 172 /// @param[in] nav Pointer to the dtNavMesh object to use for all queries. 173 /// @param[in] maxNodes Maximum number of search nodes. [Limits: 0 < value <= 65535] 174 /// @returns The status flags for the query. 175 dtStatus init(const dtNavMesh* nav, const int maxNodes); 176 177 /// @name Standard Pathfinding Functions 178 // /@{ 179 180 /// Finds a path from the start polygon to the end polygon. 181 /// @param[in] startRef The refrence id of the start polygon. 182 /// @param[in] endRef The reference id of the end polygon. 183 /// @param[in] startPos A position within the start polygon. [(x, y, z)] 184 /// @param[in] endPos A position within the end polygon. [(x, y, z)] 185 /// @param[in] filter The polygon filter to apply to the query. 186 /// @param[out] path An ordered list of polygon references representing the path. (Start to end.) 187 /// [(polyRef) * @p pathCount] 188 /// @param[out] pathCount The number of polygons returned in the @p path array. 189 /// @param[in] maxPath The maximum number of polygons the @p path array can hold. [Limit: >= 1] 190 dtStatus findPath(dtPolyRef startRef, dtPolyRef endRef, 191 const float* startPos, const float* endPos, 192 const dtQueryFilter* filter, 193 dtPolyRef* path, int* pathCount, const int maxPath) const; 194 195 /// Finds the straight path from the start to the end position within the polygon corridor. 196 /// @param[in] startPos Path start position. [(x, y, z)] 197 /// @param[in] endPos Path end position. [(x, y, z)] 198 /// @param[in] path An array of polygon references that represent the path corridor. 199 /// @param[in] pathSize The number of polygons in the @p path array. 200 /// @param[out] straightPath Points describing the straight path. [(x, y, z) * @p straightPathCount]. 201 /// @param[out] straightPathFlags Flags describing each point. (See: #dtStraightPathFlags) [opt] 202 /// @param[out] straightPathRefs The reference id of the polygon that is being entered at each point. [opt] 203 /// @param[out] straightPathCount The number of points in the straight path. 204 /// @param[in] maxStraightPath The maximum number of points the straight path arrays can hold. [Limit: > 0] 205 /// @param[in] options Query options. (see: #dtStraightPathOptions) 206 /// @returns The status flags for the query. 207 dtStatus findStraightPath(const float* startPos, const float* endPos, 208 const dtPolyRef* path, const int pathSize, 209 float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs, 210 int* straightPathCount, const int maxStraightPath, const int options = 0) const; 211 212 ///@} 213 /// @name Sliced Pathfinding Functions 214 /// Common use case: 215 /// -# Call initSlicedFindPath() to initialize the sliced path query. 216 /// -# Call updateSlicedFindPath() until it returns complete. 217 /// -# Call finalizeSlicedFindPath() to get the path. 218 ///@{ 219 220 /// Intializes a sliced path query. 221 /// @param[in] startRef The refrence id of the start polygon. 222 /// @param[in] endRef The reference id of the end polygon. 223 /// @param[in] startPos A position within the start polygon. [(x, y, z)] 224 /// @param[in] endPos A position within the end polygon. [(x, y, z)] 225 /// @param[in] filter The polygon filter to apply to the query. 226 /// @param[in] options query options (see: #dtFindPathOptions) 227 /// @returns The status flags for the query. 228 dtStatus initSlicedFindPath(dtPolyRef startRef, dtPolyRef endRef, 229 const float* startPos, const float* endPos, 230 const dtQueryFilter* filter, const unsigned int options = 0); 231 232 /// Updates an in-progress sliced path query. 233 /// @param[in] maxIter The maximum number of iterations to perform. 234 /// @param[out] doneIters The actual number of iterations completed. [opt] 235 /// @returns The status flags for the query. 236 dtStatus updateSlicedFindPath(const int maxIter, int* doneIters); 237 238 /// Finalizes and returns the results of a sliced path query. 239 /// @param[out] path An ordered list of polygon references representing the path. (Start to end.) 240 /// [(polyRef) * @p pathCount] 241 /// @param[out] pathCount The number of polygons returned in the @p path array. 242 /// @param[in] maxPath The max number of polygons the path array can hold. [Limit: >= 1] 243 /// @returns The status flags for the query. 244 dtStatus finalizeSlicedFindPath(dtPolyRef* path, int* pathCount, const int maxPath); 245 246 /// Finalizes and returns the results of an incomplete sliced path query, returning the path to the furthest 247 /// polygon on the existing path that was visited during the search. 248 /// @param[in] existing An array of polygon references for the existing path. 249 /// @param[in] existingSize The number of polygon in the @p existing array. 250 /// @param[out] path An ordered list of polygon references representing the path. (Start to end.) 251 /// [(polyRef) * @p pathCount] 252 /// @param[out] pathCount The number of polygons returned in the @p path array. 253 /// @param[in] maxPath The max number of polygons the @p path array can hold. [Limit: >= 1] 254 /// @returns The status flags for the query. 255 dtStatus finalizeSlicedFindPathPartial(const dtPolyRef* existing, const int existingSize, 256 dtPolyRef* path, int* pathCount, const int maxPath); 257 258 ///@} 259 /// @name Dijkstra Search Functions 260 /// @{ 261 262 /// Finds the polygons along the navigation graph that touch the specified circle. 263 /// @param[in] startRef The reference id of the polygon where the search starts. 264 /// @param[in] centerPos The center of the search circle. [(x, y, z)] 265 /// @param[in] radius The radius of the search circle. 266 /// @param[in] filter The polygon filter to apply to the query. 267 /// @param[out] resultRef The reference ids of the polygons touched by the circle. [opt] 268 /// @param[out] resultParent The reference ids of the parent polygons for each result. 269 /// Zero if a result polygon has no parent. [opt] 270 /// @param[out] resultCost The search cost from @p centerPos to the polygon. [opt] 271 /// @param[out] resultCount The number of polygons found. [opt] 272 /// @param[in] maxResult The maximum number of polygons the result arrays can hold. 273 /// @returns The status flags for the query. 274 dtStatus findPolysAroundCircle(dtPolyRef startRef, const float* centerPos, const float radius, 275 const dtQueryFilter* filter, 276 dtPolyRef* resultRef, dtPolyRef* resultParent, float* resultCost, 277 int* resultCount, const int maxResult) const; 278 279 /// Finds the polygons along the naviation graph that touch the specified convex polygon. 280 /// @param[in] startRef The reference id of the polygon where the search starts. 281 /// @param[in] verts The vertices describing the convex polygon. (CCW) 282 /// [(x, y, z) * @p nverts] 283 /// @param[in] nverts The number of vertices in the polygon. 284 /// @param[in] filter The polygon filter to apply to the query. 285 /// @param[out] resultRef The reference ids of the polygons touched by the search polygon. [opt] 286 /// @param[out] resultParent The reference ids of the parent polygons for each result. Zero if a 287 /// result polygon has no parent. [opt] 288 /// @param[out] resultCost The search cost from the centroid point to the polygon. [opt] 289 /// @param[out] resultCount The number of polygons found. 290 /// @param[in] maxResult The maximum number of polygons the result arrays can hold. 291 /// @returns The status flags for the query. 292 dtStatus findPolysAroundShape(dtPolyRef startRef, const float* verts, const int nverts, 293 const dtQueryFilter* filter, 294 dtPolyRef* resultRef, dtPolyRef* resultParent, float* resultCost, 295 int* resultCount, const int maxResult) const; 296 297 /// Gets a path from the explored nodes in the previous search. 298 /// @param[in] endRef The reference id of the end polygon. 299 /// @param[out] path An ordered list of polygon references representing the path. (Start to end.) 300 /// [(polyRef) * @p pathCount] 301 /// @param[out] pathCount The number of polygons returned in the @p path array. 302 /// @param[in] maxPath The maximum number of polygons the @p path array can hold. [Limit: >= 0] 303 /// @returns The status flags. Returns DT_FAILURE | DT_INVALID_PARAM if any parameter is wrong, or if 304 /// @p endRef was not explored in the previous search. Returns DT_SUCCESS | DT_BUFFER_TOO_SMALL 305 /// if @p path cannot contain the entire path. In this case it is filled to capacity with a partial path. 306 /// Otherwise returns DT_SUCCESS. 307 /// @remarks The result of this function depends on the state of the query object. For that reason it should only 308 /// be used immediately after one of the two Dijkstra searches, findPolysAroundCircle or findPolysAroundShape. 309 dtStatus getPathFromDijkstraSearch(dtPolyRef endRef, dtPolyRef* path, int* pathCount, int maxPath) const; 310 311 /// @} 312 /// @name Local Query Functions 313 ///@{ 314 315 /// Finds the polygon nearest to the specified center point. 316 /// [opt] means the specified parameter can be a null pointer, in that case the output parameter will not be set. 317 /// 318 /// @param[in] center The center of the search box. [(x, y, z)] 319 /// @param[in] halfExtents The search distance along each axis. [(x, y, z)] 320 /// @param[in] filter The polygon filter to apply to the query. 321 /// @param[out] nearestRef The reference id of the nearest polygon. Will be set to 0 if no polygon is found. 322 /// @param[out] nearestPt The nearest point on the polygon. Unchanged if no polygon is found. [opt] [(x, y, z)] 323 /// @returns The status flags for the query. 324 dtStatus findNearestPoly(const float* center, const float* halfExtents, 325 const dtQueryFilter* filter, 326 dtPolyRef* nearestRef, float* nearestPt) const; 327 328 /// Finds the polygon nearest to the specified center point. 329 /// [opt] means the specified parameter can be a null pointer, in that case the output parameter will not be set. 330 /// 331 /// @param[in] center The center of the search box. [(x, y, z)] 332 /// @param[in] halfExtents The search distance along each axis. [(x, y, z)] 333 /// @param[in] filter The polygon filter to apply to the query. 334 /// @param[out] nearestRef The reference id of the nearest polygon. Will be set to 0 if no polygon is found. 335 /// @param[out] nearestPt The nearest point on the polygon. Unchanged if no polygon is found. [opt] [(x, y, z)] 336 /// @param[out] isOverPoly Set to true if the point's X/Z coordinate lies inside the polygon, false otherwise. Unchanged if no polygon is found. [opt] 337 /// @returns The status flags for the query. 338 dtStatus findNearestPoly(const float* center, const float* halfExtents, 339 const dtQueryFilter* filter, 340 dtPolyRef* nearestRef, float* nearestPt, bool* isOverPoly) const; 341 342 /// Finds polygons that overlap the search box. 343 /// @param[in] center The center of the search box. [(x, y, z)] 344 /// @param[in] halfExtents The search distance along each axis. [(x, y, z)] 345 /// @param[in] filter The polygon filter to apply to the query. 346 /// @param[out] polys The reference ids of the polygons that overlap the query box. 347 /// @param[out] polyCount The number of polygons in the search result. 348 /// @param[in] maxPolys The maximum number of polygons the search result can hold. 349 /// @returns The status flags for the query. 350 dtStatus queryPolygons(const float* center, const float* halfExtents, 351 const dtQueryFilter* filter, 352 dtPolyRef* polys, int* polyCount, const int maxPolys) const; 353 354 /// Finds polygons that overlap the search box. 355 /// @param[in] center The center of the search box. [(x, y, z)] 356 /// @param[in] halfExtents The search distance along each axis. [(x, y, z)] 357 /// @param[in] filter The polygon filter to apply to the query. 358 /// @param[in] query The query. Polygons found will be batched together and passed to this query. 359 dtStatus queryPolygons(const float* center, const float* halfExtents, 360 const dtQueryFilter* filter, dtPolyQuery* query) const; 361 362 /// Finds the non-overlapping navigation polygons in the local neighbourhood around the center position. 363 /// @param[in] startRef The reference id of the polygon where the search starts. 364 /// @param[in] centerPos The center of the query circle. [(x, y, z)] 365 /// @param[in] radius The radius of the query circle. 366 /// @param[in] filter The polygon filter to apply to the query. 367 /// @param[out] resultRef The reference ids of the polygons touched by the circle. 368 /// @param[out] resultParent The reference ids of the parent polygons for each result. 369 /// Zero if a result polygon has no parent. [opt] 370 /// @param[out] resultCount The number of polygons found. 371 /// @param[in] maxResult The maximum number of polygons the result arrays can hold. 372 /// @returns The status flags for the query. 373 dtStatus findLocalNeighbourhood(dtPolyRef startRef, const float* centerPos, const float radius, 374 const dtQueryFilter* filter, 375 dtPolyRef* resultRef, dtPolyRef* resultParent, 376 int* resultCount, const int maxResult) const; 377 378 /// Moves from the start to the end position constrained to the navigation mesh. 379 /// @param[in] startRef The reference id of the start polygon. 380 /// @param[in] startPos A position of the mover within the start polygon. [(x, y, x)] 381 /// @param[in] endPos The desired end position of the mover. [(x, y, z)] 382 /// @param[in] filter The polygon filter to apply to the query. 383 /// @param[out] resultPos The result position of the mover. [(x, y, z)] 384 /// @param[out] visited The reference ids of the polygons visited during the move. 385 /// @param[out] visitedCount The number of polygons visited during the move. 386 /// @param[in] maxVisitedSize The maximum number of polygons the @p visited array can hold. 387 /// @returns The status flags for the query. 388 dtStatus moveAlongSurface(dtPolyRef startRef, const float* startPos, const float* endPos, 389 const dtQueryFilter* filter, 390 float* resultPos, dtPolyRef* visited, int* visitedCount, const int maxVisitedSize) const; 391 392 /// Casts a 'walkability' ray along the surface of the navigation mesh from 393 /// the start position toward the end position. 394 /// @note A wrapper around raycast(..., RaycastHit*). Retained for backward compatibility. 395 /// @param[in] startRef The reference id of the start polygon. 396 /// @param[in] startPos A position within the start polygon representing 397 /// the start of the ray. [(x, y, z)] 398 /// @param[in] endPos The position to cast the ray toward. [(x, y, z)] 399 /// @param[out] t The hit parameter. (FLT_MAX if no wall hit.) 400 /// @param[out] hitNormal The normal of the nearest wall hit. [(x, y, z)] 401 /// @param[in] filter The polygon filter to apply to the query. 402 /// @param[out] path The reference ids of the visited polygons. [opt] 403 /// @param[out] pathCount The number of visited polygons. [opt] 404 /// @param[in] maxPath The maximum number of polygons the @p path array can hold. 405 /// @returns The status flags for the query. 406 dtStatus raycast(dtPolyRef startRef, const float* startPos, const float* endPos, 407 const dtQueryFilter* filter, 408 float* t, float* hitNormal, dtPolyRef* path, int* pathCount, const int maxPath) const; 409 410 /// Casts a 'walkability' ray along the surface of the navigation mesh from 411 /// the start position toward the end position. 412 /// @param[in] startRef The reference id of the start polygon. 413 /// @param[in] startPos A position within the start polygon representing 414 /// the start of the ray. [(x, y, z)] 415 /// @param[in] endPos The position to cast the ray toward. [(x, y, z)] 416 /// @param[in] filter The polygon filter to apply to the query. 417 /// @param[in] flags govern how the raycast behaves. See dtRaycastOptions 418 /// @param[out] hit Pointer to a raycast hit structure which will be filled by the results. 419 /// @param[in] prevRef parent of start ref. Used during for cost calculation [opt] 420 /// @returns The status flags for the query. 421 dtStatus raycast(dtPolyRef startRef, const float* startPos, const float* endPos, 422 const dtQueryFilter* filter, const unsigned int options, 423 dtRaycastHit* hit, dtPolyRef prevRef = 0) const; 424 425 426 /// Finds the distance from the specified position to the nearest polygon wall. 427 /// @param[in] startRef The reference id of the polygon containing @p centerPos. 428 /// @param[in] centerPos The center of the search circle. [(x, y, z)] 429 /// @param[in] maxRadius The radius of the search circle. 430 /// @param[in] filter The polygon filter to apply to the query. 431 /// @param[out] hitDist The distance to the nearest wall from @p centerPos. 432 /// @param[out] hitPos The nearest position on the wall that was hit. [(x, y, z)] 433 /// @param[out] hitNormal The normalized ray formed from the wall point to the 434 /// source point. [(x, y, z)] 435 /// @returns The status flags for the query. 436 dtStatus findDistanceToWall(dtPolyRef startRef, const float* centerPos, const float maxRadius, 437 const dtQueryFilter* filter, 438 float* hitDist, float* hitPos, float* hitNormal) const; 439 440 /// Returns the segments for the specified polygon, optionally including portals. 441 /// @param[in] ref The reference id of the polygon. 442 /// @param[in] filter The polygon filter to apply to the query. 443 /// @param[out] segmentVerts The segments. [(ax, ay, az, bx, by, bz) * segmentCount] 444 /// @param[out] segmentRefs The reference ids of each segment's neighbor polygon. 445 /// Or zero if the segment is a wall. [opt] [(parentRef) * @p segmentCount] 446 /// @param[out] segmentCount The number of segments returned. 447 /// @param[in] maxSegments The maximum number of segments the result arrays can hold. 448 /// @returns The status flags for the query. 449 dtStatus getPolyWallSegments(dtPolyRef ref, const dtQueryFilter* filter, 450 float* segmentVerts, dtPolyRef* segmentRefs, int* segmentCount, 451 const int maxSegments) const; 452 453 /// Returns random location on navmesh. 454 /// Polygons are chosen weighted by area. The search runs in linear related to number of polygon. 455 /// @param[in] filter The polygon filter to apply to the query. 456 /// @param[in] frand Function returning a random number [0..1). 457 /// @param[out] randomRef The reference id of the random location. 458 /// @param[out] randomPt The random location. 459 /// @returns The status flags for the query. 460 dtStatus findRandomPoint(const dtQueryFilter* filter, float (*frand)(), 461 dtPolyRef* randomRef, float* randomPt) const; 462 463 /// Returns random location on navmesh within the reach of specified location. 464 /// Polygons are chosen weighted by area. The search runs in linear related to number of polygon. 465 /// The location is not exactly constrained by the circle, but it limits the visited polygons. 466 /// @param[in] startRef The reference id of the polygon where the search starts. 467 /// @param[in] centerPos The center of the search circle. [(x, y, z)] 468 /// @param[in] filter The polygon filter to apply to the query. 469 /// @param[in] frand Function returning a random number [0..1). 470 /// @param[out] randomRef The reference id of the random location. 471 /// @param[out] randomPt The random location. [(x, y, z)] 472 /// @returns The status flags for the query. 473 dtStatus findRandomPointAroundCircle(dtPolyRef startRef, const float* centerPos, const float maxRadius, 474 const dtQueryFilter* filter, float (*frand)(), 475 dtPolyRef* randomRef, float* randomPt) const; 476 477 /// Finds the closest point on the specified polygon. 478 /// @param[in] ref The reference id of the polygon. 479 /// @param[in] pos The position to check. [(x, y, z)] 480 /// @param[out] closest The closest point on the polygon. [(x, y, z)] 481 /// @param[out] posOverPoly True of the position is over the polygon. 482 /// @returns The status flags for the query. 483 dtStatus closestPointOnPoly(dtPolyRef ref, const float* pos, float* closest, bool* posOverPoly) const; 484 485 /// Returns a point on the boundary closest to the source point if the source point is outside the 486 /// polygon's xz-bounds. 487 /// @param[in] ref The reference id to the polygon. 488 /// @param[in] pos The position to check. [(x, y, z)] 489 /// @param[out] closest The closest point. [(x, y, z)] 490 /// @returns The status flags for the query. 491 dtStatus closestPointOnPolyBoundary(dtPolyRef ref, const float* pos, float* closest) const; 492 493 /// Gets the height of the polygon at the provided position using the height detail. (Most accurate.) 494 /// @param[in] ref The reference id of the polygon. 495 /// @param[in] pos A position within the xz-bounds of the polygon. [(x, y, z)] 496 /// @param[out] height The height at the surface of the polygon. 497 /// @returns The status flags for the query. 498 dtStatus getPolyHeight(dtPolyRef ref, const float* pos, float* height) const; 499 500 /// @} 501 /// @name Miscellaneous Functions 502 /// @{ 503 504 /// Returns true if the polygon reference is valid and passes the filter restrictions. 505 /// @param[in] ref The polygon reference to check. 506 /// @param[in] filter The filter to apply. 507 bool isValidPolyRef(dtPolyRef ref, const dtQueryFilter* filter) const; 508 509 /// Returns true if the polygon reference is in the closed list. 510 /// @param[in] ref The reference id of the polygon to check. 511 /// @returns True if the polygon is in closed list. 512 bool isInClosedList(dtPolyRef ref) const; 513 514 /// Gets the node pool. 515 /// @returns The node pool. getNodePool()516 class dtNodePool* getNodePool() const { return m_nodePool; } 517 518 /// Gets the navigation mesh the query object is using. 519 /// @return The navigation mesh the query object is using. getAttachedNavMesh()520 const dtNavMesh* getAttachedNavMesh() const { return m_nav; } 521 522 /// @} 523 524 private: 525 // Explicitly disabled copy constructor and copy assignment operator 526 dtNavMeshQuery(const dtNavMeshQuery&); 527 dtNavMeshQuery& operator=(const dtNavMeshQuery&); 528 529 /// Queries polygons within a tile. 530 void queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax, 531 const dtQueryFilter* filter, dtPolyQuery* query) const; 532 533 /// Returns portal points between two polygons. 534 dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float* left, float* right, 535 unsigned char& fromType, unsigned char& toType) const; 536 dtStatus getPortalPoints(dtPolyRef from, const dtPoly* fromPoly, const dtMeshTile* fromTile, 537 dtPolyRef to, const dtPoly* toPoly, const dtMeshTile* toTile, 538 float* left, float* right) const; 539 540 /// Returns edge mid point between two polygons. 541 dtStatus getEdgeMidPoint(dtPolyRef from, dtPolyRef to, float* mid) const; 542 dtStatus getEdgeMidPoint(dtPolyRef from, const dtPoly* fromPoly, const dtMeshTile* fromTile, 543 dtPolyRef to, const dtPoly* toPoly, const dtMeshTile* toTile, 544 float* mid) const; 545 546 // Appends vertex to a straight path 547 dtStatus appendVertex(const float* pos, const unsigned char flags, const dtPolyRef ref, 548 float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs, 549 int* straightPathCount, const int maxStraightPath) const; 550 551 // Appends intermediate portal points to a straight path. 552 dtStatus appendPortals(const int startIdx, const int endIdx, const float* endPos, const dtPolyRef* path, 553 float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs, 554 int* straightPathCount, const int maxStraightPath, const int options) const; 555 556 // Gets the path leading to the specified end node. 557 dtStatus getPathToNode(struct dtNode* endNode, dtPolyRef* path, int* pathCount, int maxPath) const; 558 559 const dtNavMesh* m_nav; ///< Pointer to navmesh data. 560 561 struct dtQueryData 562 { 563 dtStatus status; 564 struct dtNode* lastBestNode; 565 float lastBestNodeCost; 566 dtPolyRef startRef, endRef; 567 float startPos[3], endPos[3]; 568 const dtQueryFilter* filter; 569 unsigned int options; 570 float raycastLimitSqr; 571 }; 572 dtQueryData m_query; ///< Sliced query state. 573 574 class dtNodePool* m_tinyNodePool; ///< Pointer to small node pool. 575 class dtNodePool* m_nodePool; ///< Pointer to node pool. 576 class dtNodeQueue* m_openList; ///< Pointer to open list queue. 577 }; 578 579 /// Allocates a query object using the Detour allocator. 580 /// @return An allocated query object, or null on failure. 581 /// @ingroup detour 582 dtNavMeshQuery* dtAllocNavMeshQuery(); 583 584 /// Frees the specified query object using the Detour allocator. 585 /// @param[in] query A query object allocated using #dtAllocNavMeshQuery 586 /// @ingroup detour 587 void dtFreeNavMeshQuery(dtNavMeshQuery* query); 588 589 #endif // DETOURNAVMESHQUERY_H 590