TrinityCore
dtNavMeshQuery Class Reference

#include <DetourNavMeshQuery.h>

Classes

struct  dtQueryData
 

Public Member Functions

 dtNavMeshQuery ()
 
 ~dtNavMeshQuery ()
 
dtStatus init (const dtNavMesh *nav, const int maxNodes)
 
Standard Pathfinding Functions
dtStatus findPath (dtPolyRef startRef, dtPolyRef endRef, const float *startPos, const float *endPos, const dtQueryFilter *filter, dtPolyRef *path, int *pathCount, const int maxPath) const
 
dtStatus findStraightPath (const float *startPos, const float *endPos, const dtPolyRef *path, const int pathSize, float *straightPath, unsigned char *straightPathFlags, dtPolyRef *straightPathRefs, int *straightPathCount, const int maxStraightPath, const int options=0) const
 
Sliced Pathfinding Functions

Common use case:

  1. Call initSlicedFindPath() to initialize the sliced path query.
  2. Call updateSlicedFindPath() until it returns complete.
  3. Call finalizeSlicedFindPath() to get the path.
dtStatus initSlicedFindPath (dtPolyRef startRef, dtPolyRef endRef, const float *startPos, const float *endPos, const dtQueryFilter *filter, const unsigned int options=0)
 
dtStatus updateSlicedFindPath (const int maxIter, int *doneIters)
 
dtStatus finalizeSlicedFindPath (dtPolyRef *path, int *pathCount, const int maxPath)
 
dtStatus finalizeSlicedFindPathPartial (const dtPolyRef *existing, const int existingSize, dtPolyRef *path, int *pathCount, const int maxPath)
 
Dijkstra Search Functions
dtStatus findPolysAroundCircle (dtPolyRef startRef, const float *centerPos, const float radius, const dtQueryFilter *filter, dtPolyRef *resultRef, dtPolyRef *resultParent, float *resultCost, int *resultCount, const int maxResult) const
 
dtStatus findPolysAroundShape (dtPolyRef startRef, const float *verts, const int nverts, const dtQueryFilter *filter, dtPolyRef *resultRef, dtPolyRef *resultParent, float *resultCost, int *resultCount, const int maxResult) const
 
dtStatus getPathFromDijkstraSearch (dtPolyRef endRef, dtPolyRef *path, int *pathCount, int maxPath) const
 
Local Query Functions
dtStatus findNearestPoly (const float *center, const float *halfExtents, const dtQueryFilter *filter, dtPolyRef *nearestRef, float *nearestPt) const
 
dtStatus queryPolygons (const float *center, const float *halfExtents, const dtQueryFilter *filter, dtPolyRef *polys, int *polyCount, const int maxPolys) const
 
dtStatus queryPolygons (const float *center, const float *halfExtents, const dtQueryFilter *filter, dtPolyQuery *query) const
 
dtStatus findLocalNeighbourhood (dtPolyRef startRef, const float *centerPos, const float radius, const dtQueryFilter *filter, dtPolyRef *resultRef, dtPolyRef *resultParent, int *resultCount, const int maxResult) const
 
dtStatus moveAlongSurface (dtPolyRef startRef, const float *startPos, const float *endPos, const dtQueryFilter *filter, float *resultPos, dtPolyRef *visited, int *visitedCount, const int maxVisitedSize) const
 
dtStatus raycast (dtPolyRef startRef, const float *startPos, const float *endPos, const dtQueryFilter *filter, float *t, float *hitNormal, dtPolyRef *path, int *pathCount, const int maxPath) const
 
dtStatus raycast (dtPolyRef startRef, const float *startPos, const float *endPos, const dtQueryFilter *filter, const unsigned int options, dtRaycastHit *hit, dtPolyRef prevRef=0) const
 
dtStatus findDistanceToWall (dtPolyRef startRef, const float *centerPos, const float maxRadius, const dtQueryFilter *filter, float *hitDist, float *hitPos, float *hitNormal) const
 
dtStatus getPolyWallSegments (dtPolyRef ref, const dtQueryFilter *filter, float *segmentVerts, dtPolyRef *segmentRefs, int *segmentCount, const int maxSegments) const
 
dtStatus findRandomPoint (const dtQueryFilter *filter, float(*frand)(), dtPolyRef *randomRef, float *randomPt) const
 
dtStatus findRandomPointAroundCircle (dtPolyRef startRef, const float *centerPos, const float maxRadius, const dtQueryFilter *filter, float(*frand)(), dtPolyRef *randomRef, float *randomPt) const
 
dtStatus closestPointOnPoly (dtPolyRef ref, const float *pos, float *closest, bool *posOverPoly) const
 
dtStatus closestPointOnPolyBoundary (dtPolyRef ref, const float *pos, float *closest) const
 
dtStatus getPolyHeight (dtPolyRef ref, const float *pos, float *height) const
 
Miscellaneous Functions
bool isValidPolyRef (dtPolyRef ref, const dtQueryFilter *filter) const
 
bool isInClosedList (dtPolyRef ref) const
 
class dtNodePoolgetNodePool () const
 
const dtNavMeshgetAttachedNavMesh () const
 

Private Member Functions

 dtNavMeshQuery (const dtNavMeshQuery &)
 
dtNavMeshQueryoperator= (const dtNavMeshQuery &)
 
void queryPolygonsInTile (const dtMeshTile *tile, const float *qmin, const float *qmax, const dtQueryFilter *filter, dtPolyQuery *query) const
 Queries polygons within a tile. More...
 
dtStatus getPortalPoints (dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
 Returns portal points between two polygons. More...
 
dtStatus getPortalPoints (dtPolyRef from, const dtPoly *fromPoly, const dtMeshTile *fromTile, dtPolyRef to, const dtPoly *toPoly, const dtMeshTile *toTile, float *left, float *right) const
 
dtStatus getEdgeMidPoint (dtPolyRef from, dtPolyRef to, float *mid) const
 Returns edge mid point between two polygons. More...
 
dtStatus getEdgeMidPoint (dtPolyRef from, const dtPoly *fromPoly, const dtMeshTile *fromTile, dtPolyRef to, const dtPoly *toPoly, const dtMeshTile *toTile, float *mid) const
 
dtStatus appendVertex (const float *pos, const unsigned char flags, const dtPolyRef ref, float *straightPath, unsigned char *straightPathFlags, dtPolyRef *straightPathRefs, int *straightPathCount, const int maxStraightPath) const
 
dtStatus appendPortals (const int startIdx, const int endIdx, const float *endPos, const dtPolyRef *path, float *straightPath, unsigned char *straightPathFlags, dtPolyRef *straightPathRefs, int *straightPathCount, const int maxStraightPath, const int options) const
 
dtStatus getPathToNode (struct dtNode *endNode, dtPolyRef *path, int *pathCount, int maxPath) const
 

Private Attributes

const dtNavMeshm_nav
 Pointer to navmesh data. More...
 
dtQueryData m_query
 Sliced query state. More...
 
class dtNodePoolm_tinyNodePool
 Pointer to small node pool. More...
 
class dtNodePoolm_nodePool
 Pointer to node pool. More...
 
class dtNodeQueuem_openList
 Pointer to open list queue. More...
 

Detailed Description

Provides the ability to perform pathfinding related queries against a navigation mesh.

For methods that support undersized buffers, if the buffer is too small to hold the entire result set the return status of the method will include the DT_BUFFER_TOO_SMALL flag.

Constant member functions can be used by multiple clients without side effects. (E.g. No change to the closed list. No impact on an in-progress sliced path query. Etc.)

Walls and portals: A wall is a polygon segment that is considered impassable. A portal is a passable segment between polygons. A portal may be treated as a wall based on the dtQueryFilter used for a query.

See also
dtNavMesh, dtQueryFilter, dtAllocNavMeshQuery(), dtAllocNavMeshQuery()

Constructor & Destructor Documentation

◆ dtNavMeshQuery() [1/2]

dtNavMeshQuery::dtNavMeshQuery ( )
138  :
139  m_nav(0),
140  m_tinyNodePool(0),
141  m_nodePool(0),
142  m_openList(0)
143 {
144  memset(&m_query, 0, sizeof(dtQueryData));
145 }
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:560
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
dtQueryData m_query
Sliced query state.
Definition: DetourNavMeshQuery.h:558

◆ ~dtNavMeshQuery()

dtNavMeshQuery::~dtNavMeshQuery ( )
148 {
149  if (m_tinyNodePool)
151  if (m_nodePool)
153  if (m_openList)
158 }
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
~dtNodeQueue()
Definition: DetourNode.cpp:167
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
~dtNodePool()
Definition: DetourNode.cpp:76
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:560
void dtFree(void *ptr)
Definition: DetourAlloc.cpp:46
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ dtNavMeshQuery() [2/2]

dtNavMeshQuery::dtNavMeshQuery ( const dtNavMeshQuery )
private

Member Function Documentation

◆ appendPortals()

dtStatus dtNavMeshQuery::appendPortals ( const int  startIdx,
const int  endIdx,
const float *  endPos,
const dtPolyRef path,
float *  straightPath,
unsigned char *  straightPathFlags,
dtPolyRef straightPathRefs,
int *  straightPathCount,
const int  maxStraightPath,
const int  options 
) const
private
1756 {
1757  const float* startPos = &straightPath[(*straightPathCount-1)*3];
1758  // Append or update last vertex
1759  dtStatus stat = 0;
1760  for (int i = startIdx; i < endIdx; i++)
1761  {
1762  // Calculate portal
1763  const dtPolyRef from = path[i];
1764  const dtMeshTile* fromTile = 0;
1765  const dtPoly* fromPoly = 0;
1766  if (dtStatusFailed(m_nav->getTileAndPolyByRef(from, &fromTile, &fromPoly)))
1767  return DT_FAILURE | DT_INVALID_PARAM;
1768 
1769  const dtPolyRef to = path[i+1];
1770  const dtMeshTile* toTile = 0;
1771  const dtPoly* toPoly = 0;
1772  if (dtStatusFailed(m_nav->getTileAndPolyByRef(to, &toTile, &toPoly)))
1773  return DT_FAILURE | DT_INVALID_PARAM;
1774 
1775  float left[3], right[3];
1776  if (dtStatusFailed(getPortalPoints(from, fromPoly, fromTile, to, toPoly, toTile, left, right)))
1777  break;
1778 
1779  if (options & DT_STRAIGHTPATH_AREA_CROSSINGS)
1780  {
1781  // Skip intersection if only area crossings are requested.
1782  if (fromPoly->getArea() == toPoly->getArea())
1783  continue;
1784  }
1785 
1786  // Append intersection
1787  float s,t;
1788  if (dtIntersectSegSeg2D(startPos, endPos, left, right, s, t))
1789  {
1790  float pt[3];
1791  dtVlerp(pt, left,right, t);
1792 
1793  stat = appendVertex(pt, 0, path[i+1],
1794  straightPath, straightPathFlags, straightPathRefs,
1795  straightPathCount, maxStraightPath);
1796  if (stat != DT_IN_PROGRESS)
1797  return stat;
1798  }
1799  }
1800  return DT_IN_PROGRESS;
1801 }
unsigned char getArea() const
Gets the user defined area id.
Definition: DetourNavMesh.h:191
dtStatus appendVertex(const float *pos, const unsigned char flags, const dtPolyRef ref, float *straightPath, unsigned char *straightPathFlags, dtPolyRef *straightPathRefs, int *straightPathCount, const int maxStraightPath) const
Definition: DetourNavMeshQuery.cpp:1716
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1128
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
Definition: DetourNavMesh.h:162
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
bool left(const int *a, const int *b, const int *c)
Definition: RecastContour.cpp:487
bool dtIntersectSegSeg2D(const float *ap, const float *aq, const float *bp, const float *bq, float &s, float &t)
Definition: DetourCommon.cpp:374
Add a vertex at every polygon edge crossing where area changes.
Definition: DetourNavMesh.h:128
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
Definition: DetourNavMesh.h:288
static const unsigned int DT_IN_PROGRESS
Definition: DetourStatus.h:27
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ appendVertex()

dtStatus dtNavMeshQuery::appendVertex ( const float *  pos,
const unsigned char  flags,
const dtPolyRef  ref,
float *  straightPath,
unsigned char *  straightPathFlags,
dtPolyRef straightPathRefs,
int *  straightPathCount,
const int  maxStraightPath 
) const
private
1719 {
1720  if ((*straightPathCount) > 0 && dtVequal(&straightPath[((*straightPathCount)-1)*3], pos))
1721  {
1722  // The vertices are equal, update flags and poly.
1723  if (straightPathFlags)
1724  straightPathFlags[(*straightPathCount)-1] = flags;
1725  if (straightPathRefs)
1726  straightPathRefs[(*straightPathCount)-1] = ref;
1727  }
1728  else
1729  {
1730  // Append new vertex.
1731  dtVcopy(&straightPath[(*straightPathCount)*3], pos);
1732  if (straightPathFlags)
1733  straightPathFlags[(*straightPathCount)] = flags;
1734  if (straightPathRefs)
1735  straightPathRefs[(*straightPathCount)] = ref;
1736  (*straightPathCount)++;
1737 
1738  // If there is no space to append more vertices, return.
1739  if ((*straightPathCount) >= maxStraightPath)
1740  {
1742  }
1743 
1744  // If reached end of path, return.
1745  if (flags == DT_STRAIGHTPATH_END)
1746  {
1747  return DT_SUCCESS;
1748  }
1749  }
1750  return DT_IN_PROGRESS;
1751 }
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
The vertex is the end position in the path.
Definition: DetourNavMesh.h:121
bool dtVequal(const float *p0, const float *p1)
Definition: DetourCommon.h:279
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
uint8 flags
Definition: DisableMgr.cpp:47
static const unsigned int DT_IN_PROGRESS
Definition: DetourStatus.h:27
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ closestPointOnPoly()

dtStatus dtNavMeshQuery::closestPointOnPoly ( dtPolyRef  ref,
const float *  pos,
float *  closest,
bool posOverPoly 
) const

Finds the closest point on the specified polygon.

Parameters
[in]refThe reference id of the polygon.
[in]posThe position to check. [(x, y, z)]
[out]closestThe closest point on the polygon. [(x, y, z)]
[out]posOverPolyTrue of the position is over the polygon.
Returns
The status flags for the query.

Uses the detail polygons to find the surface height. (Most accurate.)

pos does not have to be within the bounds of the polygon or navigation mesh.

See closestPointOnPolyBoundary() for a limited but faster option.

507 {
508  dtAssert(m_nav);
509  const dtMeshTile* tile = 0;
510  const dtPoly* poly = 0;
511  if (dtStatusFailed(m_nav->getTileAndPolyByRef(ref, &tile, &poly)))
512  return DT_FAILURE | DT_INVALID_PARAM;
513  if (!tile)
514  return DT_FAILURE | DT_INVALID_PARAM;
515 
516  // Off-mesh connections don't have detail polygons.
518  {
519  const float* v0 = &tile->verts[poly->verts[0]*3];
520  const float* v1 = &tile->verts[poly->verts[1]*3];
521  const float d0 = dtVdist(pos, v0);
522  const float d1 = dtVdist(pos, v1);
523  const float u = d0 / (d0+d1);
524  dtVlerp(closest, v0, v1, u);
525  if (posOverPoly)
526  *posOverPoly = false;
527  return DT_SUCCESS;
528  }
529 
530  const unsigned int ip = (unsigned int)(poly - tile->polys);
531  const dtPolyDetail* pd = &tile->detailMeshes[ip];
532 
533  // Clamp point to be inside the polygon.
534  float verts[DT_VERTS_PER_POLYGON*3];
535  float edged[DT_VERTS_PER_POLYGON];
536  float edget[DT_VERTS_PER_POLYGON];
537  const int nv = poly->vertCount;
538  for (int i = 0; i < nv; ++i)
539  dtVcopy(&verts[i*3], &tile->verts[poly->verts[i]*3]);
540 
541  dtVcopy(closest, pos);
542  if (!dtDistancePtPolyEdgesSqr(pos, verts, nv, edged, edget))
543  {
544  // Point is outside the polygon, dtClamp to nearest edge.
545  float dmin = edged[0];
546  int imin = 0;
547  for (int i = 1; i < nv; ++i)
548  {
549  if (edged[i] < dmin)
550  {
551  dmin = edged[i];
552  imin = i;
553  }
554  }
555  const float* va = &verts[imin*3];
556  const float* vb = &verts[((imin+1)%nv)*3];
557  dtVlerp(closest, va, vb, edget[imin]);
558 
559  if (posOverPoly)
560  *posOverPoly = false;
561  }
562  else
563  {
564  if (posOverPoly)
565  *posOverPoly = true;
566  }
567 
568  // Find height at the location.
569  for (int j = 0; j < pd->triCount; ++j)
570  {
571  const unsigned char* t = &tile->detailTris[(pd->triBase+j)*4];
572  const float* v[3];
573  for (int k = 0; k < 3; ++k)
574  {
575  if (t[k] < poly->vertCount)
576  v[k] = &tile->verts[poly->verts[t[k]]*3];
577  else
578  v[k] = &tile->detailVerts[(pd->vertBase+(t[k]-poly->vertCount))*3];
579  }
580  float h;
581  if (dtClosestHeightPointTriangle(closest, v[0], v[1], v[2], h))
582  {
583  closest[1] = h;
584  break;
585  }
586  }
587 
588  return DT_SUCCESS;
589 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
Defines the location of detail sub-mesh data within a dtMeshTile.
Definition: DetourNavMesh.h:198
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:218
unsigned char triCount
The number of triangles in the sub-mesh.
Definition: DetourNavMesh.h:203
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1128
unsigned int vertBase
The offset of the vertices in the dtMeshTile::detailVerts array.
Definition: DetourNavMesh.h:200
Definition: DetourNavMesh.h:162
bool dtClosestHeightPointTriangle(const float *p, const float *a, const float *b, const float *c, float &h)
Definition: DetourCommon.cpp:204
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
float * detailVerts
The detail mesh&#39;s unique vertices. [(x, y, z) * dtMeshHeader::detailVertCount].
Definition: DetourNavMesh.h:300
unsigned char * detailTris
The detail mesh&#39;s triangles. [(vertA, vertB, vertC) * dtMeshHeader::detailTriCount].
Definition: DetourNavMesh.h:303
dtPolyDetail * detailMeshes
The tile&#39;s detail sub-meshes. [Size: dtMeshHeader::detailMeshCount].
Definition: DetourNavMesh.h:297
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
unsigned int triBase
The offset of the triangles in the dtMeshTile::detailTris array.
Definition: DetourNavMesh.h:201
Definition: DetourNavMesh.h:288
bool dtDistancePtPolyEdgesSqr(const float *pt, const float *verts, const int nverts, float *ed, float *et)
Definition: DetourCommon.cpp:255
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:73
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ closestPointOnPolyBoundary()

dtStatus dtNavMeshQuery::closestPointOnPolyBoundary ( dtPolyRef  ref,
const float *  pos,
float *  closest 
) const

Returns a point on the boundary closest to the source point if the source point is outside the polygon's xz-bounds.

Parameters
[in]refThe reference id to the polygon.
[in]posThe position to check. [(x, y, z)]
[out]closestThe closest point. [(x, y, z)]
Returns
The status flags for the query.

Much faster than closestPointOnPoly().

If the provided position lies within the polygon's xz-bounds (above or below), then pos and closest will be equal.

The height of closest will be the polygon boundary. The height detail is not used.

pos does not have to be within the bounds of the polybon or the navigation mesh.

603 {
604  dtAssert(m_nav);
605 
606  const dtMeshTile* tile = 0;
607  const dtPoly* poly = 0;
608  if (dtStatusFailed(m_nav->getTileAndPolyByRef(ref, &tile, &poly)))
609  return DT_FAILURE | DT_INVALID_PARAM;
610 
611  // Collect vertices.
612  float verts[DT_VERTS_PER_POLYGON*3];
613  float edged[DT_VERTS_PER_POLYGON];
614  float edget[DT_VERTS_PER_POLYGON];
615  int nv = 0;
616  for (int i = 0; i < (int)poly->vertCount; ++i)
617  {
618  dtVcopy(&verts[nv*3], &tile->verts[poly->verts[i]*3]);
619  nv++;
620  }
621 
622  bool inside = dtDistancePtPolyEdgesSqr(pos, verts, nv, edged, edget);
623  if (inside)
624  {
625  // Point is inside the polygon, return the point.
626  dtVcopy(closest, pos);
627  }
628  else
629  {
630  // Point is outside the polygon, dtClamp to nearest edge.
631  float dmin = edged[0];
632  int imin = 0;
633  for (int i = 1; i < nv; ++i)
634  {
635  if (edged[i] < dmin)
636  {
637  dmin = edged[i];
638  imin = i;
639  }
640  }
641  const float* va = &verts[imin*3];
642  const float* vb = &verts[((imin+1)%nv)*3];
643  dtVlerp(closest, va, vb, edget[imin]);
644  }
645 
646  return DT_SUCCESS;
647 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1128
Definition: DetourNavMesh.h:162
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
Definition: DetourNavMesh.h:288
bool dtDistancePtPolyEdgesSqr(const float *pt, const float *verts, const int nverts, float *ed, float *et)
Definition: DetourCommon.cpp:255
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:73
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ finalizeSlicedFindPath()

dtStatus dtNavMeshQuery::finalizeSlicedFindPath ( dtPolyRef path,
int *  pathCount,
const int  maxPath 
)

Finalizes and returns the results of a sliced path query.

Parameters
[out]pathAn ordered list of polygon references representing the path. (Start to end.) [(polyRef) * pathCount]
[out]pathCountThe number of polygons returned in the path array.
[in]maxPathThe max number of polygons the path array can hold. [Limit: >= 1]
Returns
The status flags for the query.
1532 {
1533  *pathCount = 0;
1534 
1536  {
1537  // Reset query.
1538  memset(&m_query, 0, sizeof(dtQueryData));
1539  return DT_FAILURE;
1540  }
1541 
1542  int n = 0;
1543 
1544  if (m_query.startRef == m_query.endRef)
1545  {
1546  // Special case: the search starts and ends at same poly.
1547  path[n++] = m_query.startRef;
1548  }
1549  else
1550  {
1551  // Reverse the path.
1553 
1556 
1557  dtNode* prev = 0;
1558  dtNode* node = m_query.lastBestNode;
1559  int prevRay = 0;
1560  do
1561  {
1562  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1563  node->pidx = m_nodePool->getNodeIdx(prev);
1564  prev = node;
1565  int nextRay = node->flags & DT_NODE_PARENT_DETACHED; // keep track of whether parent is not adjacent (i.e. due to raycast shortcut)
1566  node->flags = (node->flags & ~DT_NODE_PARENT_DETACHED) | prevRay; // and store it in the reversed path's node
1567  prevRay = nextRay;
1568  node = next;
1569  }
1570  while (node);
1571 
1572  // Store path
1573  node = prev;
1574  do
1575  {
1576  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1577  dtStatus status = 0;
1578  if (node->flags & DT_NODE_PARENT_DETACHED)
1579  {
1580  float t, normal[3];
1581  int m;
1582  status = raycast(node->id, node->pos, next->pos, m_query.filter, &t, normal, path+n, &m, maxPath-n);
1583  n += m;
1584  // raycast ends on poly boundary and the path might include the next poly boundary.
1585  if (path[n-1] == next->id)
1586  n--; // remove to avoid duplicates
1587  }
1588  else
1589  {
1590  path[n++] = node->id;
1591  if (n >= maxPath)
1592  status = DT_BUFFER_TOO_SMALL;
1593  }
1594 
1595  if (status & DT_STATUS_DETAIL_MASK)
1596  {
1597  m_query.status |= status & DT_STATUS_DETAIL_MASK;
1598  break;
1599  }
1600  node = next;
1601  }
1602  while (node);
1603  }
1604 
1605  const dtStatus details = m_query.status & DT_STATUS_DETAIL_MASK;
1606 
1607  // Reset query.
1608  memset(&m_query, 0, sizeof(dtQueryData));
1609 
1610  *pathCount = n;
1611 
1612  return DT_SUCCESS | details;
1613 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
Definition: DetourNode.h:36
static const unsigned int DT_STATUS_DETAIL_MASK
Definition: DetourStatus.h:30
int next(int i, int n)
Definition: RecastContour.cpp:469
float pos[3]
Position of the node.
Definition: DetourNode.h:38
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
struct dtNode * lastBestNode
Definition: DetourNavMeshQuery.h:550
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned int dtStatus
Definition: DetourStatus.h:22
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
dtStatus status
Definition: DetourNavMeshQuery.h:549
static const unsigned int DT_PARTIAL_RESULT
Definition: DetourStatus.h:37
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
dtStatus raycast(dtPolyRef startRef, const float *startPos, const float *endPos, const dtQueryFilter *filter, float *t, float *hitNormal, dtPolyRef *path, int *pathCount, const int maxPath) const
Definition: DetourNavMeshQuery.cpp:2424
Definition: DetourNode.h:28
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
dtPolyRef startRef
Definition: DetourNavMeshQuery.h:552
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
dtPolyRef endRef
Definition: DetourNavMeshQuery.h:552
int prev(int i, int n)
Definition: RecastContour.cpp:468
dtQueryData m_query
Sliced query state.
Definition: DetourNavMeshQuery.h:558
const dtQueryFilter * filter
Definition: DetourNavMeshQuery.h:554
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ finalizeSlicedFindPathPartial()

dtStatus dtNavMeshQuery::finalizeSlicedFindPathPartial ( const dtPolyRef existing,
const int  existingSize,
dtPolyRef path,
int *  pathCount,
const int  maxPath 
)

Finalizes and returns the results of an incomplete sliced path query, returning the path to the furthest polygon on the existing path that was visited during the search.

Parameters
[in]existingAn array of polygon references for the existing path.
[in]existingSizeThe number of polygon in the existing array.
[out]pathAn ordered list of polygon references representing the path. (Start to end.) [(polyRef) * pathCount]
[out]pathCountThe number of polygons returned in the path array.
[in]maxPathThe max number of polygons the path array can hold. [Limit: >= 1]
Returns
The status flags for the query.
1617 {
1618  *pathCount = 0;
1619 
1620  if (existingSize == 0)
1621  {
1622  return DT_FAILURE;
1623  }
1624 
1626  {
1627  // Reset query.
1628  memset(&m_query, 0, sizeof(dtQueryData));
1629  return DT_FAILURE;
1630  }
1631 
1632  int n = 0;
1633 
1634  if (m_query.startRef == m_query.endRef)
1635  {
1636  // Special case: the search starts and ends at same poly.
1637  path[n++] = m_query.startRef;
1638  }
1639  else
1640  {
1641  // Find furthest existing node that was visited.
1642  dtNode* prev = 0;
1643  dtNode* node = 0;
1644  for (int i = existingSize-1; i >= 0; --i)
1645  {
1646  m_nodePool->findNodes(existing[i], &node, 1);
1647  if (node)
1648  break;
1649  }
1650 
1651  if (!node)
1652  {
1655  node = m_query.lastBestNode;
1656  }
1657 
1658  // Reverse the path.
1659  int prevRay = 0;
1660  do
1661  {
1662  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1663  node->pidx = m_nodePool->getNodeIdx(prev);
1664  prev = node;
1665  int nextRay = node->flags & DT_NODE_PARENT_DETACHED; // keep track of whether parent is not adjacent (i.e. due to raycast shortcut)
1666  node->flags = (node->flags & ~DT_NODE_PARENT_DETACHED) | prevRay; // and store it in the reversed path's node
1667  prevRay = nextRay;
1668  node = next;
1669  }
1670  while (node);
1671 
1672  // Store path
1673  node = prev;
1674  do
1675  {
1676  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1677  dtStatus status = 0;
1678  if (node->flags & DT_NODE_PARENT_DETACHED)
1679  {
1680  float t, normal[3];
1681  int m;
1682  status = raycast(node->id, node->pos, next->pos, m_query.filter, &t, normal, path+n, &m, maxPath-n);
1683  n += m;
1684  // raycast ends on poly boundary and the path might include the next poly boundary.
1685  if (path[n-1] == next->id)
1686  n--; // remove to avoid duplicates
1687  }
1688  else
1689  {
1690  path[n++] = node->id;
1691  if (n >= maxPath)
1692  status = DT_BUFFER_TOO_SMALL;
1693  }
1694 
1695  if (status & DT_STATUS_DETAIL_MASK)
1696  {
1697  m_query.status |= status & DT_STATUS_DETAIL_MASK;
1698  break;
1699  }
1700  node = next;
1701  }
1702  while (node);
1703  }
1704 
1705  const dtStatus details = m_query.status & DT_STATUS_DETAIL_MASK;
1706 
1707  // Reset query.
1708  memset(&m_query, 0, sizeof(dtQueryData));
1709 
1710  *pathCount = n;
1711 
1712  return DT_SUCCESS | details;
1713 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
Definition: DetourNode.h:36
static const unsigned int DT_STATUS_DETAIL_MASK
Definition: DetourStatus.h:30
int next(int i, int n)
Definition: RecastContour.cpp:469
float pos[3]
Position of the node.
Definition: DetourNode.h:38
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
struct dtNode * lastBestNode
Definition: DetourNavMeshQuery.h:550
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned int dtStatus
Definition: DetourStatus.h:22
unsigned int findNodes(dtPolyRef id, dtNode **nodes, const int maxNodes)
Definition: DetourNode.cpp:89
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
dtStatus status
Definition: DetourNavMeshQuery.h:549
static const unsigned int DT_PARTIAL_RESULT
Definition: DetourStatus.h:37
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
dtStatus raycast(dtPolyRef startRef, const float *startPos, const float *endPos, const dtQueryFilter *filter, float *t, float *hitNormal, dtPolyRef *path, int *pathCount, const int maxPath) const
Definition: DetourNavMeshQuery.cpp:2424
Definition: DetourNode.h:28
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
dtPolyRef startRef
Definition: DetourNavMeshQuery.h:552
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
dtPolyRef endRef
Definition: DetourNavMeshQuery.h:552
int prev(int i, int n)
Definition: RecastContour.cpp:468
dtQueryData m_query
Sliced query state.
Definition: DetourNavMeshQuery.h:558
const dtQueryFilter * filter
Definition: DetourNavMeshQuery.h:554
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ findDistanceToWall()

dtStatus dtNavMeshQuery::findDistanceToWall ( dtPolyRef  startRef,
const float *  centerPos,
const float  maxRadius,
const dtQueryFilter filter,
float *  hitDist,
float *  hitPos,
float *  hitNormal 
) const

Finds the distance from the specified position to the nearest polygon wall.

Parameters
[in]startRefThe reference id of the polygon containing centerPos.
[in]centerPosThe center of the search circle. [(x, y, z)]
[in]maxRadiusThe radius of the search circle.
[in]filterThe polygon filter to apply to the query.
[out]hitDistThe distance to the nearest wall from centerPos.
[out]hitPosThe nearest position on the wall that was hit. [(x, y, z)]
[out]hitNormalThe normalized ray formed from the wall point to the source point. [(x, y, z)]
Returns
The status flags for the query.

hitPos is not adjusted using the height detail data.

hitDist will equal the search radius if there is no wall within the radius. In this case the values of hitPos and hitNormal are undefined.

The normal will become unpredicable if hitDist is a very small number.

3452 {
3453  dtAssert(m_nav);
3456 
3457  // Validate input
3458  if (!startRef || !m_nav->isValidPolyRef(startRef))
3459  return DT_FAILURE | DT_INVALID_PARAM;
3460 
3461  m_nodePool->clear();
3462  m_openList->clear();
3463 
3464  dtNode* startNode = m_nodePool->getNode(startRef);
3465  dtVcopy(startNode->pos, centerPos);
3466  startNode->pidx = 0;
3467  startNode->cost = 0;
3468  startNode->total = 0;
3469  startNode->id = startRef;
3470  startNode->flags = DT_NODE_OPEN;
3471  m_openList->push(startNode);
3472 
3473  float radiusSqr = dtSqr(maxRadius);
3474 
3475  dtStatus status = DT_SUCCESS;
3476 
3477  while (!m_openList->empty())
3478  {
3479  dtNode* bestNode = m_openList->pop();
3480  bestNode->flags &= ~DT_NODE_OPEN;
3481  bestNode->flags |= DT_NODE_CLOSED;
3482 
3483  // Get poly and tile.
3484  // The API input has been cheked already, skip checking internal data.
3485  const dtPolyRef bestRef = bestNode->id;
3486  const dtMeshTile* bestTile = 0;
3487  const dtPoly* bestPoly = 0;
3488  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
3489 
3490  // Get parent poly and tile.
3491  dtPolyRef parentRef = 0;
3492  const dtMeshTile* parentTile = 0;
3493  const dtPoly* parentPoly = 0;
3494  if (bestNode->pidx)
3495  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
3496  if (parentRef)
3497  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
3498 
3499  // Hit test walls.
3500  for (int i = 0, j = (int)bestPoly->vertCount-1; i < (int)bestPoly->vertCount; j = i++)
3501  {
3502  // Skip non-solid edges.
3503  if (bestPoly->neis[j] & DT_EXT_LINK)
3504  {
3505  // Tile border.
3506  bool solid = true;
3507  for (unsigned int k = bestPoly->firstLink; k != DT_NULL_LINK; k = bestTile->links[k].next)
3508  {
3509  const dtLink* link = &bestTile->links[k];
3510  if (link->edge == j)
3511  {
3512  if (link->ref != 0)
3513  {
3514  const dtMeshTile* neiTile = 0;
3515  const dtPoly* neiPoly = 0;
3516  m_nav->getTileAndPolyByRefUnsafe(link->ref, &neiTile, &neiPoly);
3517  if (filter->passFilter(link->ref, neiTile, neiPoly))
3518  solid = false;
3519  }
3520  break;
3521  }
3522  }
3523  if (!solid) continue;
3524  }
3525  else if (bestPoly->neis[j])
3526  {
3527  // Internal edge
3528  const unsigned int idx = (unsigned int)(bestPoly->neis[j]-1);
3529  const dtPolyRef ref = m_nav->getPolyRefBase(bestTile) | idx;
3530  if (filter->passFilter(ref, bestTile, &bestTile->polys[idx]))
3531  continue;
3532  }
3533 
3534  // Calc distance to the edge.
3535  const float* vj = &bestTile->verts[bestPoly->verts[j]*3];
3536  const float* vi = &bestTile->verts[bestPoly->verts[i]*3];
3537  float tseg;
3538  float distSqr = dtDistancePtSegSqr2D(centerPos, vj, vi, tseg);
3539 
3540  // Edge is too far, skip.
3541  if (distSqr > radiusSqr)
3542  continue;
3543 
3544  // Hit wall, update radius.
3545  radiusSqr = distSqr;
3546  // Calculate hit pos.
3547  hitPos[0] = vj[0] + (vi[0] - vj[0])*tseg;
3548  hitPos[1] = vj[1] + (vi[1] - vj[1])*tseg;
3549  hitPos[2] = vj[2] + (vi[2] - vj[2])*tseg;
3550  }
3551 
3552  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
3553  {
3554  const dtLink* link = &bestTile->links[i];
3555  dtPolyRef neighbourRef = link->ref;
3556  // Skip invalid neighbours and do not follow back to parent.
3557  if (!neighbourRef || neighbourRef == parentRef)
3558  continue;
3559 
3560  // Expand to neighbour.
3561  const dtMeshTile* neighbourTile = 0;
3562  const dtPoly* neighbourPoly = 0;
3563  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
3564 
3565  // Skip off-mesh connections.
3566  if (neighbourPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
3567  continue;
3568 
3569  // Calc distance to the edge.
3570  const float* va = &bestTile->verts[bestPoly->verts[link->edge]*3];
3571  const float* vb = &bestTile->verts[bestPoly->verts[(link->edge+1) % bestPoly->vertCount]*3];
3572  float tseg;
3573  float distSqr = dtDistancePtSegSqr2D(centerPos, va, vb, tseg);
3574 
3575  // If the circle is not touching the next polygon, skip it.
3576  if (distSqr > radiusSqr)
3577  continue;
3578 
3579  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
3580  continue;
3581 
3582  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
3583  if (!neighbourNode)
3584  {
3585  status |= DT_OUT_OF_NODES;
3586  continue;
3587  }
3588 
3589  if (neighbourNode->flags & DT_NODE_CLOSED)
3590  continue;
3591 
3592  // Cost
3593  if (neighbourNode->flags == 0)
3594  {
3595  getEdgeMidPoint(bestRef, bestPoly, bestTile,
3596  neighbourRef, neighbourPoly, neighbourTile, neighbourNode->pos);
3597  }
3598 
3599  const float total = bestNode->total + dtVdist(bestNode->pos, neighbourNode->pos);
3600 
3601  // The node is already in open list and the new result is worse, skip.
3602  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
3603  continue;
3604 
3605  neighbourNode->id = neighbourRef;
3606  neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED);
3607  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
3608  neighbourNode->total = total;
3609 
3610  if (neighbourNode->flags & DT_NODE_OPEN)
3611  {
3612  m_openList->modify(neighbourNode);
3613  }
3614  else
3615  {
3616  neighbourNode->flags |= DT_NODE_OPEN;
3617  m_openList->push(neighbourNode);
3618  }
3619  }
3620  }
3621 
3622  // Calc hit normal.
3623  dtVsub(hitNormal, centerPos, hitPos);
3624  dtVnormalize(hitNormal);
3625 
3626  *hitDist = sqrtf(radiusSqr);
3627 
3628  return status;
3629 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
bool empty() const
Definition: DetourNode.h:144
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
void clear()
Definition: DetourNode.h:114
#define dtAssert(expression)
Definition: DetourAssert.h:47
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
Definition: DetourNode.h:36
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:218
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:129
float pos[3]
Position of the node.
Definition: DetourNode.h:38
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
Definition: DetourNode.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int dtStatus
Definition: DetourStatus.h:22
float dtDistancePtSegSqr2D(const float *pt, const float *p, const float *q, float &t)
Definition: DetourCommon.cpp:170
static const unsigned int DT_OUT_OF_NODES
Definition: DetourStatus.h:36
dtNode * pop()
Definition: DetourNode.h:118
void dtVnormalize(float *v)
Definition: DetourCommon.h:264
unsigned short neis[DT_VERTS_PER_POLYGON]
Packed data representing neighbor polygons references and flags for each edge.
Definition: DetourNavMesh.h:172
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
Definition: DetourNavMesh.h:162
dtStatus getEdgeMidPoint(dtPolyRef from, dtPolyRef to, float *mid) const
Returns edge mid point between two polygons.
Definition: DetourNavMeshQuery.cpp:2359
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:97
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
void dtVsub(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:140
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
float cost
Cost from previous node to current node.
Definition: DetourNode.h:39
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
void modify(dtNode *node)
Definition: DetourNode.h:132
Definition: DetourNavMesh.h:288
float total
Cost up to the node.
Definition: DetourNode.h:40
void clear()
Definition: DetourNode.cpp:83
void push(dtNode *node)
Definition: DetourNode.h:126
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ findLocalNeighbourhood()

dtStatus dtNavMeshQuery::findLocalNeighbourhood ( dtPolyRef  startRef,
const float *  centerPos,
const float  radius,
const dtQueryFilter filter,
dtPolyRef resultRef,
dtPolyRef resultParent,
int *  resultCount,
const int  maxResult 
) const

Finds the non-overlapping navigation polygons in the local neighbourhood around the center position.

Parameters
[in]startRefThe reference id of the polygon where the search starts.
[in]centerPosThe center of the query circle. [(x, y, z)]
[in]radiusThe radius of the query circle.
[in]filterThe polygon filter to apply to the query.
[out]resultRefThe reference ids of the polygons touched by the circle.
[out]resultParentThe reference ids of the parent polygons for each result. Zero if a result polygon has no parent. [opt]
[out]resultCountThe number of polygons found.
[in]maxResultThe maximum number of polygons the result arrays can hold.
Returns
The status flags for the query.

This method is optimized for a small search radius and small number of result polygons.

Candidate polygons are found by searching the navigation graph beginning at the start polygon.

The same intersection test restrictions that apply to the findPolysAroundCircle mehtod applies to this method.

The value of the center point is used as the start point for cost calculations. It is not projected onto the surface of the mesh, so its y-value will effect the costs.

Intersection tests occur in 2D. All polygons and the search circle are projected onto the xz-plane. So the y-value of the center point does not effect intersection tests.

If the result arrays are is too small to hold the entire result set, they will be filled to capacity.

3088 {
3089  dtAssert(m_nav);
3091 
3092  *resultCount = 0;
3093 
3094  // Validate input
3095  if (!startRef || !m_nav->isValidPolyRef(startRef))
3096  return DT_FAILURE | DT_INVALID_PARAM;
3097 
3098  static const int MAX_STACK = 48;
3099  dtNode* stack[MAX_STACK];
3100  int nstack = 0;
3101 
3102  m_tinyNodePool->clear();
3103 
3104  dtNode* startNode = m_tinyNodePool->getNode(startRef);
3105  startNode->pidx = 0;
3106  startNode->id = startRef;
3107  startNode->flags = DT_NODE_CLOSED;
3108  stack[nstack++] = startNode;
3109 
3110  const float radiusSqr = dtSqr(radius);
3111 
3112  float pa[DT_VERTS_PER_POLYGON*3];
3113  float pb[DT_VERTS_PER_POLYGON*3];
3114 
3115  dtStatus status = DT_SUCCESS;
3116 
3117  int n = 0;
3118  if (n < maxResult)
3119  {
3120  resultRef[n] = startNode->id;
3121  if (resultParent)
3122  resultParent[n] = 0;
3123  ++n;
3124  }
3125  else
3126  {
3127  status |= DT_BUFFER_TOO_SMALL;
3128  }
3129 
3130  while (nstack)
3131  {
3132  // Pop front.
3133  dtNode* curNode = stack[0];
3134  for (int i = 0; i < nstack-1; ++i)
3135  stack[i] = stack[i+1];
3136  nstack--;
3137 
3138  // Get poly and tile.
3139  // The API input has been cheked already, skip checking internal data.
3140  const dtPolyRef curRef = curNode->id;
3141  const dtMeshTile* curTile = 0;
3142  const dtPoly* curPoly = 0;
3143  m_nav->getTileAndPolyByRefUnsafe(curRef, &curTile, &curPoly);
3144 
3145  for (unsigned int i = curPoly->firstLink; i != DT_NULL_LINK; i = curTile->links[i].next)
3146  {
3147  const dtLink* link = &curTile->links[i];
3148  dtPolyRef neighbourRef = link->ref;
3149  // Skip invalid neighbours.
3150  if (!neighbourRef)
3151  continue;
3152 
3153  // Skip if cannot alloca more nodes.
3154  dtNode* neighbourNode = m_tinyNodePool->getNode(neighbourRef);
3155  if (!neighbourNode)
3156  continue;
3157  // Skip visited.
3158  if (neighbourNode->flags & DT_NODE_CLOSED)
3159  continue;
3160 
3161  // Expand to neighbour
3162  const dtMeshTile* neighbourTile = 0;
3163  const dtPoly* neighbourPoly = 0;
3164  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
3165 
3166  // Skip off-mesh connections.
3167  if (neighbourPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
3168  continue;
3169 
3170  // Do not advance if the polygon is excluded by the filter.
3171  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
3172  continue;
3173 
3174  // Find edge and calc distance to the edge.
3175  float va[3], vb[3];
3176  if (!getPortalPoints(curRef, curPoly, curTile, neighbourRef, neighbourPoly, neighbourTile, va, vb))
3177  continue;
3178 
3179  // If the circle is not touching the next polygon, skip it.
3180  float tseg;
3181  float distSqr = dtDistancePtSegSqr2D(centerPos, va, vb, tseg);
3182  if (distSqr > radiusSqr)
3183  continue;
3184 
3185  // Mark node visited, this is done before the overlap test so that
3186  // we will not visit the poly again if the test fails.
3187  neighbourNode->flags |= DT_NODE_CLOSED;
3188  neighbourNode->pidx = m_tinyNodePool->getNodeIdx(curNode);
3189 
3190  // Check that the polygon does not collide with existing polygons.
3191 
3192  // Collect vertices of the neighbour poly.
3193  const int npa = neighbourPoly->vertCount;
3194  for (int k = 0; k < npa; ++k)
3195  dtVcopy(&pa[k*3], &neighbourTile->verts[neighbourPoly->verts[k]*3]);
3196 
3197  bool overlap = false;
3198  for (int j = 0; j < n; ++j)
3199  {
3200  dtPolyRef pastRef = resultRef[j];
3201 
3202  // Connected polys do not overlap.
3203  bool connected = false;
3204  for (unsigned int k = curPoly->firstLink; k != DT_NULL_LINK; k = curTile->links[k].next)
3205  {
3206  if (curTile->links[k].ref == pastRef)
3207  {
3208  connected = true;
3209  break;
3210  }
3211  }
3212  if (connected)
3213  continue;
3214 
3215  // Potentially overlapping.
3216  const dtMeshTile* pastTile = 0;
3217  const dtPoly* pastPoly = 0;
3218  m_nav->getTileAndPolyByRefUnsafe(pastRef, &pastTile, &pastPoly);
3219 
3220  // Get vertices and test overlap
3221  const int npb = pastPoly->vertCount;
3222  for (int k = 0; k < npb; ++k)
3223  dtVcopy(&pb[k*3], &pastTile->verts[pastPoly->verts[k]*3]);
3224 
3225  if (dtOverlapPolyPoly2D(pa,npa, pb,npb))
3226  {
3227  overlap = true;
3228  break;
3229  }
3230  }
3231  if (overlap)
3232  continue;
3233 
3234  // This poly is fine, store and advance to the poly.
3235  if (n < maxResult)
3236  {
3237  resultRef[n] = neighbourRef;
3238  if (resultParent)
3239  resultParent[n] = curRef;
3240  ++n;
3241  }
3242  else
3243  {
3244  status |= DT_BUFFER_TOO_SMALL;
3245  }
3246 
3247  if (nstack < MAX_STACK)
3248  {
3249  stack[nstack++] = neighbourNode;
3250  }
3251  }
3252  }
3253 
3254  *resultCount = n;
3255 
3256  return status;
3257 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
#define dtAssert(expression)
Definition: DetourAssert.h:47
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
Definition: DetourNode.h:36
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:129
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
Definition: BnetFileGenerator.h:49
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
float dtDistancePtSegSqr2D(const float *pt, const float *p, const float *q, float &t)
Definition: DetourCommon.cpp:170
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
Definition: DetourNavMesh.h:162
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
bool dtOverlapPolyPoly2D(const float *polya, const int npolya, const float *polyb, const int npolyb)
Definition: DetourCommon.cpp:295
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:560
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
Definition: DetourNavMesh.h:288
void clear()
Definition: DetourNode.cpp:83
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:73
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ findNearestPoly()

dtStatus dtNavMeshQuery::findNearestPoly ( const float *  center,
const float *  halfExtents,
const dtQueryFilter filter,
dtPolyRef nearestRef,
float *  nearestPt 
) const

Finds the polygon nearest to the specified center point.

Parameters
[in]centerThe center of the search box. [(x, y, z)]
[in]halfExtentsThe search distance along each axis. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[out]nearestRefThe reference id of the nearest polygon.
[out]nearestPtThe nearest point on the polygon. [opt] [(x, y, z)]
Returns
The status flags for the query.
Note
If the search box does not intersect any polygons the search will return DT_SUCCESS, but nearestRef will be zero. So if in doubt, check nearestRef before using nearestPt.
765 {
766  dtAssert(m_nav);
767 
768  if (!nearestRef)
769  return DT_FAILURE | DT_INVALID_PARAM;
770 
771  dtFindNearestPolyQuery query(this, center);
772 
773  dtStatus status = queryPolygons(center, halfExtents, filter, &query);
774  if (dtStatusFailed(status))
775  return status;
776 
777  *nearestRef = query.nearestRef();
778  // Only override nearestPt if we actually found a poly so the nearest point
779  // is valid.
780  if (nearestPt && *nearestRef)
781  dtVcopy(nearestPt, query.nearestPoint());
782 
783  return DT_SUCCESS;
784 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
Definition: DetourNavMeshQuery.cpp:702
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
char * query(struct soap *soap)
Definition: httpget.cpp:244
unsigned int dtStatus
Definition: DetourStatus.h:22
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtStatus queryPolygons(const float *center, const float *halfExtents, const dtQueryFilter *filter, dtPolyRef *polys, int *polyCount, const int maxPolys) const
Definition: DetourNavMeshQuery.cpp:946
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ findPath()

dtStatus dtNavMeshQuery::findPath ( dtPolyRef  startRef,
dtPolyRef  endRef,
const float *  startPos,
const float *  endPos,
const dtQueryFilter filter,
dtPolyRef path,
int *  pathCount,
const int  maxPath 
) const

Finds a path from the start polygon to the end polygon.

Parameters
[in]startRefThe refrence id of the start polygon.
[in]endRefThe reference id of the end polygon.
[in]startPosA position within the start polygon. [(x, y, z)]
[in]endPosA position within the end polygon. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[out]pathAn ordered list of polygon references representing the path. (Start to end.) [(polyRef) * pathCount]
[out]pathCountThe number of polygons returned in the path array.
[in]maxPathThe maximum number of polygons the path array can hold. [Limit: >= 1]

If the end polygon cannot be reached through the navigation graph, the last polygon in the path will be the nearest the end polygon.

If the path array is to small to hold the full result, it will be filled as far as possible from the start polygon toward the end polygon.

The start and end positions are used to calculate traversal costs. (The y-values impact the result.)

1020 {
1021  dtAssert(m_nav);
1024 
1025  if (pathCount)
1026  *pathCount = 0;
1027 
1028  // Validate input
1029  if (!m_nav->isValidPolyRef(startRef) || !m_nav->isValidPolyRef(endRef) ||
1030  !startPos || !endPos || !filter || maxPath <= 0 || !path || !pathCount)
1031  return DT_FAILURE | DT_INVALID_PARAM;
1032 
1033  if (startRef == endRef)
1034  {
1035  path[0] = startRef;
1036  *pathCount = 1;
1037  return DT_SUCCESS;
1038  }
1039 
1040  m_nodePool->clear();
1041  m_openList->clear();
1042 
1043  dtNode* startNode = m_nodePool->getNode(startRef);
1044  dtVcopy(startNode->pos, startPos);
1045  startNode->pidx = 0;
1046  startNode->cost = 0;
1047  startNode->total = dtVdist(startPos, endPos) * H_SCALE;
1048  startNode->id = startRef;
1049  startNode->flags = DT_NODE_OPEN;
1050  m_openList->push(startNode);
1051 
1052  dtNode* lastBestNode = startNode;
1053  float lastBestNodeCost = startNode->total;
1054 
1055  bool outOfNodes = false;
1056 
1057  while (!m_openList->empty())
1058  {
1059  // Remove node from open list and put it in closed list.
1060  dtNode* bestNode = m_openList->pop();
1061  bestNode->flags &= ~DT_NODE_OPEN;
1062  bestNode->flags |= DT_NODE_CLOSED;
1063 
1064  // Reached the goal, stop searching.
1065  if (bestNode->id == endRef)
1066  {
1067  lastBestNode = bestNode;
1068  break;
1069  }
1070 
1071  // Get current poly and tile.
1072  // The API input has been cheked already, skip checking internal data.
1073  const dtPolyRef bestRef = bestNode->id;
1074  const dtMeshTile* bestTile = 0;
1075  const dtPoly* bestPoly = 0;
1076  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
1077 
1078  // Get parent poly and tile.
1079  dtPolyRef parentRef = 0;
1080  const dtMeshTile* parentTile = 0;
1081  const dtPoly* parentPoly = 0;
1082  if (bestNode->pidx)
1083  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
1084  if (parentRef)
1085  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
1086 
1087  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
1088  {
1089  dtPolyRef neighbourRef = bestTile->links[i].ref;
1090 
1091  // Skip invalid ids and do not expand back to where we came from.
1092  if (!neighbourRef || neighbourRef == parentRef)
1093  continue;
1094 
1095  // Get neighbour poly and tile.
1096  // The API input has been cheked already, skip checking internal data.
1097  const dtMeshTile* neighbourTile = 0;
1098  const dtPoly* neighbourPoly = 0;
1099  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
1100 
1101  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
1102  continue;
1103 
1104  // deal explicitly with crossing tile boundaries
1105  unsigned char crossSide = 0;
1106  if (bestTile->links[i].side != 0xff)
1107  crossSide = bestTile->links[i].side >> 1;
1108 
1109  // get the node
1110  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef, crossSide);
1111  if (!neighbourNode)
1112  {
1113  outOfNodes = true;
1114  continue;
1115  }
1116 
1117  // If the node is visited the first time, calculate node position.
1118  if (neighbourNode->flags == 0)
1119  {
1120  getEdgeMidPoint(bestRef, bestPoly, bestTile,
1121  neighbourRef, neighbourPoly, neighbourTile,
1122  neighbourNode->pos);
1123  }
1124 
1125  // Calculate cost and heuristic.
1126  float cost = 0;
1127  float heuristic = 0;
1128 
1129  // Special case for last node.
1130  if (neighbourRef == endRef)
1131  {
1132  // Cost
1133  const float curCost = filter->getCost(bestNode->pos, neighbourNode->pos,
1134  parentRef, parentTile, parentPoly,
1135  bestRef, bestTile, bestPoly,
1136  neighbourRef, neighbourTile, neighbourPoly);
1137  const float endCost = filter->getCost(neighbourNode->pos, endPos,
1138  bestRef, bestTile, bestPoly,
1139  neighbourRef, neighbourTile, neighbourPoly,
1140  0, 0, 0);
1141 
1142  cost = bestNode->cost + curCost + endCost;
1143  heuristic = 0;
1144  }
1145  else
1146  {
1147  // Cost
1148  const float curCost = filter->getCost(bestNode->pos, neighbourNode->pos,
1149  parentRef, parentTile, parentPoly,
1150  bestRef, bestTile, bestPoly,
1151  neighbourRef, neighbourTile, neighbourPoly);
1152  cost = bestNode->cost + curCost;
1153  heuristic = dtVdist(neighbourNode->pos, endPos)*H_SCALE;
1154  }
1155 
1156  const float total = cost + heuristic;
1157 
1158  // The node is already in open list and the new result is worse, skip.
1159  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
1160  continue;
1161  // The node is already visited and process, and the new result is worse, skip.
1162  if ((neighbourNode->flags & DT_NODE_CLOSED) && total >= neighbourNode->total)
1163  continue;
1164 
1165  // Add or update the node.
1166  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
1167  neighbourNode->id = neighbourRef;
1168  neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED);
1169  neighbourNode->cost = cost;
1170  neighbourNode->total = total;
1171 
1172  if (neighbourNode->flags & DT_NODE_OPEN)
1173  {
1174  // Already in open, update node location.
1175  m_openList->modify(neighbourNode);
1176  }
1177  else
1178  {
1179  // Put the node in open list.
1180  neighbourNode->flags |= DT_NODE_OPEN;
1181  m_openList->push(neighbourNode);
1182  }
1183 
1184  // Update nearest node to target so far.
1185  if (heuristic < lastBestNodeCost)
1186  {
1187  lastBestNodeCost = heuristic;
1188  lastBestNode = neighbourNode;
1189  }
1190  }
1191  }
1192 
1193  dtStatus status = getPathToNode(lastBestNode, path, pathCount, maxPath);
1194 
1195  if (lastBestNode->id != endRef)
1196  status |= DT_PARTIAL_RESULT;
1197 
1198  if (outOfNodes)
1199  status |= DT_OUT_OF_NODES;
1200 
1201  return status;
1202 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
bool empty() const
Definition: DetourNode.h:144
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
void clear()
Definition: DetourNode.h:114
dtStatus getPathToNode(struct dtNode *endNode, dtPolyRef *path, int *pathCount, int maxPath) const
Definition: DetourNavMeshQuery.cpp:1204
#define dtAssert(expression)
Definition: DetourAssert.h:47
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
Definition: DetourNode.h:36
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:218
float pos[3]
Position of the node.
Definition: DetourNode.h:38
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
Definition: DetourNode.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned int dtStatus
Definition: DetourStatus.h:22
static const unsigned int DT_OUT_OF_NODES
Definition: DetourStatus.h:36
dtNode * pop()
Definition: DetourNode.h:118
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
Definition: DetourNavMesh.h:162
dtStatus getEdgeMidPoint(dtPolyRef from, dtPolyRef to, float *mid) const
Returns edge mid point between two polygons.
Definition: DetourNavMeshQuery.cpp:2359
static const unsigned int DT_PARTIAL_RESULT
Definition: DetourStatus.h:37
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
float cost
Cost from previous node to current node.
Definition: DetourNode.h:39
void modify(dtNode *node)
Definition: DetourNode.h:132
static const float H_SCALE
Definition: DetourNavMeshQuery.cpp:103
Definition: DetourNavMesh.h:288
float total
Cost up to the node.
Definition: DetourNode.h:40
void clear()
Definition: DetourNode.cpp:83
float getCost(const float *pa, const float *pb, const dtPolyRef prevRef, const dtMeshTile *prevTile, const dtPoly *prevPoly, const dtPolyRef curRef, const dtMeshTile *curTile, const dtPoly *curPoly, const dtPolyRef nextRef, const dtMeshTile *nextTile, const dtPoly *nextPoly) const
Definition: DetourNavMeshQuery.cpp:94
void push(dtNode *node)
Definition: DetourNode.h:126
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ findPolysAroundCircle()

dtStatus dtNavMeshQuery::findPolysAroundCircle ( dtPolyRef  startRef,
const float *  centerPos,
const float  radius,
const dtQueryFilter filter,
dtPolyRef resultRef,
dtPolyRef resultParent,
float *  resultCost,
int *  resultCount,
const int  maxResult 
) const

Finds the polygons along the navigation graph that touch the specified circle.

Parameters
[in]startRefThe reference id of the polygon where the search starts.
[in]centerPosThe center of the search circle. [(x, y, z)]
[in]radiusThe radius of the search circle.
[in]filterThe polygon filter to apply to the query.
[out]resultRefThe reference ids of the polygons touched by the circle. [opt]
[out]resultParentThe reference ids of the parent polygons for each result. Zero if a result polygon has no parent. [opt]
[out]resultCostThe search cost from centerPos to the polygon. [opt]
[out]resultCountThe number of polygons found. [opt]
[in]maxResultThe maximum number of polygons the result arrays can hold.
Returns
The status flags for the query.

At least one result array must be provided.

The order of the result set is from least to highest cost to reach the polygon.

A common use case for this method is to perform Dijkstra searches. Candidate polygons are found by searching the graph beginning at the start polygon.

If a polygon is not found via the graph search, even if it intersects the search circle, it will not be included in the result set. For example:

polyA is the start polygon. polyB shares an edge with polyA. (Is adjacent.) polyC shares an edge with polyB, but not with polyA Even if the search circle overlaps polyC, it will not be included in the result set unless polyB is also in the set.

The value of the center point is used as the start position for cost calculations. It is not projected onto the surface of the mesh, so its y-value will effect the costs.

Intersection tests occur in 2D. All polygons and the search circle are projected onto the xz-plane. So the y-value of the center point does not effect intersection tests.

If the result arrays are to small to hold the entire result set, they will be filled to capacity.

2733 {
2734  dtAssert(m_nav);
2737 
2738  *resultCount = 0;
2739 
2740  // Validate input
2741  if (!startRef || !m_nav->isValidPolyRef(startRef))
2742  return DT_FAILURE | DT_INVALID_PARAM;
2743 
2744  m_nodePool->clear();
2745  m_openList->clear();
2746 
2747  dtNode* startNode = m_nodePool->getNode(startRef);
2748  dtVcopy(startNode->pos, centerPos);
2749  startNode->pidx = 0;
2750  startNode->cost = 0;
2751  startNode->total = 0;
2752  startNode->id = startRef;
2753  startNode->flags = DT_NODE_OPEN;
2754  m_openList->push(startNode);
2755 
2756  dtStatus status = DT_SUCCESS;
2757 
2758  int n = 0;
2759 
2760  const float radiusSqr = dtSqr(radius);
2761 
2762  while (!m_openList->empty())
2763  {
2764  dtNode* bestNode = m_openList->pop();
2765  bestNode->flags &= ~DT_NODE_OPEN;
2766  bestNode->flags |= DT_NODE_CLOSED;
2767 
2768  // Get poly and tile.
2769  // The API input has been cheked already, skip checking internal data.
2770  const dtPolyRef bestRef = bestNode->id;
2771  const dtMeshTile* bestTile = 0;
2772  const dtPoly* bestPoly = 0;
2773  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
2774 
2775  // Get parent poly and tile.
2776  dtPolyRef parentRef = 0;
2777  const dtMeshTile* parentTile = 0;
2778  const dtPoly* parentPoly = 0;
2779  if (bestNode->pidx)
2780  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
2781  if (parentRef)
2782  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
2783 
2784  if (n < maxResult)
2785  {
2786  if (resultRef)
2787  resultRef[n] = bestRef;
2788  if (resultParent)
2789  resultParent[n] = parentRef;
2790  if (resultCost)
2791  resultCost[n] = bestNode->total;
2792  ++n;
2793  }
2794  else
2795  {
2796  status |= DT_BUFFER_TOO_SMALL;
2797  }
2798 
2799  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
2800  {
2801  const dtLink* link = &bestTile->links[i];
2802  dtPolyRef neighbourRef = link->ref;
2803  // Skip invalid neighbours and do not follow back to parent.
2804  if (!neighbourRef || neighbourRef == parentRef)
2805  continue;
2806 
2807  // Expand to neighbour
2808  const dtMeshTile* neighbourTile = 0;
2809  const dtPoly* neighbourPoly = 0;
2810  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
2811 
2812  // Do not advance if the polygon is excluded by the filter.
2813  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
2814  continue;
2815 
2816  // Find edge and calc distance to the edge.
2817  float va[3], vb[3];
2818  if (!getPortalPoints(bestRef, bestPoly, bestTile, neighbourRef, neighbourPoly, neighbourTile, va, vb))
2819  continue;
2820 
2821  // If the circle is not touching the next polygon, skip it.
2822  float tseg;
2823  float distSqr = dtDistancePtSegSqr2D(centerPos, va, vb, tseg);
2824  if (distSqr > radiusSqr)
2825  continue;
2826 
2827  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
2828  if (!neighbourNode)
2829  {
2830  status |= DT_OUT_OF_NODES;
2831  continue;
2832  }
2833 
2834  if (neighbourNode->flags & DT_NODE_CLOSED)
2835  continue;
2836 
2837  // Cost
2838  if (neighbourNode->flags == 0)
2839  dtVlerp(neighbourNode->pos, va, vb, 0.5f);
2840 
2841  float cost = filter->getCost(
2842  bestNode->pos, neighbourNode->pos,
2843  parentRef, parentTile, parentPoly,
2844  bestRef, bestTile, bestPoly,
2845  neighbourRef, neighbourTile, neighbourPoly);
2846 
2847  const float total = bestNode->total + cost;
2848 
2849  // The node is already in open list and the new result is worse, skip.
2850  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
2851  continue;
2852 
2853  neighbourNode->id = neighbourRef;
2854  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
2855  neighbourNode->total = total;
2856 
2857  if (neighbourNode->flags & DT_NODE_OPEN)
2858  {
2859  m_openList->modify(neighbourNode);
2860  }
2861  else
2862  {
2863  neighbourNode->flags = DT_NODE_OPEN;
2864  m_openList->push(neighbourNode);
2865  }
2866  }
2867  }
2868 
2869  *resultCount = n;
2870 
2871  return status;
2872 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
bool empty() const
Definition: DetourNode.h:144
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
void clear()
Definition: DetourNode.h:114
#define dtAssert(expression)
Definition: DetourAssert.h:47
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
Definition: DetourNode.h:36
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:129
float pos[3]
Position of the node.
Definition: DetourNode.h:38
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
Definition: DetourNode.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
float dtDistancePtSegSqr2D(const float *pt, const float *p, const float *q, float &t)
Definition: DetourCommon.cpp:170
static const unsigned int DT_OUT_OF_NODES
Definition: DetourStatus.h:36
dtNode * pop()
Definition: DetourNode.h:118
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
Definition: DetourNavMesh.h:162
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
float cost
Cost from previous node to current node.
Definition: DetourNode.h:39
void modify(dtNode *node)
Definition: DetourNode.h:132
Definition: DetourNavMesh.h:288
float total
Cost up to the node.
Definition: DetourNode.h:40
void clear()
Definition: DetourNode.cpp:83
float getCost(const float *pa, const float *pb, const dtPolyRef prevRef, const dtMeshTile *prevTile, const dtPoly *prevPoly, const dtPolyRef curRef, const dtMeshTile *curTile, const dtPoly *curPoly, const dtPolyRef nextRef, const dtMeshTile *nextTile, const dtPoly *nextPoly) const
Definition: DetourNavMeshQuery.cpp:94
void push(dtNode *node)
Definition: DetourNode.h:126
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ findPolysAroundShape()

dtStatus dtNavMeshQuery::findPolysAroundShape ( dtPolyRef  startRef,
const float *  verts,
const int  nverts,
const dtQueryFilter filter,
dtPolyRef resultRef,
dtPolyRef resultParent,
float *  resultCost,
int *  resultCount,
const int  maxResult 
) const

Finds the polygons along the naviation graph that touch the specified convex polygon.

Parameters
[in]startRefThe reference id of the polygon where the search starts.
[in]vertsThe vertices describing the convex polygon. (CCW) [(x, y, z) * nverts]
[in]nvertsThe number of vertices in the polygon.
[in]filterThe polygon filter to apply to the query.
[out]resultRefThe reference ids of the polygons touched by the search polygon. [opt]
[out]resultParentThe reference ids of the parent polygons for each result. Zero if a result polygon has no parent. [opt]
[out]resultCostThe search cost from the centroid point to the polygon. [opt]
[out]resultCountThe number of polygons found.
[in]maxResultThe maximum number of polygons the result arrays can hold.
Returns
The status flags for the query.

The order of the result set is from least to highest cost.

At least one result array must be provided.

A common use case for this method is to perform Dijkstra searches. Candidate polygons are found by searching the graph beginning at the start polygon.

The same intersection test restrictions that apply to findPolysAroundCircle() method apply to this method.

The 3D centroid of the search polygon is used as the start position for cost calculations.

Intersection tests occur in 2D. All polygons are projected onto the xz-plane. So the y-values of the vertices do not effect intersection tests.

If the result arrays are is too small to hold the entire result set, they will be filled to capacity.

2900 {
2901  dtAssert(m_nav);
2904 
2905  *resultCount = 0;
2906 
2907  // Validate input
2908  if (!startRef || !m_nav->isValidPolyRef(startRef))
2909  return DT_FAILURE | DT_INVALID_PARAM;
2910 
2911  m_nodePool->clear();
2912  m_openList->clear();
2913 
2914  float centerPos[3] = {0,0,0};
2915  for (int i = 0; i < nverts; ++i)
2916  dtVadd(centerPos,centerPos,&verts[i*3]);
2917  dtVscale(centerPos,centerPos,1.0f/nverts);
2918 
2919  dtNode* startNode = m_nodePool->getNode(startRef);
2920  dtVcopy(startNode->pos, centerPos);
2921  startNode->pidx = 0;
2922  startNode->cost = 0;
2923  startNode->total = 0;
2924  startNode->id = startRef;
2925  startNode->flags = DT_NODE_OPEN;
2926  m_openList->push(startNode);
2927 
2928  dtStatus status = DT_SUCCESS;
2929 
2930  int n = 0;
2931 
2932  while (!m_openList->empty())
2933  {
2934  dtNode* bestNode = m_openList->pop();
2935  bestNode->flags &= ~DT_NODE_OPEN;
2936  bestNode->flags |= DT_NODE_CLOSED;
2937 
2938  // Get poly and tile.
2939  // The API input has been cheked already, skip checking internal data.
2940  const dtPolyRef bestRef = bestNode->id;
2941  const dtMeshTile* bestTile = 0;
2942  const dtPoly* bestPoly = 0;
2943  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
2944 
2945  // Get parent poly and tile.
2946  dtPolyRef parentRef = 0;
2947  const dtMeshTile* parentTile = 0;
2948  const dtPoly* parentPoly = 0;
2949  if (bestNode->pidx)
2950  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
2951  if (parentRef)
2952  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
2953 
2954  if (n < maxResult)
2955  {
2956  if (resultRef)
2957  resultRef[n] = bestRef;
2958  if (resultParent)
2959  resultParent[n] = parentRef;
2960  if (resultCost)
2961  resultCost[n] = bestNode->total;
2962 
2963  ++n;
2964  }
2965  else
2966  {
2967  status |= DT_BUFFER_TOO_SMALL;
2968  }
2969 
2970  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
2971  {
2972  const dtLink* link = &bestTile->links[i];
2973  dtPolyRef neighbourRef = link->ref;
2974  // Skip invalid neighbours and do not follow back to parent.
2975  if (!neighbourRef || neighbourRef == parentRef)
2976  continue;
2977 
2978  // Expand to neighbour
2979  const dtMeshTile* neighbourTile = 0;
2980  const dtPoly* neighbourPoly = 0;
2981  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
2982 
2983  // Do not advance if the polygon is excluded by the filter.
2984  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
2985  continue;
2986 
2987  // Find edge and calc distance to the edge.
2988  float va[3], vb[3];
2989  if (!getPortalPoints(bestRef, bestPoly, bestTile, neighbourRef, neighbourPoly, neighbourTile, va, vb))
2990  continue;
2991 
2992  // If the poly is not touching the edge to the next polygon, skip the connection it.
2993  float tmin, tmax;
2994  int segMin, segMax;
2995  if (!dtIntersectSegmentPoly2D(va, vb, verts, nverts, tmin, tmax, segMin, segMax))
2996  continue;
2997  if (tmin > 1.0f || tmax < 0.0f)
2998  continue;
2999 
3000  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
3001  if (!neighbourNode)
3002  {
3003  status |= DT_OUT_OF_NODES;
3004  continue;
3005  }
3006 
3007  if (neighbourNode->flags & DT_NODE_CLOSED)
3008  continue;
3009 
3010  // Cost
3011  if (neighbourNode->flags == 0)
3012  dtVlerp(neighbourNode->pos, va, vb, 0.5f);
3013 
3014  float cost = filter->getCost(
3015  bestNode->pos, neighbourNode->pos,
3016  parentRef, parentTile, parentPoly,
3017  bestRef, bestTile, bestPoly,
3018  neighbourRef, neighbourTile, neighbourPoly);
3019 
3020  const float total = bestNode->total + cost;
3021 
3022  // The node is already in open list and the new result is worse, skip.
3023  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
3024  continue;
3025 
3026  neighbourNode->id = neighbourRef;
3027  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
3028  neighbourNode->total = total;
3029 
3030  if (neighbourNode->flags & DT_NODE_OPEN)
3031  {
3032  m_openList->modify(neighbourNode);
3033  }
3034  else
3035  {
3036  neighbourNode->flags = DT_NODE_OPEN;
3037  m_openList->push(neighbourNode);
3038  }
3039  }
3040  }
3041 
3042  *resultCount = n;
3043 
3044  return status;
3045 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
bool empty() const
Definition: DetourNode.h:144
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
void clear()
Definition: DetourNode.h:114
#define dtAssert(expression)
Definition: DetourAssert.h:47
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
Definition: DetourNode.h:36
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:129
float pos[3]
Position of the node.
Definition: DetourNode.h:38
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
Definition: DetourNode.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
bool dtIntersectSegmentPoly2D(const float *p0, const float *p1, const float *verts, int nverts, float &tmin, float &tmax, int &segMin, int &segMax)
Definition: DetourCommon.cpp:110
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
void dtVadd(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:129
static const unsigned int DT_OUT_OF_NODES
Definition: DetourStatus.h:36
dtNode * pop()
Definition: DetourNode.h:118
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
Definition: DetourNavMesh.h:162
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
float cost
Cost from previous node to current node.
Definition: DetourNode.h:39
void modify(dtNode *node)
Definition: DetourNode.h:132
void dtVscale(float *dest, const float *v, const float t)
Definition: DetourCommon.h:151
Definition: DetourNavMesh.h:288
float total
Cost up to the node.
Definition: DetourNode.h:40
void clear()
Definition: DetourNode.cpp:83
float getCost(const float *pa, const float *pb, const dtPolyRef prevRef, const dtMeshTile *prevTile, const dtPoly *prevPoly, const dtPolyRef curRef, const dtMeshTile *curTile, const dtPoly *curPoly, const dtPolyRef nextRef, const dtMeshTile *nextTile, const dtPoly *nextPoly) const
Definition: DetourNavMeshQuery.cpp:94
void push(dtNode *node)
Definition: DetourNode.h:126
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ findRandomPoint()

dtStatus dtNavMeshQuery::findRandomPoint ( const dtQueryFilter filter,
float(*)()  frand,
dtPolyRef randomRef,
float *  randomPt 
) const

Returns random location on navmesh. Polygons are chosen weighted by area. The search runs in linear related to number of polygon.

Parameters
[in]filterThe polygon filter to apply to the query.
[in]frandFunction returning a random number [0..1).
[out]randomRefThe reference id of the random location.
[out]randomPtThe random location.
Returns
The status flags for the query.
223 {
224  dtAssert(m_nav);
225 
226  // Randomly pick one tile. Assume that all tiles cover roughly the same area.
227  const dtMeshTile* tile = 0;
228  float tsum = 0.0f;
229  for (int i = 0; i < m_nav->getMaxTiles(); i++)
230  {
231  const dtMeshTile* t = m_nav->getTile(i);
232  if (!t || !t->header) continue;
233 
234  // Choose random tile using reservoi sampling.
235  const float area = 1.0f; // Could be tile area too.
236  tsum += area;
237  const float u = frand();
238  if (u*tsum <= area)
239  tile = t;
240  }
241  if (!tile)
242  return DT_FAILURE;
243 
244  // Randomly pick one polygon weighted by polygon area.
245  const dtPoly* poly = 0;
246  dtPolyRef polyRef = 0;
247  const dtPolyRef base = m_nav->getPolyRefBase(tile);
248 
249  float areaSum = 0.0f;
250  for (int i = 0; i < tile->header->polyCount; ++i)
251  {
252  const dtPoly* p = &tile->polys[i];
253  // Do not return off-mesh connection polygons.
254  if (p->getType() != DT_POLYTYPE_GROUND)
255  continue;
256  // Must pass filter
257  const dtPolyRef ref = base | (dtPolyRef)i;
258  if (!filter->passFilter(ref, tile, p))
259  continue;
260 
261  // Calc area of the polygon.
262  float polyArea = 0.0f;
263  for (int j = 2; j < p->vertCount; ++j)
264  {
265  const float* va = &tile->verts[p->verts[0]*3];
266  const float* vb = &tile->verts[p->verts[j-1]*3];
267  const float* vc = &tile->verts[p->verts[j]*3];
268  polyArea += dtTriArea2D(va,vb,vc);
269  }
270 
271  // Choose random polygon weighted by area, using reservoi sampling.
272  areaSum += polyArea;
273  const float u = frand();
274  if (u*areaSum <= polyArea)
275  {
276  poly = p;
277  polyRef = ref;
278  }
279  }
280 
281  if (!poly)
282  return DT_FAILURE;
283 
284  // Randomly pick point on polygon.
285  const float* v = &tile->verts[poly->verts[0]*3];
286  float verts[3*DT_VERTS_PER_POLYGON];
287  float areas[DT_VERTS_PER_POLYGON];
288  dtVcopy(&verts[0*3],v);
289  for (int j = 1; j < poly->vertCount; ++j)
290  {
291  v = &tile->verts[poly->verts[j]*3];
292  dtVcopy(&verts[j*3],v);
293  }
294 
295  const float s = frand();
296  const float t = frand();
297 
298  float pt[3];
299  dtRandomPointInConvexPoly(verts, poly->vertCount, areas, s, t, pt);
300 
301  float h = 0.0f;
302  dtStatus status = getPolyHeight(polyRef, pt, &h);
303  if (dtStatusFailed(status))
304  return status;
305  pt[1] = h;
306 
307  dtVcopy(randomPt, pt);
308  *randomRef = polyRef;
309 
310  return DT_SUCCESS;
311 }
void dtRandomPointInConvexPoly(const float *pts, const int npts, float *areas, const float s, const float t, float *out)
Definition: DetourCommon.cpp:333
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
float dtTriArea2D(const float *a, const float *b, const float *c)
Definition: DetourCommon.h:317
#define dtAssert(expression)
Definition: DetourAssert.h:47
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
const dtMeshTile * getTile(int i) const
Definition: DetourNavMesh.cpp:1117
double frand()
Definition: Vector3.cpp:170
int getMaxTiles() const
Definition: DetourNavMesh.cpp:1107
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int dtStatus
Definition: DetourStatus.h:22
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
dtStatus getPolyHeight(dtPolyRef ref, const float *pos, float *height) const
Definition: DetourNavMeshQuery.cpp:654
The polygon is a standard convex polygon that is part of the surface of the mesh. ...
Definition: DetourNavMesh.h:154
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:73
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ findRandomPointAroundCircle()

dtStatus dtNavMeshQuery::findRandomPointAroundCircle ( dtPolyRef  startRef,
const float *  centerPos,
const float  maxRadius,
const dtQueryFilter filter,
float(*)()  frand,
dtPolyRef randomRef,
float *  randomPt 
) const

Returns random location on navmesh within the reach of specified location. Polygons are chosen weighted by area. The search runs in linear related to number of polygon. The location is not exactly constrained by the circle, but it limits the visited polygons.

Parameters
[in]startRefThe reference id of the polygon where the search starts.
[in]centerPosThe center of the search circle. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[in]frandFunction returning a random number [0..1).
[out]randomRefThe reference id of the random location.
[out]randomPtThe random location. [(x, y, z)]
Returns
The status flags for the query.
316 {
317  dtAssert(m_nav);
320 
321  // Validate input
322  if (!startRef || !m_nav->isValidPolyRef(startRef))
323  return DT_FAILURE | DT_INVALID_PARAM;
324 
325  const dtMeshTile* startTile = 0;
326  const dtPoly* startPoly = 0;
327  m_nav->getTileAndPolyByRefUnsafe(startRef, &startTile, &startPoly);
328  if (!filter->passFilter(startRef, startTile, startPoly))
329  return DT_FAILURE | DT_INVALID_PARAM;
330 
331  m_nodePool->clear();
332  m_openList->clear();
333 
334  dtNode* startNode = m_nodePool->getNode(startRef);
335  dtVcopy(startNode->pos, centerPos);
336  startNode->pidx = 0;
337  startNode->cost = 0;
338  startNode->total = 0;
339  startNode->id = startRef;
340  startNode->flags = DT_NODE_OPEN;
341  m_openList->push(startNode);
342 
343  dtStatus status = DT_SUCCESS;
344 
345  const float radiusSqr = dtSqr(maxRadius);
346  float areaSum = 0.0f;
347 
348  const dtMeshTile* randomTile = 0;
349  const dtPoly* randomPoly = 0;
350  dtPolyRef randomPolyRef = 0;
351 
352  while (!m_openList->empty())
353  {
354  dtNode* bestNode = m_openList->pop();
355  bestNode->flags &= ~DT_NODE_OPEN;
356  bestNode->flags |= DT_NODE_CLOSED;
357 
358  // Get poly and tile.
359  // The API input has been cheked already, skip checking internal data.
360  const dtPolyRef bestRef = bestNode->id;
361  const dtMeshTile* bestTile = 0;
362  const dtPoly* bestPoly = 0;
363  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
364 
365  // Place random locations on on ground.
366  if (bestPoly->getType() == DT_POLYTYPE_GROUND)
367  {
368  // Calc area of the polygon.
369  float polyArea = 0.0f;
370  for (int j = 2; j < bestPoly->vertCount; ++j)
371  {
372  const float* va = &bestTile->verts[bestPoly->verts[0]*3];
373  const float* vb = &bestTile->verts[bestPoly->verts[j-1]*3];
374  const float* vc = &bestTile->verts[bestPoly->verts[j]*3];
375  polyArea += dtTriArea2D(va,vb,vc);
376  }
377  // Choose random polygon weighted by area, using reservoi sampling.
378  areaSum += polyArea;
379  const float u = frand();
380  if (u*areaSum <= polyArea)
381  {
382  randomTile = bestTile;
383  randomPoly = bestPoly;
384  randomPolyRef = bestRef;
385  }
386  }
387 
388 
389  // Get parent poly and tile.
390  dtPolyRef parentRef = 0;
391  const dtMeshTile* parentTile = 0;
392  const dtPoly* parentPoly = 0;
393  if (bestNode->pidx)
394  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
395  if (parentRef)
396  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
397 
398  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
399  {
400  const dtLink* link = &bestTile->links[i];
401  dtPolyRef neighbourRef = link->ref;
402  // Skip invalid neighbours and do not follow back to parent.
403  if (!neighbourRef || neighbourRef == parentRef)
404  continue;
405 
406  // Expand to neighbour
407  const dtMeshTile* neighbourTile = 0;
408  const dtPoly* neighbourPoly = 0;
409  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
410 
411  // Do not advance if the polygon is excluded by the filter.
412  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
413  continue;
414 
415  // Find edge and calc distance to the edge.
416  float va[3], vb[3];
417  if (!getPortalPoints(bestRef, bestPoly, bestTile, neighbourRef, neighbourPoly, neighbourTile, va, vb))
418  continue;
419 
420  // If the circle is not touching the next polygon, skip it.
421  float tseg;
422  float distSqr = dtDistancePtSegSqr2D(centerPos, va, vb, tseg);
423  if (distSqr > radiusSqr)
424  continue;
425 
426  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
427  if (!neighbourNode)
428  {
429  status |= DT_OUT_OF_NODES;
430  continue;
431  }
432 
433  if (neighbourNode->flags & DT_NODE_CLOSED)
434  continue;
435 
436  // Cost
437  if (neighbourNode->flags == 0)
438  dtVlerp(neighbourNode->pos, va, vb, 0.5f);
439 
440  const float total = bestNode->total + dtVdist(bestNode->pos, neighbourNode->pos);
441 
442  // The node is already in open list and the new result is worse, skip.
443  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
444  continue;
445 
446  neighbourNode->id = neighbourRef;
447  neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED);
448  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
449  neighbourNode->total = total;
450 
451  if (neighbourNode->flags & DT_NODE_OPEN)
452  {
453  m_openList->modify(neighbourNode);
454  }
455  else
456  {
457  neighbourNode->flags = DT_NODE_OPEN;
458  m_openList->push(neighbourNode);
459  }
460  }
461  }
462 
463  if (!randomPoly)
464  return DT_FAILURE;
465 
466  // Randomly pick point on polygon.
467  const float* v = &randomTile->verts[randomPoly->verts[0]*3];
468  float verts[3*DT_VERTS_PER_POLYGON];
469  float areas[DT_VERTS_PER_POLYGON];
470  dtVcopy(&verts[0*3],v);
471  for (int j = 1; j < randomPoly->vertCount; ++j)
472  {
473  v = &randomTile->verts[randomPoly->verts[j]*3];
474  dtVcopy(&verts[j*3],v);
475  }
476 
477  const float s = frand();
478  const float t = frand();
479 
480  float pt[3];
481  dtRandomPointInConvexPoly(verts, randomPoly->vertCount, areas, s, t, pt);
482 
483  float h = 0.0f;
484  dtStatus stat = getPolyHeight(randomPolyRef, pt, &h);
485  if (dtStatusFailed(status))
486  return stat;
487  pt[1] = h;
488 
489  dtVcopy(randomPt, pt);
490  *randomRef = randomPolyRef;
491 
492  return DT_SUCCESS;
493 }
void dtRandomPointInConvexPoly(const float *pts, const int npts, float *areas, const float s, const float t, float *out)
Definition: DetourCommon.cpp:333
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
bool empty() const
Definition: DetourNode.h:144
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
void clear()
Definition: DetourNode.h:114
float dtTriArea2D(const float *a, const float *b, const float *c)
Definition: DetourCommon.h:317
#define dtAssert(expression)
Definition: DetourAssert.h:47
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
Definition: DetourNode.h:36
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:218
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:129
double frand()
Definition: Vector3.cpp:170
float pos[3]
Position of the node.
Definition: DetourNode.h:38
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
Definition: DetourNode.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
float dtDistancePtSegSqr2D(const float *pt, const float *p, const float *q, float &t)
Definition: DetourCommon.cpp:170
static const unsigned int DT_OUT_OF_NODES
Definition: DetourStatus.h:36
dtNode * pop()
Definition: DetourNode.h:118
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
Definition: DetourNavMesh.h:162
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
float cost
Cost from previous node to current node.
Definition: DetourNode.h:39
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
void modify(dtNode *node)
Definition: DetourNode.h:132
Definition: DetourNavMesh.h:288
float total
Cost up to the node.
Definition: DetourNode.h:40
void clear()
Definition: DetourNode.cpp:83
dtStatus getPolyHeight(dtPolyRef ref, const float *pos, float *height) const
Definition: DetourNavMeshQuery.cpp:654
The polygon is a standard convex polygon that is part of the surface of the mesh. ...
Definition: DetourNavMesh.h:154
void push(dtNode *node)
Definition: DetourNode.h:126
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:73
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ findStraightPath()

dtStatus dtNavMeshQuery::findStraightPath ( const float *  startPos,
const float *  endPos,
const dtPolyRef path,
const int  pathSize,
float *  straightPath,
unsigned char *  straightPathFlags,
dtPolyRef straightPathRefs,
int *  straightPathCount,
const int  maxStraightPath,
const int  options = 0 
) const

Finds the straight path from the start to the end position within the polygon corridor.

Parameters
[in]startPosPath start position. [(x, y, z)]
[in]endPosPath end position. [(x, y, z)]
[in]pathAn array of polygon references that represent the path corridor.
[in]pathSizeThe number of polygons in the path array.
[out]straightPathPoints describing the straight path. [(x, y, z) * straightPathCount].
[out]straightPathFlagsFlags describing each point. (See: dtStraightPathFlags) [opt]
[out]straightPathRefsThe reference id of the polygon that is being entered at each point. [opt]
[out]straightPathCountThe number of points in the straight path.
[in]maxStraightPathThe maximum number of points the straight path arrays can hold. [Limit: > 0]
[in]optionsQuery options. (see: dtStraightPathOptions)
Returns
The status flags for the query.

This method peforms what is often called 'string pulling'.

The start position is clamped to the first polygon in the path, and the end position is clamped to the last. So the start and end positions should normally be within or very near the first and last polygons respectively.

The returned polygon references represent the reference id of the polygon that is entered at the associated path position. The reference id associated with the end point will always be zero. This allows, for example, matching off-mesh link points to their representative polygons.

If the provided result buffers are too small for the entire result set, they will be filled as far as possible from the start toward the end position.

1824 {
1825  dtAssert(m_nav);
1826 
1827  *straightPathCount = 0;
1828 
1829  if (!maxStraightPath)
1830  return DT_FAILURE | DT_INVALID_PARAM;
1831 
1832  if (!path[0])
1833  return DT_FAILURE | DT_INVALID_PARAM;
1834 
1835  dtStatus stat = 0;
1836 
1837  // TODO: Should this be callers responsibility?
1838  float closestStartPos[3];
1839  if (dtStatusFailed(closestPointOnPolyBoundary(path[0], startPos, closestStartPos)))
1840  return DT_FAILURE | DT_INVALID_PARAM;
1841 
1842  float closestEndPos[3];
1843  if (dtStatusFailed(closestPointOnPolyBoundary(path[pathSize-1], endPos, closestEndPos)))
1844  return DT_FAILURE | DT_INVALID_PARAM;
1845 
1846  // Add start point.
1847  stat = appendVertex(closestStartPos, DT_STRAIGHTPATH_START, path[0],
1848  straightPath, straightPathFlags, straightPathRefs,
1849  straightPathCount, maxStraightPath);
1850  if (stat != DT_IN_PROGRESS)
1851  return stat;
1852 
1853  if (pathSize > 1)
1854  {
1855  float portalApex[3], portalLeft[3], portalRight[3];
1856  dtVcopy(portalApex, closestStartPos);
1857  dtVcopy(portalLeft, portalApex);
1858  dtVcopy(portalRight, portalApex);
1859  int apexIndex = 0;
1860  int leftIndex = 0;
1861  int rightIndex = 0;
1862 
1863  unsigned char leftPolyType = 0;
1864  unsigned char rightPolyType = 0;
1865 
1866  dtPolyRef leftPolyRef = path[0];
1867  dtPolyRef rightPolyRef = path[0];
1868 
1869  for (int i = 0; i < pathSize; ++i)
1870  {
1871  float left[3], right[3];
1872  unsigned char toType;
1873 
1874  if (i+1 < pathSize)
1875  {
1876  unsigned char fromType; // fromType is ignored.
1877 
1878  // Next portal.
1879  if (dtStatusFailed(getPortalPoints(path[i], path[i+1], left, right, fromType, toType)))
1880  {
1881  // Failed to get portal points, in practice this means that path[i+1] is invalid polygon.
1882  // Clamp the end point to path[i], and return the path so far.
1883 
1884  if (dtStatusFailed(closestPointOnPolyBoundary(path[i], endPos, closestEndPos)))
1885  {
1886  // This should only happen when the first polygon is invalid.
1887  return DT_FAILURE | DT_INVALID_PARAM;
1888  }
1889 
1890  // Apeend portals along the current straight path segment.
1892  {
1893  // Ignore status return value as we're just about to return anyway.
1894  appendPortals(apexIndex, i, closestEndPos, path,
1895  straightPath, straightPathFlags, straightPathRefs,
1896  straightPathCount, maxStraightPath, options);
1897  }
1898 
1899  // Ignore status return value as we're just about to return anyway.
1900  appendVertex(closestEndPos, 0, path[i],
1901  straightPath, straightPathFlags, straightPathRefs,
1902  straightPathCount, maxStraightPath);
1903 
1904  return DT_SUCCESS | DT_PARTIAL_RESULT | ((*straightPathCount >= maxStraightPath) ? DT_BUFFER_TOO_SMALL : 0);
1905  }
1906 
1907  // If starting really close the portal, advance.
1908  if (i == 0)
1909  {
1910  float t;
1911  if (dtDistancePtSegSqr2D(portalApex, left, right, t) < dtSqr(0.001f))
1912  continue;
1913  }
1914  }
1915  else
1916  {
1917  // End of the path.
1918  dtVcopy(left, closestEndPos);
1919  dtVcopy(right, closestEndPos);
1920 
1921  toType = DT_POLYTYPE_GROUND;
1922  }
1923 
1924  // Right vertex.
1925  if (dtTriArea2D(portalApex, portalRight, right) <= 0.0f)
1926  {
1927  if (dtVequal(portalApex, portalRight) || dtTriArea2D(portalApex, portalLeft, right) > 0.0f)
1928  {
1929  dtVcopy(portalRight, right);
1930  rightPolyRef = (i+1 < pathSize) ? path[i+1] : 0;
1931  rightPolyType = toType;
1932  rightIndex = i;
1933  }
1934  else
1935  {
1936  // Append portals along the current straight path segment.
1938  {
1939  stat = appendPortals(apexIndex, leftIndex, portalLeft, path,
1940  straightPath, straightPathFlags, straightPathRefs,
1941  straightPathCount, maxStraightPath, options);
1942  if (stat != DT_IN_PROGRESS)
1943  return stat;
1944  }
1945 
1946  dtVcopy(portalApex, portalLeft);
1947  apexIndex = leftIndex;
1948 
1949  unsigned char flags = 0;
1950  if (!leftPolyRef)
1951  flags = DT_STRAIGHTPATH_END;
1952  else if (leftPolyType == DT_POLYTYPE_OFFMESH_CONNECTION)
1954  dtPolyRef ref = leftPolyRef;
1955 
1956  // Append or update vertex
1957  stat = appendVertex(portalApex, flags, ref,
1958  straightPath, straightPathFlags, straightPathRefs,
1959  straightPathCount, maxStraightPath);
1960  if (stat != DT_IN_PROGRESS)
1961  return stat;
1962 
1963  dtVcopy(portalLeft, portalApex);
1964  dtVcopy(portalRight, portalApex);
1965  leftIndex = apexIndex;
1966  rightIndex = apexIndex;
1967 
1968  // Restart
1969  i = apexIndex;
1970 
1971  continue;
1972  }
1973  }
1974 
1975  // Left vertex.
1976  if (dtTriArea2D(portalApex, portalLeft, left) >= 0.0f)
1977  {
1978  if (dtVequal(portalApex, portalLeft) || dtTriArea2D(portalApex, portalRight, left) < 0.0f)
1979  {
1980  dtVcopy(portalLeft, left);
1981  leftPolyRef = (i+1 < pathSize) ? path[i+1] : 0;
1982  leftPolyType = toType;
1983  leftIndex = i;
1984  }
1985  else
1986  {
1987  // Append portals along the current straight path segment.
1989  {
1990  stat = appendPortals(apexIndex, rightIndex, portalRight, path,
1991  straightPath, straightPathFlags, straightPathRefs,
1992  straightPathCount, maxStraightPath, options);
1993  if (stat != DT_IN_PROGRESS)
1994  return stat;
1995  }
1996 
1997  dtVcopy(portalApex, portalRight);
1998  apexIndex = rightIndex;
1999 
2000  unsigned char flags = 0;
2001  if (!rightPolyRef)
2002  flags = DT_STRAIGHTPATH_END;
2003  else if (rightPolyType == DT_POLYTYPE_OFFMESH_CONNECTION)
2005  dtPolyRef ref = rightPolyRef;
2006 
2007  // Append or update vertex
2008  stat = appendVertex(portalApex, flags, ref,
2009  straightPath, straightPathFlags, straightPathRefs,
2010  straightPathCount, maxStraightPath);
2011  if (stat != DT_IN_PROGRESS)
2012  return stat;
2013 
2014  dtVcopy(portalLeft, portalApex);
2015  dtVcopy(portalRight, portalApex);
2016  leftIndex = apexIndex;
2017  rightIndex = apexIndex;
2018 
2019  // Restart
2020  i = apexIndex;
2021 
2022  continue;
2023  }
2024  }
2025  }
2026 
2027  // Append portals along the current straight path segment.
2029  {
2030  stat = appendPortals(apexIndex, pathSize-1, closestEndPos, path,
2031  straightPath, straightPathFlags, straightPathRefs,
2032  straightPathCount, maxStraightPath, options);
2033  if (stat != DT_IN_PROGRESS)
2034  return stat;
2035  }
2036  }
2037 
2038  // Ignore status return value as we're just about to return anyway.
2039  appendVertex(closestEndPos, DT_STRAIGHTPATH_END, 0,
2040  straightPath, straightPathFlags, straightPathRefs,
2041  straightPathCount, maxStraightPath);
2042 
2043  return DT_SUCCESS | ((*straightPathCount >= maxStraightPath) ? DT_BUFFER_TOO_SMALL : 0);
2044 }
dtStatus appendVertex(const float *pos, const unsigned char flags, const dtPolyRef ref, float *straightPath, unsigned char *straightPathFlags, dtPolyRef *straightPathRefs, int *straightPathCount, const int maxStraightPath) const
Definition: DetourNavMeshQuery.cpp:1716
float dtTriArea2D(const float *a, const float *b, const float *c)
Definition: DetourCommon.h:317
#define dtAssert(expression)
Definition: DetourAssert.h:47
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
The vertex is the start position in the path.
Definition: DetourNavMesh.h:120
float dtDistancePtSegSqr2D(const float *pt, const float *p, const float *q, float &t)
Definition: DetourCommon.cpp:170
The vertex is the end position in the path.
Definition: DetourNavMesh.h:121
Add a vertex at every polygon edge crossing.
Definition: DetourNavMesh.h:129
static const unsigned int DT_PARTIAL_RESULT
Definition: DetourStatus.h:37
size_t const pathSize
Definition: zone_dun_morogh_area_coldridge_valley.cpp:253
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
bool left(const int *a, const int *b, const int *c)
Definition: RecastContour.cpp:487
bool dtVequal(const float *p0, const float *p1)
Definition: DetourCommon.h:279
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
Add a vertex at every polygon edge crossing where area changes.
Definition: DetourNavMesh.h:128
T dtSqr(T a)
Definition: DetourCommon.h:68
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
dtStatus appendPortals(const int startIdx, const int endIdx, const float *endPos, const dtPolyRef *path, float *straightPath, unsigned char *straightPathFlags, dtPolyRef *straightPathRefs, int *straightPathCount, const int maxStraightPath, const int options) const
Definition: DetourNavMeshQuery.cpp:1753
uint8 flags
Definition: DisableMgr.cpp:47
static const unsigned int DT_IN_PROGRESS
Definition: DetourStatus.h:27
The vertex is the start of an off-mesh connection.
Definition: DetourNavMesh.h:122
dtStatus closestPointOnPolyBoundary(dtPolyRef ref, const float *pos, float *closest) const
Definition: DetourNavMeshQuery.cpp:602
The polygon is a standard convex polygon that is part of the surface of the mesh. ...
Definition: DetourNavMesh.h:154
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getAttachedNavMesh()

const dtNavMesh* dtNavMeshQuery::getAttachedNavMesh ( ) const
inline

Gets the navigation mesh the query object is using.

Returns
The navigation mesh the query object is using.
506 { return m_nav; }
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
+ Here is the call graph for this function:

◆ getEdgeMidPoint() [1/2]

dtStatus dtNavMeshQuery::getEdgeMidPoint ( dtPolyRef  from,
dtPolyRef  to,
float *  mid 
) const
private

Returns edge mid point between two polygons.

2360 {
2361  float left[3], right[3];
2362  unsigned char fromType, toType;
2363  if (dtStatusFailed(getPortalPoints(from, to, left,right, fromType, toType)))
2364  return DT_FAILURE | DT_INVALID_PARAM;
2365  mid[0] = (left[0]+right[0])*0.5f;
2366  mid[1] = (left[1]+right[1])*0.5f;
2367  mid[2] = (left[2]+right[2])*0.5f;
2368  return DT_SUCCESS;
2369 }
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
bool left(const int *a, const int *b, const int *c)
Definition: RecastContour.cpp:487
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getEdgeMidPoint() [2/2]

dtStatus dtNavMeshQuery::getEdgeMidPoint ( dtPolyRef  from,
const dtPoly fromPoly,
const dtMeshTile fromTile,
dtPolyRef  to,
const dtPoly toPoly,
const dtMeshTile toTile,
float *  mid 
) const
private
2374 {
2375  float left[3], right[3];
2376  if (dtStatusFailed(getPortalPoints(from, fromPoly, fromTile, to, toPoly, toTile, left, right)))
2377  return DT_FAILURE | DT_INVALID_PARAM;
2378  mid[0] = (left[0]+right[0])*0.5f;
2379  mid[1] = (left[1]+right[1])*0.5f;
2380  mid[2] = (left[2]+right[2])*0.5f;
2381  return DT_SUCCESS;
2382 }
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
bool left(const int *a, const int *b, const int *c)
Definition: RecastContour.cpp:487
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ getNodePool()

class dtNodePool* dtNavMeshQuery::getNodePool ( ) const
inline

Gets the node pool.

Returns
The node pool.
502 { return m_nodePool; }
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561

◆ getPathFromDijkstraSearch()

dtStatus dtNavMeshQuery::getPathFromDijkstraSearch ( dtPolyRef  endRef,
dtPolyRef path,
int *  pathCount,
int  maxPath 
) const

Gets a path from the explored nodes in the previous search.

Parameters
[in]endRefThe reference id of the end polygon.
[out]pathAn ordered list of polygon references representing the path. (Start to end.) [(polyRef) * pathCount]
[out]pathCountThe number of polygons returned in the path array.
[in]maxPathThe maximum number of polygons the path array can hold. [Limit: >= 0]
Returns
The status flags. Returns DT_FAILURE | DT_INVALID_PARAM if any parameter is wrong, or if endRef was not explored in the previous search. Returns DT_SUCCESS | DT_BUFFER_TOO_SMALL if path cannot contain the entire path. In this case it is filled to capacity with a partial path. Otherwise returns DT_SUCCESS.
Remarks
The result of this function depends on the state of the query object. For that reason it should only be used immediately after one of the two Dijkstra searches, findPolysAroundCircle or findPolysAroundShape.
3048 {
3049  if (!m_nav->isValidPolyRef(endRef) || !path || !pathCount || maxPath < 0)
3050  return DT_FAILURE | DT_INVALID_PARAM;
3051 
3052  *pathCount = 0;
3053 
3054  dtNode* endNode;
3055  if (m_nodePool->findNodes(endRef, &endNode, 1) != 1 ||
3056  (endNode->flags & DT_NODE_CLOSED) == 0)
3057  return DT_FAILURE | DT_INVALID_PARAM;
3058 
3059  return getPathToNode(endNode, path, pathCount, maxPath);
3060 }
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
dtStatus getPathToNode(struct dtNode *endNode, dtPolyRef *path, int *pathCount, int maxPath) const
Definition: DetourNavMeshQuery.cpp:1204
Definition: DetourNode.h:36
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned int findNodes(dtPolyRef id, dtNode **nodes, const int maxNodes)
Definition: DetourNode.cpp:89
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
Definition: DetourNode.h:27
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ getPathToNode()

dtStatus dtNavMeshQuery::getPathToNode ( struct dtNode endNode,
dtPolyRef path,
int *  pathCount,
int  maxPath 
) const
private
1205 {
1206  // Find the length of the entire path.
1207  dtNode* curNode = endNode;
1208  int length = 0;
1209  do
1210  {
1211  length++;
1212  curNode = m_nodePool->getNodeAtIdx(curNode->pidx);
1213  } while (curNode);
1214 
1215  // If the path cannot be fully stored then advance to the last node we will be able to store.
1216  curNode = endNode;
1217  int writeCount;
1218  for (writeCount = length; writeCount > maxPath; writeCount--)
1219  {
1220  dtAssert(curNode);
1221 
1222  curNode = m_nodePool->getNodeAtIdx(curNode->pidx);
1223  }
1224 
1225  // Write path
1226  for (int i = writeCount - 1; i >= 0; i--)
1227  {
1228  dtAssert(curNode);
1229 
1230  path[i] = curNode->id;
1231  curNode = m_nodePool->getNodeAtIdx(curNode->pidx);
1232  }
1233 
1234  dtAssert(!curNode);
1235 
1236  *pathCount = dtMin(length, maxPath);
1237 
1238  if (length > maxPath)
1240 
1241  return DT_SUCCESS;
1242 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
Definition: DetourNode.h:36
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
float length(float v)
Definition: vectorMath.h:208
T dtMin(T a, T b)
Definition: DetourCommon.h:52
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getPolyHeight()

dtStatus dtNavMeshQuery::getPolyHeight ( dtPolyRef  ref,
const float *  pos,
float *  height 
) const

Gets the height of the polygon at the provided position using the height detail. (Most accurate.)

Parameters
[in]refThe reference id of the polygon.
[in]posA position within the xz-bounds of the polygon. [(x, y, z)]
[out]heightThe height at the surface of the polygon.
Returns
The status flags for the query.

Will return DT_FAILURE if the provided position is outside the xz-bounds of the polygon.

655 {
656  dtAssert(m_nav);
657 
658  const dtMeshTile* tile = 0;
659  const dtPoly* poly = 0;
660  if (dtStatusFailed(m_nav->getTileAndPolyByRef(ref, &tile, &poly)))
661  return DT_FAILURE | DT_INVALID_PARAM;
662 
664  {
665  const float* v0 = &tile->verts[poly->verts[0]*3];
666  const float* v1 = &tile->verts[poly->verts[1]*3];
667  const float d0 = dtVdist2D(pos, v0);
668  const float d1 = dtVdist2D(pos, v1);
669  const float u = d0 / (d0+d1);
670  if (height)
671  *height = v0[1] + (v1[1] - v0[1]) * u;
672  return DT_SUCCESS;
673  }
674  else
675  {
676  const unsigned int ip = (unsigned int)(poly - tile->polys);
677  const dtPolyDetail* pd = &tile->detailMeshes[ip];
678  for (int j = 0; j < pd->triCount; ++j)
679  {
680  const unsigned char* t = &tile->detailTris[(pd->triBase+j)*4];
681  const float* v[3];
682  for (int k = 0; k < 3; ++k)
683  {
684  if (t[k] < poly->vertCount)
685  v[k] = &tile->verts[poly->verts[t[k]]*3];
686  else
687  v[k] = &tile->detailVerts[(pd->vertBase+(t[k]-poly->vertCount))*3];
688  }
689  float h;
690  if (dtClosestHeightPointTriangle(pos, v[0], v[1], v[2], h))
691  {
692  if (height)
693  *height = h;
694  return DT_SUCCESS;
695  }
696  }
697  }
698 
699  return DT_FAILURE | DT_INVALID_PARAM;
700 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
Defines the location of detail sub-mesh data within a dtMeshTile.
Definition: DetourNavMesh.h:198
unsigned char triCount
The number of triangles in the sub-mesh.
Definition: DetourNavMesh.h:203
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1128
unsigned int vertBase
The offset of the vertices in the dtMeshTile::detailVerts array.
Definition: DetourNavMesh.h:200
float dtVdist2D(const float *v1, const float *v2)
Definition: DetourCommon.h:244
Definition: DetourNavMesh.h:162
bool dtClosestHeightPointTriangle(const float *p, const float *a, const float *b, const float *c, float &h)
Definition: DetourCommon.cpp:204
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
float * detailVerts
The detail mesh&#39;s unique vertices. [(x, y, z) * dtMeshHeader::detailVertCount].
Definition: DetourNavMesh.h:300
unsigned char * detailTris
The detail mesh&#39;s triangles. [(vertA, vertB, vertC) * dtMeshHeader::detailTriCount].
Definition: DetourNavMesh.h:303
dtPolyDetail * detailMeshes
The tile&#39;s detail sub-meshes. [Size: dtMeshHeader::detailMeshCount].
Definition: DetourNavMesh.h:297
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
unsigned int triBase
The offset of the triangles in the dtMeshTile::detailTris array.
Definition: DetourNavMesh.h:201
Definition: DetourNavMesh.h:288
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getPolyWallSegments()

dtStatus dtNavMeshQuery::getPolyWallSegments ( dtPolyRef  ref,
const dtQueryFilter filter,
float *  segmentVerts,
dtPolyRef segmentRefs,
int *  segmentCount,
const int  maxSegments 
) const

Returns the segments for the specified polygon, optionally including portals.

Parameters
[in]refThe reference id of the polygon.
[in]filterThe polygon filter to apply to the query.
[out]segmentVertsThe segments. [(ax, ay, az, bx, by, bz) * segmentCount]
[out]segmentRefsThe reference ids of each segment's neighbor polygon. Or zero if the segment is a wall. [opt] [(parentRef) * segmentCount]
[out]segmentCountThe number of segments returned.
[in]maxSegmentsThe maximum number of segments the result arrays can hold.
Returns
The status flags for the query.

If the segmentRefs parameter is provided, then all polygon segments will be returned. Otherwise only the wall segments are returned.

A segment that is normally a portal will be included in the result set as a wall if the filter results in the neighbor polygon becoomming impassable.

The segmentVerts and segmentRefs buffers should normally be sized for the maximum segments per polygon of the source navigation mesh.

3302 {
3303  dtAssert(m_nav);
3304 
3305  *segmentCount = 0;
3306 
3307  const dtMeshTile* tile = 0;
3308  const dtPoly* poly = 0;
3309  if (dtStatusFailed(m_nav->getTileAndPolyByRef(ref, &tile, &poly)))
3310  return DT_FAILURE | DT_INVALID_PARAM;
3311 
3312  int n = 0;
3313  static const int MAX_INTERVAL = 16;
3314  dtSegInterval ints[MAX_INTERVAL];
3315  int nints;
3316 
3317  const bool storePortals = segmentRefs != 0;
3318 
3319  dtStatus status = DT_SUCCESS;
3320 
3321  for (int i = 0, j = (int)poly->vertCount-1; i < (int)poly->vertCount; j = i++)
3322  {
3323  // Skip non-solid edges.
3324  nints = 0;
3325  if (poly->neis[j] & DT_EXT_LINK)
3326  {
3327  // Tile border.
3328  for (unsigned int k = poly->firstLink; k != DT_NULL_LINK; k = tile->links[k].next)
3329  {
3330  const dtLink* link = &tile->links[k];
3331  if (link->edge == j)
3332  {
3333  if (link->ref != 0)
3334  {
3335  const dtMeshTile* neiTile = 0;
3336  const dtPoly* neiPoly = 0;
3337  m_nav->getTileAndPolyByRefUnsafe(link->ref, &neiTile, &neiPoly);
3338  if (filter->passFilter(link->ref, neiTile, neiPoly))
3339  {
3340  insertInterval(ints, nints, MAX_INTERVAL, link->bmin, link->bmax, link->ref);
3341  }
3342  }
3343  }
3344  }
3345  }
3346  else
3347  {
3348  // Internal edge
3349  dtPolyRef neiRef = 0;
3350  if (poly->neis[j])
3351  {
3352  const unsigned int idx = (unsigned int)(poly->neis[j]-1);
3353  neiRef = m_nav->getPolyRefBase(tile) | idx;
3354  if (!filter->passFilter(neiRef, tile, &tile->polys[idx]))
3355  neiRef = 0;
3356  }
3357 
3358  // If the edge leads to another polygon and portals are not stored, skip.
3359  if (neiRef != 0 && !storePortals)
3360  continue;
3361 
3362  if (n < maxSegments)
3363  {
3364  const float* vj = &tile->verts[poly->verts[j]*3];
3365  const float* vi = &tile->verts[poly->verts[i]*3];
3366  float* seg = &segmentVerts[n*6];
3367  dtVcopy(seg+0, vj);
3368  dtVcopy(seg+3, vi);
3369  if (segmentRefs)
3370  segmentRefs[n] = neiRef;
3371  n++;
3372  }
3373  else
3374  {
3375  status |= DT_BUFFER_TOO_SMALL;
3376  }
3377 
3378  continue;
3379  }
3380 
3381  // Add sentinels
3382  insertInterval(ints, nints, MAX_INTERVAL, -1, 0, 0);
3383  insertInterval(ints, nints, MAX_INTERVAL, 255, 256, 0);
3384 
3385  // Store segments.
3386  const float* vj = &tile->verts[poly->verts[j]*3];
3387  const float* vi = &tile->verts[poly->verts[i]*3];
3388  for (int k = 1; k < nints; ++k)
3389  {
3390  // Portal segment.
3391  if (storePortals && ints[k].ref)
3392  {
3393  const float tmin = ints[k].tmin/255.0f;
3394  const float tmax = ints[k].tmax/255.0f;
3395  if (n < maxSegments)
3396  {
3397  float* seg = &segmentVerts[n*6];
3398  dtVlerp(seg+0, vj,vi, tmin);
3399  dtVlerp(seg+3, vj,vi, tmax);
3400  if (segmentRefs)
3401  segmentRefs[n] = ints[k].ref;
3402  n++;
3403  }
3404  else
3405  {
3406  status |= DT_BUFFER_TOO_SMALL;
3407  }
3408  }
3409 
3410  // Wall segment.
3411  const int imin = ints[k-1].tmax;
3412  const int imax = ints[k].tmin;
3413  if (imin != imax)
3414  {
3415  const float tmin = imin/255.0f;
3416  const float tmax = imax/255.0f;
3417  if (n < maxSegments)
3418  {
3419  float* seg = &segmentVerts[n*6];
3420  dtVlerp(seg+0, vj,vi, tmin);
3421  dtVlerp(seg+3, vj,vi, tmax);
3422  if (segmentRefs)
3423  segmentRefs[n] = 0;
3424  n++;
3425  }
3426  else
3427  {
3428  status |= DT_BUFFER_TOO_SMALL;
3429  }
3430  }
3431  }
3432  }
3433 
3434  *segmentCount = n;
3435 
3436  return status;
3437 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
static void insertInterval(dtSegInterval *ints, int &nints, const int maxInts, const short tmin, const short tmax, const dtPolyRef ref)
Definition: DetourNavMeshQuery.cpp:3266
#define dtAssert(expression)
Definition: DetourAssert.h:47
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
short tmax
Definition: DetourNavMeshQuery.cpp:3263
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1128
unsigned short neis[DT_VERTS_PER_POLYGON]
Packed data representing neighbor polygons references and flags for each edge.
Definition: DetourNavMesh.h:172
Definition: DetourNavMesh.h:162
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:97
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
short tmin
Definition: DetourNavMeshQuery.cpp:3263
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
dtPolyRef ref
Definition: DetourNavMeshQuery.cpp:3262
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
Definition: DetourNavMeshQuery.cpp:3260
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ getPortalPoints() [1/2]

dtStatus dtNavMeshQuery::getPortalPoints ( dtPolyRef  from,
dtPolyRef  to,
float *  left,
float *  right,
unsigned char &  fromType,
unsigned char &  toType 
) const
private

Returns portal points between two polygons.

2266 {
2267  dtAssert(m_nav);
2268 
2269  const dtMeshTile* fromTile = 0;
2270  const dtPoly* fromPoly = 0;
2271  if (dtStatusFailed(m_nav->getTileAndPolyByRef(from, &fromTile, &fromPoly)))
2272  return DT_FAILURE | DT_INVALID_PARAM;
2273  fromType = fromPoly->getType();
2274 
2275  const dtMeshTile* toTile = 0;
2276  const dtPoly* toPoly = 0;
2277  if (dtStatusFailed(m_nav->getTileAndPolyByRef(to, &toTile, &toPoly)))
2278  return DT_FAILURE | DT_INVALID_PARAM;
2279  toType = toPoly->getType();
2280 
2281  return getPortalPoints(from, fromPoly, fromTile, to, toPoly, toTile, left, right);
2282 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1128
dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float *left, float *right, unsigned char &fromType, unsigned char &toType) const
Returns portal points between two polygons.
Definition: DetourNavMeshQuery.cpp:2264
Definition: DetourNavMesh.h:162
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
bool left(const int *a, const int *b, const int *c)
Definition: RecastContour.cpp:487
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
Definition: DetourNavMesh.h:288
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getPortalPoints() [2/2]

dtStatus dtNavMeshQuery::getPortalPoints ( dtPolyRef  from,
const dtPoly fromPoly,
const dtMeshTile fromTile,
dtPolyRef  to,
const dtPoly toPoly,
const dtMeshTile toTile,
float *  left,
float *  right 
) const
private
2288 {
2289  // Find the link that points to the 'to' polygon.
2290  const dtLink* link = 0;
2291  for (unsigned int i = fromPoly->firstLink; i != DT_NULL_LINK; i = fromTile->links[i].next)
2292  {
2293  if (fromTile->links[i].ref == to)
2294  {
2295  link = &fromTile->links[i];
2296  break;
2297  }
2298  }
2299  if (!link)
2300  return DT_FAILURE | DT_INVALID_PARAM;
2301 
2302  // Handle off-mesh connections.
2303  if (fromPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
2304  {
2305  // Find link that points to first vertex.
2306  for (unsigned int i = fromPoly->firstLink; i != DT_NULL_LINK; i = fromTile->links[i].next)
2307  {
2308  if (fromTile->links[i].ref == to)
2309  {
2310  const int v = fromTile->links[i].edge;
2311  dtVcopy(left, &fromTile->verts[fromPoly->verts[v]*3]);
2312  dtVcopy(right, &fromTile->verts[fromPoly->verts[v]*3]);
2313  return DT_SUCCESS;
2314  }
2315  }
2316  return DT_FAILURE | DT_INVALID_PARAM;
2317  }
2318 
2319  if (toPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
2320  {
2321  for (unsigned int i = toPoly->firstLink; i != DT_NULL_LINK; i = toTile->links[i].next)
2322  {
2323  if (toTile->links[i].ref == from)
2324  {
2325  const int v = toTile->links[i].edge;
2326  dtVcopy(left, &toTile->verts[toPoly->verts[v]*3]);
2327  dtVcopy(right, &toTile->verts[toPoly->verts[v]*3]);
2328  return DT_SUCCESS;
2329  }
2330  }
2331  return DT_FAILURE | DT_INVALID_PARAM;
2332  }
2333 
2334  // Find portal vertices.
2335  const int v0 = fromPoly->verts[link->edge];
2336  const int v1 = fromPoly->verts[(link->edge+1) % (int)fromPoly->vertCount];
2337  dtVcopy(left, &fromTile->verts[v0*3]);
2338  dtVcopy(right, &fromTile->verts[v1*3]);
2339 
2340  // If the link is at tile boundary, dtClamp the vertices to
2341  // the link width.
2342  if (link->side != 0xff)
2343  {
2344  // Unpack portal limits.
2345  if (link->bmin != 0 || link->bmax != 255)
2346  {
2347  const float s = 1.0f/255.0f;
2348  const float tmin = link->bmin*s;
2349  const float tmax = link->bmax*s;
2350  dtVlerp(left, &fromTile->verts[v0*3], &fromTile->verts[v1*3], tmin);
2351  dtVlerp(right, &fromTile->verts[v0*3], &fromTile->verts[v1*3], tmax);
2352  }
2353  }
2354 
2355  return DT_SUCCESS;
2356 }
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
bool left(const int *a, const int *b, const int *c)
Definition: RecastContour.cpp:487
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ init()

dtStatus dtNavMeshQuery::init ( const dtNavMesh nav,
const int  maxNodes 
)

Initializes the query object.

Parameters
[in]navPointer to the dtNavMesh object to use for all queries.
[in]maxNodesMaximum number of search nodes. [Limits: 0 < value <= 65535]
Returns
The status flags for the query.

Must be the first function called after construction, before other functions are used.

This function can be used multiple times.

167 {
168  if (maxNodes > DT_NULL_IDX || maxNodes > (1 << DT_NODE_PARENT_BITS) - 1)
169  return DT_FAILURE | DT_INVALID_PARAM;
170 
171  m_nav = nav;
172 
173  if (!m_nodePool || m_nodePool->getMaxNodes() < maxNodes)
174  {
175  if (m_nodePool)
176  {
179  m_nodePool = 0;
180  }
181  m_nodePool = new (dtAlloc(sizeof(dtNodePool), DT_ALLOC_PERM)) dtNodePool(maxNodes, dtNextPow2(maxNodes/4));
182  if (!m_nodePool)
183  return DT_FAILURE | DT_OUT_OF_MEMORY;
184  }
185  else
186  {
187  m_nodePool->clear();
188  }
189 
190  if (!m_tinyNodePool)
191  {
192  m_tinyNodePool = new (dtAlloc(sizeof(dtNodePool), DT_ALLOC_PERM)) dtNodePool(64, 32);
193  if (!m_tinyNodePool)
194  return DT_FAILURE | DT_OUT_OF_MEMORY;
195  }
196  else
197  {
199  }
200 
201  if (!m_openList || m_openList->getCapacity() < maxNodes)
202  {
203  if (m_openList)
204  {
207  m_openList = 0;
208  }
209  m_openList = new (dtAlloc(sizeof(dtNodeQueue), DT_ALLOC_PERM)) dtNodeQueue(maxNodes);
210  if (!m_openList)
211  return DT_FAILURE | DT_OUT_OF_MEMORY;
212  }
213  else
214  {
215  m_openList->clear();
216  }
217 
218  return DT_SUCCESS;
219 }
void clear()
Definition: DetourNode.h:114
int getCapacity() const
Definition: DetourNode.h:152
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
void * dtAlloc(size_t size, dtAllocHint hint)
Definition: DetourAlloc.cpp:41
~dtNodeQueue()
Definition: DetourNode.cpp:167
Memory persist after a function call.
Definition: DetourAlloc.h:28
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
static const int DT_NODE_PARENT_BITS
Definition: DetourNode.h:34
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
Definition: DetourNode.h:108
~dtNodePool()
Definition: DetourNode.cpp:76
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
unsigned int dtNextPow2(unsigned int v)
Definition: DetourCommon.h:418
static const dtNodeIndex DT_NULL_IDX
Definition: DetourNode.h:32
Definition: DetourNode.h:49
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:560
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
int getMaxNodes() const
Definition: DetourNode.h:88
void clear()
Definition: DetourNode.cpp:83
static const unsigned int DT_OUT_OF_MEMORY
Definition: DetourStatus.h:33
void dtFree(void *ptr)
Definition: DetourAlloc.cpp:46
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ initSlicedFindPath()

dtStatus dtNavMeshQuery::initSlicedFindPath ( dtPolyRef  startRef,
dtPolyRef  endRef,
const float *  startPos,
const float *  endPos,
const dtQueryFilter filter,
const unsigned int  options = 0 
)

Intializes a sliced path query.

Parameters
[in]startRefThe refrence id of the start polygon.
[in]endRefThe reference id of the end polygon.
[in]startPosA position within the start polygon. [(x, y, z)]
[in]endPosA position within the end polygon. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[in]optionsquery options (see: dtFindPathOptions)
Returns
The status flags for the query.
Warning
Calling any non-slice methods before calling finalizeSlicedFindPath() or finalizeSlicedFindPathPartial() may result in corrupted data!

The filter pointer is stored and used for the duration of the sliced path query.

1256 {
1257  dtAssert(m_nav);
1260 
1261  // Init path state.
1262  memset(&m_query, 0, sizeof(dtQueryData));
1264  m_query.startRef = startRef;
1265  m_query.endRef = endRef;
1266  dtVcopy(m_query.startPos, startPos);
1267  dtVcopy(m_query.endPos, endPos);
1268  m_query.filter = filter;
1269  m_query.options = options;
1270  m_query.raycastLimitSqr = FLT_MAX;
1271 
1272  if (!startRef || !endRef)
1273  return DT_FAILURE | DT_INVALID_PARAM;
1274 
1275  // Validate input
1276  if (!m_nav->isValidPolyRef(startRef) || !m_nav->isValidPolyRef(endRef))
1277  return DT_FAILURE | DT_INVALID_PARAM;
1278 
1279  // trade quality with performance?
1280  if (options & DT_FINDPATH_ANY_ANGLE)
1281  {
1282  // limiting to several times the character radius yields nice results. It is not sensitive
1283  // so it is enough to compute it from the first tile.
1284  const dtMeshTile* tile = m_nav->getTileByRef(startRef);
1285  float agentRadius = tile->header->walkableRadius;
1287  }
1288 
1289  if (startRef == endRef)
1290  {
1292  return DT_SUCCESS;
1293  }
1294 
1295  m_nodePool->clear();
1296  m_openList->clear();
1297 
1298  dtNode* startNode = m_nodePool->getNode(startRef);
1299  dtVcopy(startNode->pos, startPos);
1300  startNode->pidx = 0;
1301  startNode->cost = 0;
1302  startNode->total = dtVdist(startPos, endPos) * H_SCALE;
1303  startNode->id = startRef;
1304  startNode->flags = DT_NODE_OPEN;
1305  m_openList->push(startNode);
1306 
1308  m_query.lastBestNode = startNode;
1309  m_query.lastBestNodeCost = startNode->total;
1310 
1311  return m_query.status;
1312 }
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
void clear()
Definition: DetourNode.h:114
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
#define dtAssert(expression)
Definition: DetourAssert.h:47
static const float DT_RAY_CAST_LIMIT_PROPORTIONS
Definition: DetourNavMesh.h:148
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:562
Definition: DetourNode.h:36
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:218
float walkableRadius
The radius of the agents using the tile.
Definition: DetourNavMesh.h:277
float pos[3]
Position of the node.
Definition: DetourNode.h:38
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
Definition: DetourNode.h:26
const dtMeshTile * getTileByRef(dtTileRef ref) const
Definition: DetourNavMesh.cpp:1093
struct dtNode * lastBestNode
Definition: DetourNavMeshQuery.h:550
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
dtStatus status
Definition: DetourNavMeshQuery.h:549
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
float lastBestNodeCost
Definition: DetourNavMeshQuery.h:551
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtPolyRef startRef
Definition: DetourNavMeshQuery.h:552
dtPolyRef endRef
Definition: DetourNavMeshQuery.h:552
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
use raycasts during pathfind to "shortcut" (raycast still consider costs)
Definition: DetourNavMesh.h:136
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
float cost
Cost from previous node to current node.
Definition: DetourNode.h:39
unsigned int options
Definition: DetourNavMeshQuery.h:555
dtQueryData m_query
Sliced query state.
Definition: DetourNavMeshQuery.h:558
static const float H_SCALE
Definition: DetourNavMeshQuery.cpp:103
const dtQueryFilter * filter
Definition: DetourNavMeshQuery.h:554
Definition: DetourNavMesh.h:288
float total
Cost up to the node.
Definition: DetourNode.h:40
void clear()
Definition: DetourNode.cpp:83
float startPos[3]
Definition: DetourNavMeshQuery.h:553
static const unsigned int DT_IN_PROGRESS
Definition: DetourStatus.h:27
float endPos[3]
Definition: DetourNavMeshQuery.h:553
float raycastLimitSqr
Definition: DetourNavMeshQuery.h:556
void push(dtNode *node)
Definition: DetourNode.h:126
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ isInClosedList()

bool dtNavMeshQuery::isInClosedList ( dtPolyRef  ref) const

Returns true if the polygon reference is in the closed list.

Parameters
[in]refThe reference id of the polygon to check.
Returns
True if the polygon is in closed list.

The closed list is the list of polygons that were fully evaluated during the last navigation graph search. (A* or Dijkstra)

3651 {
3652  if (!m_nodePool) return false;
3653 
3655  int n= m_nodePool->findNodes(ref, nodes, DT_MAX_STATES_PER_NODE);
3656 
3657  for (int i=0; i<n; i++)
3658  {
3659  if (nodes[i]->flags & DT_NODE_CLOSED)
3660  return true;
3661  }
3662 
3663  return false;
3664 }
Definition: DetourNode.h:36
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:561
unsigned int findNodes(dtPolyRef id, dtNode **nodes, const int maxNodes)
Definition: DetourNode.cpp:89
Definition: DetourNode.h:27
static const int DT_MAX_STATES_PER_NODE
Definition: DetourNode.h:47
uint8 flags
Definition: DisableMgr.cpp:47
+ Here is the call graph for this function:

◆ isValidPolyRef()

bool dtNavMeshQuery::isValidPolyRef ( dtPolyRef  ref,
const dtQueryFilter filter 
) const

Returns true if the polygon reference is valid and passes the filter restrictions.

Parameters
[in]refThe polygon reference to check.
[in]filterThe filter to apply.
3632 {
3633  const dtMeshTile* tile = 0;
3634  const dtPoly* poly = 0;
3635  dtStatus status = m_nav->getTileAndPolyByRef(ref, &tile, &poly);
3636  // If cannot get polygon, assume it does not exists and boundary is invalid.
3637  if (dtStatusFailed(status))
3638  return false;
3639  // If cannot pass filter, assume flags has changed and boundary is invalid.
3640  if (!filter->passFilter(ref, tile, poly))
3641  return false;
3642  return true;
3643 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1128
Definition: DetourNavMesh.h:162
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
Definition: DetourNavMesh.h:288
+ Here is the call graph for this function:

◆ moveAlongSurface()

dtStatus dtNavMeshQuery::moveAlongSurface ( dtPolyRef  startRef,
const float *  startPos,
const float *  endPos,
const dtQueryFilter filter,
float *  resultPos,
dtPolyRef visited,
int *  visitedCount,
const int  maxVisitedSize 
) const

Moves from the start to the end position constrained to the navigation mesh.

Parameters
[in]startRefThe reference id of the start polygon.
[in]startPosA position of the mover within the start polygon. [(x, y, x)]
[in]endPosThe desired end position of the mover. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[out]resultPosThe result position of the mover. [(x, y, z)]
[out]visitedThe reference ids of the polygons visited during the move.
[out]visitedCountThe number of polygons visited during the move.
[in]maxVisitedSizeThe maximum number of polygons the visited array can hold.
Returns
The status flags for the query.

This method is optimized for small delta movement and a small number of polygons. If used for too great a distance, the result set will form an incomplete path.

resultPos will equal the endPos if the end is reached. Otherwise the closest reachable position will be returned.

resultPos is not projected onto the surface of the navigation mesh. Use getPolyHeight if this is needed.

This method treats the end position in the same manner as the raycast method. (As a 2D point.) See that method's documentation for details.

If the visited array is too small to hold the entire result set, it will be filled as far as possible from the start position toward the end position.

2069 {
2070  dtAssert(m_nav);
2072 
2073  *visitedCount = 0;
2074 
2075  // Validate input
2076  if (!startRef)
2077  return DT_FAILURE | DT_INVALID_PARAM;
2078  if (!m_nav->isValidPolyRef(startRef))
2079  return DT_FAILURE | DT_INVALID_PARAM;
2080 
2081  dtStatus status = DT_SUCCESS;
2082 
2083  static const int MAX_STACK = 48;
2084  dtNode* stack[MAX_STACK];
2085  int nstack = 0;
2086 
2087  m_tinyNodePool->clear();
2088 
2089  dtNode* startNode = m_tinyNodePool->getNode(startRef);
2090  startNode->pidx = 0;
2091  startNode->cost = 0;
2092  startNode->total = 0;
2093  startNode->id = startRef;
2094  startNode->flags = DT_NODE_CLOSED;
2095  stack[nstack++] = startNode;
2096 
2097  float bestPos[3];
2098  float bestDist = FLT_MAX;
2099  dtNode* bestNode = 0;
2100  dtVcopy(bestPos, startPos);
2101 
2102  // Search constraints
2103  float searchPos[3], searchRadSqr;
2104  dtVlerp(searchPos, startPos, endPos, 0.5f);
2105  searchRadSqr = dtSqr(dtVdist(startPos, endPos)/2.0f + 0.001f);
2106 
2107  float verts[DT_VERTS_PER_POLYGON*3];
2108 
2109  while (nstack)
2110  {
2111  // Pop front.
2112  dtNode* curNode = stack[0];
2113  for (int i = 0; i < nstack-1; ++i)
2114  stack[i] = stack[i+1];
2115  nstack--;
2116 
2117  // Get poly and tile.
2118  // The API input has been cheked already, skip checking internal data.
2119  const dtPolyRef curRef = curNode->id;
2120  const dtMeshTile* curTile = 0;
2121  const dtPoly* curPoly = 0;
2122  m_nav->getTileAndPolyByRefUnsafe(curRef, &curTile, &curPoly);
2123 
2124  // Collect vertices.
2125  const int nverts = curPoly->vertCount;
2126  for (int i = 0; i < nverts; ++i)
2127  dtVcopy(&verts[i*3], &curTile->verts[curPoly->verts[i]*3]);
2128 
2129  // If target is inside the poly, stop search.
2130  if (dtPointInPolygon(endPos, verts, nverts))
2131  {
2132  bestNode = curNode;
2133  dtVcopy(bestPos, endPos);
2134  break;
2135  }
2136 
2137  // Find wall edges and find nearest point inside the walls.
2138  for (int i = 0, j = (int)curPoly->vertCount-1; i < (int)curPoly->vertCount; j = i++)
2139  {
2140  // Find links to neighbours.
2141  static const int MAX_NEIS = 8;
2142  int nneis = 0;
2143  dtPolyRef neis[MAX_NEIS];
2144 
2145  if (curPoly->neis[j] & DT_EXT_LINK)
2146  {
2147  // Tile border.
2148  for (unsigned int k = curPoly->firstLink; k != DT_NULL_LINK; k = curTile->links[k].next)
2149  {
2150  const dtLink* link = &curTile->links[k];
2151  if (link->edge == j)
2152  {
2153  if (link->ref != 0)
2154  {
2155  const dtMeshTile* neiTile = 0;
2156  const dtPoly* neiPoly = 0;
2157  m_nav->getTileAndPolyByRefUnsafe(link->ref, &neiTile, &neiPoly);
2158  if (filter->passFilter(link->ref, neiTile, neiPoly))
2159  {
2160  if (nneis < MAX_NEIS)
2161  neis[nneis++] = link->ref;
2162  }
2163  }
2164  }
2165  }
2166  }
2167  else if (curPoly->neis[j])
2168  {
2169  const unsigned int idx = (unsigned int)(curPoly->neis[j]-1);
2170  const dtPolyRef ref = m_nav->getPolyRefBase(curTile) | idx;
2171  if (filter->passFilter(ref, curTile, &curTile->polys[idx]))
2172  {
2173  // Internal edge, encode id.
2174  neis[nneis++] = ref;
2175  }
2176  }
2177 
2178  if (!nneis)
2179  {
2180  // Wall edge, calc distance.
2181  const float* vj = &verts[j*3];
2182  const float* vi = &verts[i*3];
2183  float tseg;
2184  const float distSqr = dtDistancePtSegSqr2D(endPos, vj, vi, tseg);
2185  if (distSqr < bestDist)
2186  {
2187  // Update nearest distance.
2188  dtVlerp(bestPos, vj,vi, tseg);
2189  bestDist = distSqr;
2190  bestNode = curNode;
2191  }
2192  }
2193  else
2194  {
2195  for (int k = 0; k < nneis; ++k)
2196  {
2197  // Skip if no node can be allocated.
2198  dtNode* neighbourNode = m_tinyNodePool->getNode(neis[k]);
2199  if (!neighbourNode)
2200  continue;
2201  // Skip if already visited.
2202  if (neighbourNode->flags & DT_NODE_CLOSED)
2203  continue;
2204 
2205  // Skip the link if it is too far from search constraint.
2206  // TODO: Maybe should use getPortalPoints(), but this one is way faster.
2207  const float* vj = &verts[j*3];
2208  const float* vi = &verts[i*3];
2209  float tseg;
2210  float distSqr = dtDistancePtSegSqr2D(searchPos, vj, vi, tseg);
2211  if (distSqr > searchRadSqr)
2212  continue;
2213 
2214  // Mark as the node as visited and push to queue.
2215  if (nstack < MAX_STACK)
2216  {
2217  neighbourNode->pidx = m_tinyNodePool->getNodeIdx(curNode);
2218  neighbourNode->flags |= DT_NODE_CLOSED;
2219  stack[nstack++] = neighbourNode;
2220  }
2221  }
2222  }
2223  }
2224  }
2225 
2226  int n = 0;
2227  if (bestNode)
2228  {
2229  // Reverse the path.
2230  dtNode* prev = 0;
2231  dtNode* node = bestNode;
2232  do
2233  {
2235  node->pidx = m_tinyNodePool->getNodeIdx(prev);
2236  prev = node;
2237  node = next;
2238  }
2239  while (node);
2240 
2241  // Store result
2242  node = prev;
2243  do
2244  {
2245  visited[n++] = node->id;
2246  if (n >= maxVisitedSize)
2247  {
2248  status |= DT_BUFFER_TOO_SMALL;
2249  break;
2250  }
2251  node = m_tinyNodePool->getNodeAtIdx(node->pidx);
2252  }
2253  while (node);
2254  }
2255 
2256  dtVcopy(resultPos, bestPos);
2257 
2258  *visitedCount = n;
2259 
2260  return status;
2261 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
#define dtAssert(expression)
Definition: DetourAssert.h:47
Definition: DetourNode.h:36
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:218
int next(int i, int n)
Definition: RecastContour.cpp:469
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
bool dtPointInPolygon(const float *pt, const float *verts, const int nverts)
Definition: DetourCommon.cpp:239
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:62
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int dtStatus
Definition: DetourStatus.h:22
float dtDistancePtSegSqr2D(const float *pt, const float *p, const float *q, float &t)
Definition: DetourCommon.cpp:170
unsigned short neis[DT_VERTS_PER_POLYGON]
Packed data representing neighbor polygons references and flags for each edge.
Definition: DetourNavMesh.h:172
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:43
Definition: DetourNavMesh.h:162
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:44
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:41
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:68
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:97
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:560
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
int prev(int i, int n)
Definition: RecastContour.cpp:468
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
float cost
Cost from previous node to current node.
Definition: DetourNode.h:39
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
float total
Cost up to the node.
Definition: DetourNode.h:40
void clear()
Definition: DetourNode.cpp:83
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:73
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ operator=()

dtNavMeshQuery& dtNavMeshQuery::operator= ( const dtNavMeshQuery )
private

◆ queryPolygons() [1/2]

dtStatus dtNavMeshQuery::queryPolygons ( const float *  center,
const float *  halfExtents,
const dtQueryFilter filter,
dtPolyRef polys,
int *  polyCount,
const int  maxPolys 
) const

Finds polygons that overlap the search box.

Parameters
[in]centerThe center of the search box. [(x, y, z)]
[in]halfExtentsThe search distance along each axis. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[out]polysThe reference ids of the polygons that overlap the query box.
[out]polyCountThe number of polygons in the search result.
[in]maxPolysThe maximum number of polygons the search result can hold.
Returns
The status flags for the query.

If no polygons are found, the function will return DT_SUCCESS with a polyCount of zero.

If polys is too small to hold the entire result set, then the array will be filled to capacity. The method of choosing which polygons from the full set are included in the partial result set is undefined.

949 {
950  if (!polys || !polyCount || maxPolys < 0)
951  return DT_FAILURE | DT_INVALID_PARAM;
952 
953  dtCollectPolysQuery collector(polys, maxPolys);
954 
955  dtStatus status = queryPolygons(center, halfExtents, filter, &collector);
956  if (dtStatusFailed(status))
957  return status;
958 
959  *polyCount = collector.numCollected();
960  return collector.overflowed() ? DT_SUCCESS | DT_BUFFER_TOO_SMALL : DT_SUCCESS;
961 }
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int dtStatus
Definition: DetourStatus.h:22
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtStatus queryPolygons(const float *center, const float *halfExtents, const dtQueryFilter *filter, dtPolyRef *polys, int *polyCount, const int maxPolys) const
Definition: DetourNavMeshQuery.cpp:946
Definition: DetourNavMeshQuery.cpp:903
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ queryPolygons() [2/2]

dtStatus dtNavMeshQuery::queryPolygons ( const float *  center,
const float *  halfExtents,
const dtQueryFilter filter,
dtPolyQuery query 
) const

Finds polygons that overlap the search box.

Parameters
[in]centerThe center of the search box. [(x, y, z)]
[in]halfExtentsThe search distance along each axis. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[in]queryThe query. Polygons found will be batched together and passed to this query.

The query will be invoked with batches of polygons. Polygons passed to the query have bounding boxes that overlap with the center and halfExtents passed to this function. The dtPolyQuery::process function is invoked multiple times until all overlapping polygons have been processed.

972 {
973  dtAssert(m_nav);
974 
975  if (!center || !halfExtents || !filter || !query)
976  return DT_FAILURE | DT_INVALID_PARAM;
977 
978  float bmin[3], bmax[3];
979  dtVsub(bmin, center, halfExtents);
980  dtVadd(bmax, center, halfExtents);
981 
982  // Find tiles the query touches.
983  int minx, miny, maxx, maxy;
984  m_nav->calcTileLoc(bmin, &minx, &miny);
985  m_nav->calcTileLoc(bmax, &maxx, &maxy);
986 
987  static const int MAX_NEIS = 32;
988  const dtMeshTile* neis[MAX_NEIS];
989 
990  for (int y = miny; y <= maxy; ++y)
991  {
992  for (int x = minx; x <= maxx; ++x)
993  {
994  const int nneis = m_nav->getTilesAt(x,y,neis,MAX_NEIS);
995  for (int j = 0; j < nneis; ++j)
996  {
997  queryPolygonsInTile(neis[j], bmin, bmax, filter, query);
998  }
999  }
1000  }
1001 
1002  return DT_SUCCESS;
1003 }
#define dtAssert(expression)
Definition: DetourAssert.h:47
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
void dtVadd(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:129
void queryPolygonsInTile(const dtMeshTile *tile, const float *qmin, const float *qmax, const dtQueryFilter *filter, dtPolyQuery *query) const
Queries polygons within a tile.
Definition: DetourNavMeshQuery.cpp:786
int getTilesAt(const int x, const int y, dtMeshTile const **tiles, const int maxTiles) const
Definition: DetourNavMesh.cpp:1051
G3D::int16 y
Definition: Vector2int16.h:38
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
void dtVsub(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:140
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
void calcTileLoc(const float *pos, int *tx, int *ty) const
Definition: DetourNavMesh.cpp:1122
G3D::int16 x
Definition: Vector2int16.h:37
Definition: DetourNavMesh.h:288
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ queryPolygonsInTile()

void dtNavMeshQuery::queryPolygonsInTile ( const dtMeshTile tile,
const float *  qmin,
const float *  qmax,
const dtQueryFilter filter,
dtPolyQuery query 
) const
private

Queries polygons within a tile.

788 {
789  dtAssert(m_nav);
790  static const int batchSize = 32;
791  dtPolyRef polyRefs[batchSize];
792  dtPoly* polys[batchSize];
793  int n = 0;
794 
795  if (tile->bvTree)
796  {
797  const dtBVNode* node = &tile->bvTree[0];
798  const dtBVNode* end = &tile->bvTree[tile->header->bvNodeCount];
799  const float* tbmin = tile->header->bmin;
800  const float* tbmax = tile->header->bmax;
801  const float qfac = tile->header->bvQuantFactor;
802 
803  // Calculate quantized box
804  unsigned short bmin[3], bmax[3];
805  // dtClamp query box to world box.
806  float minx = dtClamp(qmin[0], tbmin[0], tbmax[0]) - tbmin[0];
807  float miny = dtClamp(qmin[1], tbmin[1], tbmax[1]) - tbmin[1];
808  float minz = dtClamp(qmin[2], tbmin[2], tbmax[2]) - tbmin[2];
809  float maxx = dtClamp(qmax[0], tbmin[0], tbmax[0]) - tbmin[0];
810  float maxy = dtClamp(qmax[1], tbmin[1], tbmax[1]) - tbmin[1];
811  float maxz = dtClamp(qmax[2], tbmin[2], tbmax[2]) - tbmin[2];
812  // Quantize
813  bmin[0] = (unsigned short)(qfac * minx) & 0xfffe;
814  bmin[1] = (unsigned short)(qfac * miny) & 0xfffe;
815  bmin[2] = (unsigned short)(qfac * minz) & 0xfffe;
816  bmax[0] = (unsigned short)(qfac * maxx + 1) | 1;
817  bmax[1] = (unsigned short)(qfac * maxy + 1) | 1;
818  bmax[2] = (unsigned short)(qfac * maxz + 1) | 1;
819 
820  // Traverse tree
821  const dtPolyRef base = m_nav->getPolyRefBase(tile);
822  while (node < end)
823  {
824  const bool overlap = dtOverlapQuantBounds(bmin, bmax, node->bmin, node->bmax);
825  const bool isLeafNode = node->i >= 0;
826 
827  if (isLeafNode && overlap)
828  {
829  dtPolyRef ref = base | (dtPolyRef)node->i;
830  if (filter->passFilter(ref, tile, &tile->polys[node->i]))
831  {
832  polyRefs[n] = ref;
833  polys[n] = &tile->polys[node->i];
834 
835  if (n == batchSize - 1)
836  {
837  query->process(tile, polys, polyRefs, batchSize);
838  n = 0;
839  }
840  else
841  {
842  n++;
843  }
844  }
845  }
846 
847  if (overlap || isLeafNode)
848  node++;
849  else
850  {
851  const int escapeIndex = -node->i;
852  node += escapeIndex;
853  }
854  }
855  }
856  else
857  {
858  float bmin[3], bmax[3];
859  const dtPolyRef base = m_nav->getPolyRefBase(tile);
860  for (int i = 0; i < tile->header->polyCount; ++i)
861  {
862  dtPoly* p = &tile->polys[i];
863  // Do not return off-mesh connection polygons.
865  continue;
866  // Must pass filter
867  const dtPolyRef ref = base | (dtPolyRef)i;
868  if (!filter->passFilter(ref, tile, p))
869  continue;
870  // Calc polygon bounds.
871  const float* v = &tile->verts[p->verts[0]*3];
872  dtVcopy(bmin, v);
873  dtVcopy(bmax, v);
874  for (int j = 1; j < p->vertCount; ++j)
875  {
876  v = &tile->verts[p->verts[j]*3];
877  dtVmin(bmin, v);
878  dtVmax(bmax, v);
879  }
880  if (dtOverlapBounds(qmin, qmax, bmin, bmax))
881  {
882  polyRefs[n] = ref;
883  polys[n] = p;
884 
885  if (n == batchSize - 1)
886  {
887  query->process(tile, polys, polyRefs, batchSize);
888  n = 0;
889  }
890  else
891  {
892  n++;
893  }
894  }
895  }
896  }
897 
898  // Process the last polygons that didn't make a full batch.
899  if (n > 0)
900  query->process(tile, polys, polyRefs, n);
901 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
#define dtAssert(expression)
Definition: DetourAssert.h:47
virtual void process(const dtMeshTile *tile, dtPoly **polys, dtPolyRef *refs, int count)=0
unsigned short bmax[3]
Maximum bounds of the node&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:225
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
void dtVmin(float *mn, const float *v)
Definition: DetourCommon.h:161
float bvQuantFactor
The bounding volume quantization factor.
Definition: DetourNavMesh.h:283
void dtVmax(float *mx, const float *v)
Definition: DetourCommon.h:171
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
dtBVNode * bvTree
Definition: DetourNavMesh.h:307
float bmax[3]
The maximum bounds of the tile&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:280
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
int i
The node&#39;s index. (Negative for escape sequence.)
Definition: DetourNavMesh.h:226
Definition: DetourNavMesh.h:222
unsigned short bmin[3]
Minimum bounds of the node&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:224
bool dtOverlapQuantBounds(const unsigned short amin[3], const unsigned short amax[3], const unsigned short bmin[3], const unsigned short bmax[3])
Definition: DetourCommon.h:333
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
int bvNodeCount
The number of bounding volume nodes. (Zero if bounding volumes are disabled.)
Definition: DetourNavMesh.h:273
float bmin[3]
The minimum bounds of the tile&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:279
T dtClamp(T v, T mn, T mx)
Definition: DetourCommon.h:75
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
iterator end()
Definition: GridRefManager.h:36
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
bool dtOverlapBounds(const float *amin, const float *amax, const float *bmin, const float *bmax)
Definition: DetourCommon.h:350
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ raycast() [1/2]

dtStatus dtNavMeshQuery::raycast ( dtPolyRef  startRef,
const float *  startPos,
const float *  endPos,
const dtQueryFilter filter,
float *  t,
float *  hitNormal,
dtPolyRef path,
int *  pathCount,
const int  maxPath 
) const

Casts a 'walkability' ray along the surface of the navigation mesh from the start position toward the end position.

Note
A wrapper around raycast(..., RaycastHit*). Retained for backward compatibility.
Parameters
[in]startRefThe reference id of the start polygon.
[in]startPosA position within the start polygon representing the start of the ray. [(x, y, z)]
[in]endPosThe position to cast the ray toward. [(x, y, z)]
[out]tThe hit parameter. (FLT_MAX if no wall hit.)
[out]hitNormalThe normal of the nearest wall hit. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[out]pathThe reference ids of the visited polygons. [opt]
[out]pathCountThe number of visited polygons. [opt]
[in]maxPathThe maximum number of polygons the path array can hold.
Returns
The status flags for the query.

This method is meant to be used for quick, short distance checks.

If the path array is too small to hold the result, it will be filled as far as possible from the start postion toward the end position.

Using the Hit Parameter (t)

If the hit parameter is a very high value (FLT_MAX), then the ray has hit the end position. In this case the path represents a valid corridor to the end position and the value of hitNormal is undefined.

If the hit parameter is zero, then the start position is on the wall that was hit and the value of hitNormal is undefined.

If 0 < t < 1.0 then the following applies:

distanceToHitBorder = distanceToEndPosition * t
hitPoint = startPos + (endPos - startPos) * t

Use Case Restriction

The raycast ignores the y-value of the end position. (2D check.) This places significant limits on how it can be used. For example:

Consider a scene where there is a main floor with a second floor balcony that hangs over the main floor. So the first floor mesh extends below the balcony mesh. The start position is somewhere on the first floor. The end position is on the balcony.

The raycast will search toward the end position along the first floor mesh. If it reaches the end position's xz-coordinates it will indicate FLT_MAX (no wall hit), meaning it reached the end position. This is one example of why this method is meant for short distance checks.

2427 {
2428  dtRaycastHit hit;
2429  hit.path = path;
2430  hit.maxPath = maxPath;
2431 
2432  dtStatus status = raycast(startRef, startPos, endPos, filter, 0, &hit);
2433 
2434  *t = hit.t;
2435  if (hitNormal)
2436  dtVcopy(hitNormal, hit.hitNormal);
2437  if (pathCount)
2438  *pathCount = hit.pathCount;
2439 
2440  return status;
2441 }
float t
The hit parameter. (FLT_MAX if no wall hit.)
Definition: DetourNavMeshQuery.h:130
Definition: DetourNavMeshQuery.h:127
unsigned int dtStatus
Definition: DetourStatus.h:22
dtPolyRef * path
Pointer to an array of reference ids of the visited polygons. [opt].
Definition: DetourNavMeshQuery.h:139
int maxPath
The maximum number of polygons the path array can hold.
Definition: DetourNavMeshQuery.h:145
int pathCount
The number of visited polygons. [opt].
Definition: DetourNavMeshQuery.h:142
float hitNormal[3]
hitNormal The normal of the nearest wall hit. [(x, y, z)]
Definition: DetourNavMeshQuery.h:133
dtStatus raycast(dtPolyRef startRef, const float *startPos, const float *endPos, const dtQueryFilter *filter, float *t, float *hitNormal, dtPolyRef *path, int *pathCount, const int maxPath) const
Definition: DetourNavMeshQuery.cpp:2424
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ raycast() [2/2]

dtStatus dtNavMeshQuery::raycast ( dtPolyRef  startRef,
const float *  startPos,
const float *  endPos,
const dtQueryFilter filter,
const unsigned int  options,
dtRaycastHit hit,
dtPolyRef  prevRef = 0 
) const

Casts a 'walkability' ray along the surface of the navigation mesh from the start position toward the end position.

Parameters
[in]startRefThe reference id of the start polygon.
[in]startPosA position within the start polygon representing the start of the ray. [(x, y, z)]
[in]endPosThe position to cast the ray toward. [(x, y, z)]
[in]filterThe polygon filter to apply to the query.
[in]flagsgovern how the raycast behaves. See dtRaycastOptions
[out]hitPointer to a raycast hit structure which will be filled by the results.
[in]prevRefparent of start ref. Used during for cost calculation [opt]
Returns
The status flags for the query.

This method is meant to be used for quick, short distance checks.

If the path array is too small to hold the result, it will be filled as far as possible from the start postion toward the end position.

Using the Hit Parameter t of RaycastHit

If the hit parameter is a very high value (FLT_MAX), then the ray has hit the end position. In this case the path represents a valid corridor to the end position and the value of hitNormal is undefined.

If the hit parameter is zero, then the start position is on the wall that was hit and the value of hitNormal is undefined.

If 0 < t < 1.0 then the following applies:

distanceToHitBorder = distanceToEndPosition * t
hitPoint = startPos + (endPos - startPos) * t

Use Case Restriction

The raycast ignores the y-value of the end position. (2D check.) This places significant limits on how it can be used. For example:

Consider a scene where there is a main floor with a second floor balcony that hangs over the main floor. So the first floor mesh extends below the balcony mesh. The start position is somewhere on the first floor. The end position is on the balcony.

The raycast will search toward the end position along the first floor mesh. If it reaches the end position's xz-coordinates it will indicate FLT_MAX (no wall hit), meaning it reached the end position. This is one example of why this method is meant for short distance checks.

2485 {
2486  dtAssert(m_nav);
2487 
2488  hit->t = 0;
2489  hit->pathCount = 0;
2490  hit->pathCost = 0;
2491 
2492  // Validate input
2493  if (!startRef || !m_nav->isValidPolyRef(startRef))
2494  return DT_FAILURE | DT_INVALID_PARAM;
2495  if (prevRef && !m_nav->isValidPolyRef(prevRef))
2496  return DT_FAILURE | DT_INVALID_PARAM;
2497 
2498  float dir[3], curPos[3], lastPos[3];
2499  float verts[DT_VERTS_PER_POLYGON*3+3];
2500  int n = 0;
2501 
2502  dtVcopy(curPos, startPos);
2503  dtVsub(dir, endPos, startPos);
2504  dtVset(hit->hitNormal, 0, 0, 0);
2505 
2506  dtStatus status = DT_SUCCESS;
2507 
2508  const dtMeshTile* prevTile, *tile, *nextTile;
2509  const dtPoly* prevPoly, *poly, *nextPoly;
2510  dtPolyRef curRef;
2511 
2512  // The API input has been checked already, skip checking internal data.
2513  curRef = startRef;
2514  tile = 0;
2515  poly = 0;
2516  m_nav->getTileAndPolyByRefUnsafe(curRef, &tile, &poly);
2517  nextTile = prevTile = tile;
2518  nextPoly = prevPoly = poly;
2519  if (prevRef)
2520  m_nav->getTileAndPolyByRefUnsafe(prevRef, &prevTile, &prevPoly);
2521 
2522  while (curRef)
2523  {
2524  // Cast ray against current polygon.
2525 
2526  // Collect vertices.
2527  int nv = 0;
2528  for (int i = 0; i < (int)poly->vertCount; ++i)
2529  {
2530  dtVcopy(&verts[nv*3], &tile->verts[poly->verts[i]*3]);
2531  nv++;
2532  }
2533 
2534  float tmin, tmax;
2535  int segMin, segMax;
2536  if (!dtIntersectSegmentPoly2D(startPos, endPos, verts, nv, tmin, tmax, segMin, segMax))
2537  {
2538  // Could not hit the polygon, keep the old t and report hit.
2539  hit->pathCount = n;
2540  return status;
2541  }
2542 
2543  hit->hitEdgeIndex = segMax;
2544 
2545  // Keep track of furthest t so far.
2546  if (tmax > hit->t)
2547  hit->t = tmax;
2548 
2549  // Store visited polygons.
2550  if (n < hit->maxPath)
2551  hit->path[n++] = curRef;
2552  else
2553  status |= DT_BUFFER_TOO_SMALL;
2554 
2555  // Ray end is completely inside the polygon.
2556  if (segMax == -1)
2557  {
2558  hit->t = FLT_MAX;
2559  hit->pathCount = n;
2560 
2561  // add the cost
2562  if (options & DT_RAYCAST_USE_COSTS)
2563  hit->pathCost += filter->getCost(curPos, endPos, prevRef, prevTile, prevPoly, curRef, tile, poly, curRef, tile, poly);
2564  return status;
2565  }
2566 
2567  // Follow neighbours.
2568  dtPolyRef nextRef = 0;
2569 
2570  for (unsigned int i = poly->firstLink; i != DT_NULL_LINK; i = tile->links[i].next)
2571  {
2572  const dtLink* link = &tile->links[i];
2573 
2574  // Find link which contains this edge.
2575  if ((int)link->edge != segMax)
2576  continue;
2577 
2578  // Get pointer to the next polygon.
2579  nextTile = 0;
2580  nextPoly = 0;
2581  m_nav->getTileAndPolyByRefUnsafe(link->ref, &nextTile, &nextPoly);
2582 
2583  // Skip off-mesh connections.
2584  if (nextPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
2585  continue;
2586 
2587  // Skip links based on filter.
2588  if (!filter->passFilter(link->ref, nextTile, nextPoly))
2589  continue;
2590 
2591  // If the link is internal, just return the ref.
2592  if (link->side == 0xff)
2593  {
2594  nextRef = link->ref;
2595  break;
2596  }
2597 
2598  // If the link is at tile boundary,
2599 
2600  // Check if the link spans the whole edge, and accept.
2601  if (link->bmin == 0 && link->bmax == 255)
2602  {
2603  nextRef = link->ref;
2604  break;
2605  }
2606 
2607  // Check for partial edge links.
2608  const int v0 = poly->verts[link->edge];
2609  const int v1 = poly->verts[(link->edge+1) % poly->vertCount];
2610  const float* left = &tile->verts[v0*3];
2611  const float* right = &tile->verts[v1*3];
2612 
2613  // Check that the intersection lies inside the link portal.
2614  if (link->side == 0 || link->side == 4)
2615  {
2616  // Calculate link size.
2617  const float s = 1.0f/255.0f;
2618  float lmin = left[2] + (right[2] - left[2])*(link->bmin*s);
2619  float lmax = left[2] + (right[2] - left[2])*(link->bmax*s);
2620  if (lmin > lmax) dtSwap(lmin, lmax);
2621 
2622  // Find Z intersection.
2623  float z = startPos[2] + (endPos[2]-startPos[2])*tmax;
2624  if (z >= lmin && z <= lmax)
2625  {
2626  nextRef = link->ref;
2627  break;
2628  }
2629  }
2630  else if (link->side == 2 || link->side == 6)
2631  {
2632  // Calculate link size.
2633  const float s = 1.0f/255.0f;
2634  float lmin = left[0] + (right[0] - left[0])*(link->bmin*s);
2635  float lmax = left[0] + (right[0] - left[0])*(link->bmax*s);
2636  if (lmin > lmax) dtSwap(lmin, lmax);
2637 
2638  // Find X intersection.
2639  float x = startPos[0] + (endPos[0]-startPos[0])*tmax;
2640  if (x >= lmin && x <= lmax)
2641  {
2642  nextRef = link->ref;
2643  break;
2644  }
2645  }
2646  }
2647 
2648  // add the cost
2649  if (options & DT_RAYCAST_USE_COSTS)
2650  {
2651  // compute the intersection point at the furthest end of the polygon
2652  // and correct the height (since the raycast moves in 2d)
2653  dtVcopy(lastPos, curPos);
2654  dtVmad(curPos, startPos, dir, hit->t);
2655  float* e1 = &verts[segMax*3];
2656  float* e2 = &verts[((segMax+1)%nv)*3];
2657  float eDir[3], diff[3];
2658  dtVsub(eDir, e2, e1);
2659  dtVsub(diff, curPos, e1);
2660  float s = dtSqr(eDir[0]) > dtSqr(eDir[2]) ? diff[0] / eDir[0] : diff[2] / eDir[2];
2661  curPos[1] = e1[1] + eDir[1] * s;
2662 
2663  hit->pathCost += filter->getCost(lastPos, curPos, prevRef, prevTile, prevPoly, curRef, tile, poly, nextRef, nextTile, nextPoly);
2664  }
2665 
2666  if (!nextRef)
2667  {
2668  // No neighbour, we hit a wall.
2669 
2670  // Calculate hit normal.
2671  const int a = segMax;
2672  const int b = segMax+1 < nv ? segMax+1 : 0;
2673  const float* va = &verts[a*3];
2674  const float* vb = &verts[b*3];
2675  const float dx = vb[0] - va[0];
2676  const float dz = vb[2] - va[2];
2677  hit->hitNormal[0] = dz;
2678  hit->hitNormal[1] = 0;
2679  hit->hitNormal[2] = -dx;
2680  dtVnormalize(hit->hitNormal);
2681 
2682  hit->pathCount = n;
2683  return status;
2684  }
2685 
2686  // No hit, advance to neighbour polygon.
2687  prevRef = curRef;
2688  curRef = nextRef;
2689  prevTile = tile;
2690  tile = nextTile;
2691  prevPoly = poly;
2692  poly = nextPoly;
2693  }
2694 
2695  hit->pathCount = n;
2696 
2697  return status;
2698 }
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
float t
The hit parameter. (FLT_MAX if no wall hit.)
Definition: DetourNavMeshQuery.h:130
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1154
#define dtAssert(expression)
Definition: DetourAssert.h:47
float pathCost
The cost of the path until hit.
Definition: DetourNavMeshQuery.h:148
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
void dtVmad(float *dest, const float *v1, const float *v2, const float s)
Definition: DetourCommon.h:106
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
Raycast should calculate movement cost along the ray and fill RaycastHit::cost.
Definition: DetourNavMesh.h:142
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
bool dtIntersectSegmentPoly2D(const float *p0, const float *p1, const float *verts, int nverts, float &tmin, float &tmax, int &segMin, int &segMax)
Definition: DetourCommon.cpp:110
unsigned int dtStatus
Definition: DetourStatus.h:22
void dtVnormalize(float *v)
Definition: DetourCommon.h:264
dtPolyRef * path
Pointer to an array of reference ids of the visited polygons. [opt].
Definition: DetourNavMeshQuery.h:139
Definition: DetourNavMesh.h:162
int pathCount
The number of visited polygons. [opt].
Definition: DetourNavMeshQuery.h:142
float hitNormal[3]
hitNormal The normal of the nearest wall hit. [(x, y, z)]
Definition: DetourNavMeshQuery.h:133
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
void dtVset(float *dest, const float x, const float y, const float z)
Definition: DetourCommon.h:183
G3D::int16 z
Definition: Vector3int16.h:46
int hitEdgeIndex
The index of the edge on the final polygon where the wall was hit.
Definition: DetourNavMeshQuery.h:136
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
bool left(const int *a, const int *b, const int *c)
Definition: RecastContour.cpp:487
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1121
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
void dtSwap(T &a, T &b)
Definition: DetourCommon.h:46
void dtVsub(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:140
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:545
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
G3D::int16 x
Definition: Vector2int16.h:37
Definition: DetourNavMesh.h:288
float getCost(const float *pa, const float *pb, const dtPolyRef prevRef, const dtMeshTile *prevTile, const dtPoly *prevPoly, const dtPolyRef curRef, const dtMeshTile *curTile, const dtPoly *curPoly, const dtPolyRef nextRef, const dtMeshTile *nextTile, const dtPoly *nextPoly) const
Definition: DetourNavMeshQuery.cpp:94
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:73
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ updateSlicedFindPath()

dtStatus dtNavMeshQuery::updateSlicedFindPath ( const int  maxIter,
int *  doneIters 
)

Updates an in-progress sliced path query.

Parameters
[in]maxIterThe maximum number of iterations to perform.
[out]doneItersThe actual number of iterations completed. [opt]
Returns
The status flags for the query.
1315 {
1317  return m_query.status;
1318 
1319  // Make sure the request is still valid.
1321  {
1323  return DT_FAILURE;
1324  }
1325 
1326  dtRaycastHit rayHit;
1327  rayHit.maxPath = 0;
1328 
1329  int iter = 0;
1330  while (iter < maxIter && !m_openList->empty())
1331  {
1332  iter++;
1333 
1334  // Remove node from open list and put it in closed list.
1335  dtNode* bestNode = m_openList->pop();
1336  bestNode->flags &= ~DT_NODE_OPEN;
1337  bestNode->flags |= DT_NODE_CLOSED;
1338 
1339  // Reached the goal, stop searching.
1340  if (bestNode->id == m_query.endRef)
1341  {
1342  m_query.lastBestNode = bestNode;
1343  const dtStatus details = m_query.status & DT_STATUS_DETAIL_MASK;
1344  m_query.status = DT_SUCCESS | details;
1345  if (doneIters)
1346  *doneIters = iter;
1347  return m_query.status;
1348  }
1349 
1350  // Get current poly and tile.
1351  // The API input has been cheked already, skip checking internal data.
1352  const dtPolyRef bestRef = bestNode->id;
1353  const dtMeshTile* bestTile = 0;
1354  const dtPoly* bestPoly = 0;
1355  if (dtStatusFailed(m_nav->getTileAndPolyByRef(bestRef, &bestTile, &bestPoly)))
1356  {
1357  // The polygon has disappeared during the sliced query, fail.
1359  if (doneIters)
1360  *doneIters = iter;
1361  return m_query.status;
1362  }
1363 
1364  // Get parent and grand parent poly and tile.
1365  dtPolyRef parentRef = 0, grandpaRef = 0;
1366  const dtMeshTile* parentTile = 0;
1367  const dtPoly* parentPoly = 0;
1368  dtNode* parentNode = 0;
1369  if (bestNode->pidx)
1370  {
1371  parentNode = m_nodePool->getNodeAtIdx(bestNode->pidx);
1372  parentRef = parentNode->id;
1373  if (parentNode->pidx)
1374  grandpaRef = m_nodePool->getNodeAtIdx(parentNode->pidx)->id;
1375  }
1376  if (parentRef)
1377  {
1378  bool invalidParent = dtStatusFailed(m_nav->getTileAndPolyByRef(parentRef, &parentTile, &parentPoly));
1379  if (invalidParent || (grandpaRef && !m_nav->isValidPolyRef(grandpaRef)) )
1380  {
1381  // The polygon has disappeared during the sliced query, fail.
1383  if (doneIters)
1384  *doneIters = iter;
1385  return m_query.status;
1386  }
1387  }
1388 
1389  // decide whether to test raycast to previous nodes
1390  bool tryLOS = false;
1392  {
1393  if ((parentRef != 0) && (dtVdistSqr(parentNode->pos, bestNode->pos) < m_query.raycastLimitSqr))
1394  tryLOS = true;
1395  }
1396 
1397  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
1398  {
1399  dtPolyRef neighbourRef = bestTile->links[i].ref;
1400 
1401  // Skip invalid ids and do not expand back to where we came from.
1402  if (!neighbourRef || neighbourRef == parentRef)
1403  continue;
1404 
1405  // Get neighbour poly and tile.
1406  // The API input has been cheked already, skip checking internal data.
1407  const dtMeshTile* neighbourTile = 0;
1408  const dtPoly* neighbourPoly = 0;
1409  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
1410 
1411  if (!m_query.filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
1412  continue;
1413 
1414  // get the neighbor node
1415  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef, 0);
1416  if (!neighbourNode)
1417  {
1419  continue;
1420  }
1421 
1422  // do not expand to nodes that were already visited from the same parent
1423  if (neighbourNode->pidx != 0 && neighbourNode->pidx == bestNode->pidx)
1424  continue;
1425 
1426  // If the node is visited the first time, calculate node position.
1427  if (neighbourNode->flags == 0)
1428  {
1429  getEdgeMidPoint(bestRef, bestPoly, bestTile,
1430  neighbourRef, neighbourPoly, neighbourTile,
1431  neighbourNode->pos);
1432  }
1433 
1434  // Calculate cost and heuristic.
1435  float cost = 0;
1436  float heuristic = 0;
1437 
1438  // raycast parent
1439  bool foundShortCut = false;
1440  rayHit.pathCost = rayHit.t = 0;
1441  if (tryLOS)
1442  {
1443  raycast(parentRef, parentNode->pos, neighbourNode->pos, m_query.filter, DT_RAYCAST_USE_COSTS, &rayHit, grandpaRef);
1444  foundShortCut = rayHit.t >= 1.0f;
1445  }
1446 
1447  // update move cost
1448  if (foundShortCut)
1449  {
1450  // shortcut found using raycast. Using shorter cost instead
1451  cost = parentNode->cost + rayHit.pathCost;
1452  }
1453  else
1454  {
1455  // No shortcut found.
1456  const float curCost = m_query.filter->getCost(bestNode->pos, neighbourNode->pos,
1457  parentRef, parentTile, parentPoly,
1458  bestRef, bestTile, bestPoly,
1459  neighbourRef, neighbourTile, neighbourPoly);
1460  cost = bestNode->cost + curCost;
1461  }
1462 
1463  // Special case for last node.
1464  if (neighbourRef == m_query.endRef)
1465  {
1466  const float endCost = m_query.filter->getCost(neighbourNode->pos,