TrinityCore
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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
 
Local Query Functions
dtStatus findNearestPoly (const float *center, const float *extents, const dtQueryFilter *filter, dtPolyRef *nearestRef, float *nearestPt) const
 
dtStatus queryPolygons (const float *center, const float *extents, const dtQueryFilter *filter, dtPolyRef *polys, int *polyCount, const int maxPolys) 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

dtMeshTilegetNeighbourTileAt (int x, int y, int side) const
 Returns neighbour tile based on side. More...
 
int queryPolygonsInTile (const dtMeshTile *tile, const float *qmin, const float *qmax, const dtQueryFilter *filter, dtPolyRef *polys, const int maxPolys) 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
 

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::dtNavMeshQuery ( )
139  :
140  m_nav(0),
141  m_tinyNodePool(0),
142  m_nodePool(0),
143  m_openList(0)
144 {
145  memset(&m_query, 0, sizeof(dtQueryData));
146 }
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:523
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:521
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
dtQueryData m_query
Sliced query state.
Definition: DetourNavMeshQuery.h:519
dtNavMeshQuery::~dtNavMeshQuery ( )
149 {
150  if (m_tinyNodePool)
152  if (m_nodePool)
154  if (m_openList)
159 }
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:523
~dtNodeQueue()
Definition: DetourNode.cpp:152
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
~dtNodePool()
Definition: DetourNode.cpp:61
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:521
void dtFree(void *ptr)
Definition: DetourAlloc.cpp:46

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Function Documentation

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
1643 {
1644  const float* startPos = &straightPath[(*straightPathCount-1)*3];
1645  // Append or update last vertex
1646  dtStatus stat = 0;
1647  for (int i = startIdx; i < endIdx; i++)
1648  {
1649  // Calculate portal
1650  const dtPolyRef from = path[i];
1651  const dtMeshTile* fromTile = 0;
1652  const dtPoly* fromPoly = 0;
1653  if (dtStatusFailed(m_nav->getTileAndPolyByRef(from, &fromTile, &fromPoly)))
1654  return DT_FAILURE | DT_INVALID_PARAM;
1655 
1656  const dtPolyRef to = path[i+1];
1657  const dtMeshTile* toTile = 0;
1658  const dtPoly* toPoly = 0;
1659  if (dtStatusFailed(m_nav->getTileAndPolyByRef(to, &toTile, &toPoly)))
1660  return DT_FAILURE | DT_INVALID_PARAM;
1661 
1662  float left[3], right[3];
1663  if (dtStatusFailed(getPortalPoints(from, fromPoly, fromTile, to, toPoly, toTile, left, right)))
1664  break;
1665 
1666  if (options & DT_STRAIGHTPATH_AREA_CROSSINGS)
1667  {
1668  // Skip intersection if only area crossings are requested.
1669  if (fromPoly->getArea() == toPoly->getArea())
1670  continue;
1671  }
1672 
1673  // Append intersection
1674  float s,t;
1675  if (dtIntersectSegSeg2D(startPos, endPos, left, right, s, t))
1676  {
1677  float pt[3];
1678  dtVlerp(pt, left,right, t);
1679 
1680  stat = appendVertex(pt, 0, path[i+1],
1681  straightPath, straightPathFlags, straightPathRefs,
1682  straightPathCount, maxStraightPath);
1683  if (stat != DT_IN_PROGRESS)
1684  return stat;
1685  }
1686  }
1687  return DT_IN_PROGRESS;
1688 }
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:117
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:1610
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:2146
unsigned char getArea() const
Gets the user defined area id.
Definition: DetourNavMesh.h:182
unsigned int dtStatus
Definition: DetourStatus.h:22
Definition: DetourNavMesh.h:153
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1113
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:118
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
Definition: DetourNavMesh.h:279
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:

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
1613 {
1614  if ((*straightPathCount) > 0 && dtVequal(&straightPath[((*straightPathCount)-1)*3], pos))
1615  {
1616  // The vertices are equal, update flags and poly.
1617  if (straightPathFlags)
1618  straightPathFlags[(*straightPathCount)-1] = flags;
1619  if (straightPathRefs)
1620  straightPathRefs[(*straightPathCount)-1] = ref;
1621  }
1622  else
1623  {
1624  // Append new vertex.
1625  dtVcopy(&straightPath[(*straightPathCount)*3], pos);
1626  if (straightPathFlags)
1627  straightPathFlags[(*straightPathCount)] = flags;
1628  if (straightPathRefs)
1629  straightPathRefs[(*straightPathCount)] = ref;
1630  (*straightPathCount)++;
1631  // If reached end of path or there is no space to append more vertices, return.
1632  if (flags == DT_STRAIGHTPATH_END || (*straightPathCount) >= maxStraightPath)
1633  {
1634  return DT_SUCCESS | (((*straightPathCount) >= maxStraightPath) ? DT_BUFFER_TOO_SMALL : 0);
1635  }
1636  }
1637  return DT_IN_PROGRESS;
1638 }
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:111
bool dtVequal(const float *p0, const float *p1)
Definition: DetourCommon.h:278
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
uint8 flags
Definition: DisableMgr.cpp:44
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:

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.

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

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.

602 {
603  dtAssert(m_nav);
604 
605  const dtMeshTile* tile = 0;
606  const dtPoly* poly = 0;
607  if (dtStatusFailed(m_nav->getTileAndPolyByRef(ref, &tile, &poly)))
608  return DT_FAILURE | DT_INVALID_PARAM;
609 
610  // Collect vertices.
611  float verts[DT_VERTS_PER_POLYGON*3];
612  float edged[DT_VERTS_PER_POLYGON];
613  float edget[DT_VERTS_PER_POLYGON];
614  int nv = 0;
615  for (int i = 0; i < (int)poly->vertCount; ++i)
616  {
617  dtVcopy(&verts[nv*3], &tile->verts[poly->verts[i]*3]);
618  nv++;
619  }
620 
621  bool inside = dtDistancePtPolyEdgesSqr(pos, verts, nv, edged, edget);
622  if (inside)
623  {
624  // Point is inside the polygon, return the point.
625  dtVcopy(closest, pos);
626  }
627  else
628  {
629  // Point is outside the polygon, dtClamp to nearest edge.
630  float dmin = FLT_MAX;
631  int imin = -1;
632  for (int i = 0; i < nv; ++i)
633  {
634  if (edged[i] < dmin)
635  {
636  dmin = edged[i];
637  imin = i;
638  }
639  }
640  const float* va = &verts[imin*3];
641  const float* vb = &verts[((imin+1)%nv)*3];
642  dtVlerp(closest, va, vb, edget[imin]);
643  }
644 
645  return DT_SUCCESS;
646 }
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:117
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:160
Definition: DetourNavMesh.h:153
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1113
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:286
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:169
Definition: DetourNavMesh.h:279
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:57
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:

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.
1426 {
1427  *pathCount = 0;
1428 
1430  {
1431  // Reset query.
1432  memset(&m_query, 0, sizeof(dtQueryData));
1433  return DT_FAILURE;
1434  }
1435 
1436  int n = 0;
1437 
1438  if (m_query.startRef == m_query.endRef)
1439  {
1440  // Special case: the search starts and ends at same poly.
1441  path[n++] = m_query.startRef;
1442  }
1443  else
1444  {
1445  // Reverse the path.
1447 
1450 
1451  dtNode* prev = 0;
1452  dtNode* node = m_query.lastBestNode;
1453  int prevRay = 0;
1454  do
1455  {
1456  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1457  node->pidx = m_nodePool->getNodeIdx(prev);
1458  prev = node;
1459  int nextRay = node->flags & DT_NODE_PARENT_DETACHED; // keep track of whether parent is not adjacent (i.e. due to raycast shortcut)
1460  node->flags = (node->flags & ~DT_NODE_PARENT_DETACHED) | prevRay; // and store it in the reversed path's node
1461  prevRay = nextRay;
1462  node = next;
1463  }
1464  while (node);
1465 
1466  // Store path
1467  node = prev;
1468  do
1469  {
1470  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1471  dtStatus status = 0;
1472  if (node->flags & DT_NODE_PARENT_DETACHED)
1473  {
1474  float t, normal[3];
1475  int m;
1476  status = raycast(node->id, node->pos, next->pos, m_query.filter, &t, normal, path+n, &m, maxPath-n);
1477  n += m;
1478  // raycast ends on poly boundary and the path might include the next poly boundary.
1479  if (path[n-1] == next->id)
1480  n--; // remove to avoid duplicates
1481  }
1482  else
1483  {
1484  path[n++] = node->id;
1485  if (n >= maxPath)
1486  status = DT_BUFFER_TOO_SMALL;
1487  }
1488 
1489  if (status & DT_STATUS_DETAIL_MASK)
1490  {
1491  m_query.status |= status & DT_STATUS_DETAIL_MASK;
1492  break;
1493  }
1494  node = next;
1495  }
1496  while (node);
1497  }
1498 
1499  const dtStatus details = m_query.status & DT_STATUS_DETAIL_MASK;
1500 
1501  // Reset query.
1502  memset(&m_query, 0, sizeof(dtQueryData));
1503 
1504  *pathCount = n;
1505 
1506  return DT_SUCCESS | details;
1507 }
Definition: DetourNode.h:34
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:36
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
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:2306
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:64
struct dtNode * lastBestNode
Definition: DetourNavMeshQuery.h:511
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
unsigned int dtStatus
Definition: DetourStatus.h:22
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
dtStatus status
Definition: DetourNavMeshQuery.h:510
static const unsigned int DT_PARTIAL_RESULT
Definition: DetourStatus.h:37
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
Definition: DetourNode.h:28
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
dtPolyRef startRef
Definition: DetourNavMeshQuery.h:513
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:70
dtPolyRef endRef
Definition: DetourNavMeshQuery.h:513
int prev(int i, int n)
Definition: RecastContour.cpp:468
dtQueryData m_query
Sliced query state.
Definition: DetourNavMeshQuery.h:519
const dtQueryFilter * filter
Definition: DetourNavMeshQuery.h:515
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

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.
1511 {
1512  *pathCount = 0;
1513 
1514  if (existingSize == 0)
1515  {
1516  return DT_FAILURE;
1517  }
1518 
1520  {
1521  // Reset query.
1522  memset(&m_query, 0, sizeof(dtQueryData));
1523  return DT_FAILURE;
1524  }
1525 
1526  int n = 0;
1527 
1528  if (m_query.startRef == m_query.endRef)
1529  {
1530  // Special case: the search starts and ends at same poly.
1531  path[n++] = m_query.startRef;
1532  }
1533  else
1534  {
1535  // Find furthest existing node that was visited.
1536  dtNode* prev = 0;
1537  dtNode* node = 0;
1538  for (int i = existingSize-1; i >= 0; --i)
1539  {
1540  m_nodePool->findNodes(existing[i], &node, 1);
1541  if (node)
1542  break;
1543  }
1544 
1545  if (!node)
1546  {
1549  node = m_query.lastBestNode;
1550  }
1551 
1552  // Reverse the path.
1553  int prevRay = 0;
1554  do
1555  {
1556  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1557  node->pidx = m_nodePool->getNodeIdx(prev);
1558  prev = node;
1559  int nextRay = node->flags & DT_NODE_PARENT_DETACHED; // keep track of whether parent is not adjacent (i.e. due to raycast shortcut)
1560  node->flags = (node->flags & ~DT_NODE_PARENT_DETACHED) | prevRay; // and store it in the reversed path's node
1561  prevRay = nextRay;
1562  node = next;
1563  }
1564  while (node);
1565 
1566  // Store path
1567  node = prev;
1568  do
1569  {
1570  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1571  dtStatus status = 0;
1572  if (node->flags & DT_NODE_PARENT_DETACHED)
1573  {
1574  float t, normal[3];
1575  int m;
1576  status = raycast(node->id, node->pos, next->pos, m_query.filter, &t, normal, path+n, &m, maxPath-n);
1577  n += m;
1578  // raycast ends on poly boundary and the path might include the next poly boundary.
1579  if (path[n-1] == next->id)
1580  n--; // remove to avoid duplicates
1581  }
1582  else
1583  {
1584  path[n++] = node->id;
1585  if (n >= maxPath)
1586  status = DT_BUFFER_TOO_SMALL;
1587  }
1588 
1589  if (status & DT_STATUS_DETAIL_MASK)
1590  {
1591  m_query.status |= status & DT_STATUS_DETAIL_MASK;
1592  break;
1593  }
1594  node = next;
1595  }
1596  while (node);
1597  }
1598 
1599  const dtStatus details = m_query.status & DT_STATUS_DETAIL_MASK;
1600 
1601  // Reset query.
1602  memset(&m_query, 0, sizeof(dtQueryData));
1603 
1604  *pathCount = n;
1605 
1606  return DT_SUCCESS | details;
1607 }
Definition: DetourNode.h:34
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:36
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
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:2306
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:64
struct dtNode * lastBestNode
Definition: DetourNavMeshQuery.h:511
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
unsigned int dtStatus
Definition: DetourStatus.h:22
unsigned int findNodes(dtPolyRef id, dtNode **nodes, const int maxNodes)
Definition: DetourNode.cpp:74
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
dtStatus status
Definition: DetourNavMeshQuery.h:510
static const unsigned int DT_PARTIAL_RESULT
Definition: DetourStatus.h:37
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
Definition: DetourNode.h:28
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
dtPolyRef startRef
Definition: DetourNavMeshQuery.h:513
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:70
dtPolyRef endRef
Definition: DetourNavMeshQuery.h:513
int prev(int i, int n)
Definition: RecastContour.cpp:468
dtQueryData m_query
Sliced query state.
Definition: DetourNavMeshQuery.h:519
const dtQueryFilter * filter
Definition: DetourNavMeshQuery.h:515
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

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.

3331 {
3332  dtAssert(m_nav);
3335 
3336  // Validate input
3337  if (!startRef || !m_nav->isValidPolyRef(startRef))
3338  return DT_FAILURE | DT_INVALID_PARAM;
3339 
3340  m_nodePool->clear();
3341  m_openList->clear();
3342 
3343  dtNode* startNode = m_nodePool->getNode(startRef);
3344  dtVcopy(startNode->pos, centerPos);
3345  startNode->pidx = 0;
3346  startNode->cost = 0;
3347  startNode->total = 0;
3348  startNode->id = startRef;
3349  startNode->flags = DT_NODE_OPEN;
3350  m_openList->push(startNode);
3351 
3352  float radiusSqr = dtSqr(maxRadius);
3353 
3354  dtStatus status = DT_SUCCESS;
3355 
3356  while (!m_openList->empty())
3357  {
3358  dtNode* bestNode = m_openList->pop();
3359  bestNode->flags &= ~DT_NODE_OPEN;
3360  bestNode->flags |= DT_NODE_CLOSED;
3361 
3362  // Get poly and tile.
3363  // The API input has been cheked already, skip checking internal data.
3364  const dtPolyRef bestRef = bestNode->id;
3365  const dtMeshTile* bestTile = 0;
3366  const dtPoly* bestPoly = 0;
3367  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
3368 
3369  // Get parent poly and tile.
3370  dtPolyRef parentRef = 0;
3371  const dtMeshTile* parentTile = 0;
3372  const dtPoly* parentPoly = 0;
3373  if (bestNode->pidx)
3374  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
3375  if (parentRef)
3376  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
3377 
3378  // Hit test walls.
3379  for (int i = 0, j = (int)bestPoly->vertCount-1; i < (int)bestPoly->vertCount; j = i++)
3380  {
3381  // Skip non-solid edges.
3382  if (bestPoly->neis[j] & DT_EXT_LINK)
3383  {
3384  // Tile border.
3385  bool solid = true;
3386  for (unsigned int k = bestPoly->firstLink; k != DT_NULL_LINK; k = bestTile->links[k].next)
3387  {
3388  const dtLink* link = &bestTile->links[k];
3389  if (link->edge == j)
3390  {
3391  if (link->ref != 0)
3392  {
3393  const dtMeshTile* neiTile = 0;
3394  const dtPoly* neiPoly = 0;
3395  m_nav->getTileAndPolyByRefUnsafe(link->ref, &neiTile, &neiPoly);
3396  if (filter->passFilter(link->ref, neiTile, neiPoly))
3397  solid = false;
3398  }
3399  break;
3400  }
3401  }
3402  if (!solid) continue;
3403  }
3404  else if (bestPoly->neis[j])
3405  {
3406  // Internal edge
3407  const unsigned int idx = (unsigned int)(bestPoly->neis[j]-1);
3408  const dtPolyRef ref = m_nav->getPolyRefBase(bestTile) | idx;
3409  if (filter->passFilter(ref, bestTile, &bestTile->polys[idx]))
3410  continue;
3411  }
3412 
3413  // Calc distance to the edge.
3414  const float* vj = &bestTile->verts[bestPoly->verts[j]*3];
3415  const float* vi = &bestTile->verts[bestPoly->verts[i]*3];
3416  float tseg;
3417  float distSqr = dtDistancePtSegSqr2D(centerPos, vj, vi, tseg);
3418 
3419  // Edge is too far, skip.
3420  if (distSqr > radiusSqr)
3421  continue;
3422 
3423  // Hit wall, update radius.
3424  radiusSqr = distSqr;
3425  // Calculate hit pos.
3426  hitPos[0] = vj[0] + (vi[0] - vj[0])*tseg;
3427  hitPos[1] = vj[1] + (vi[1] - vj[1])*tseg;
3428  hitPos[2] = vj[2] + (vi[2] - vj[2])*tseg;
3429  }
3430 
3431  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
3432  {
3433  const dtLink* link = &bestTile->links[i];
3434  dtPolyRef neighbourRef = link->ref;
3435  // Skip invalid neighbours and do not follow back to parent.
3436  if (!neighbourRef || neighbourRef == parentRef)
3437  continue;
3438 
3439  // Expand to neighbour.
3440  const dtMeshTile* neighbourTile = 0;
3441  const dtPoly* neighbourPoly = 0;
3442  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
3443 
3444  // Skip off-mesh connections.
3445  if (neighbourPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
3446  continue;
3447 
3448  // Calc distance to the edge.
3449  const float* va = &bestTile->verts[bestPoly->verts[link->edge]*3];
3450  const float* vb = &bestTile->verts[bestPoly->verts[(link->edge+1) % bestPoly->vertCount]*3];
3451  float tseg;
3452  float distSqr = dtDistancePtSegSqr2D(centerPos, va, vb, tseg);
3453 
3454  // If the circle is not touching the next polygon, skip it.
3455  if (distSqr > radiusSqr)
3456  continue;
3457 
3458  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
3459  continue;
3460 
3461  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
3462  if (!neighbourNode)
3463  {
3464  status |= DT_OUT_OF_NODES;
3465  continue;
3466  }
3467 
3468  if (neighbourNode->flags & DT_NODE_CLOSED)
3469  continue;
3470 
3471  // Cost
3472  if (neighbourNode->flags == 0)
3473  {
3474  getEdgeMidPoint(bestRef, bestPoly, bestTile,
3475  neighbourRef, neighbourPoly, neighbourTile, neighbourNode->pos);
3476  }
3477 
3478  const float total = bestNode->total + dtVdist(bestNode->pos, neighbourNode->pos);
3479 
3480  // The node is already in open list and the new result is worse, skip.
3481  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
3482  continue;
3483 
3484  neighbourNode->id = neighbourRef;
3485  neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED);
3486  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
3487  neighbourNode->total = total;
3488 
3489  if (neighbourNode->flags & DT_NODE_OPEN)
3490  {
3491  m_openList->modify(neighbourNode);
3492  }
3493  else
3494  {
3495  neighbourNode->flags |= DT_NODE_OPEN;
3496  m_openList->push(neighbourNode);
3497  }
3498  }
3499  }
3500 
3501  // Calc hit normal.
3502  dtVsub(hitNormal, centerPos, hitPos);
3503  dtVnormalize(hitNormal);
3504 
3505  *hitDist = sqrtf(radiusSqr);
3506 
3507  return status;
3508 }
bool empty() const
Definition: DetourNode.h:150
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
void clear()
Definition: DetourNode.h:114
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:523
Definition: DetourNode.h:34
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:217
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:125
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1139
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1131
float pos[3]
Position of the node.
Definition: DetourNode.h:36
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
Definition: DetourNode.h:26
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:64
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:160
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 char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:185
static const unsigned int DT_OUT_OF_NODES
Definition: DetourStatus.h:36
dtNode * pop()
Definition: DetourNode.h:124
void dtVnormalize(float *v)
Definition: DetourCommon.h:263
unsigned short neis[DT_VERTS_PER_POLYGON]
Packed data representing neighbor polygons references and flags for each edge.
Definition: DetourNavMesh.h:163
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
Definition: DetourNavMesh.h:153
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:286
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:287
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:70
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:81
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:106
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
T dtSqr(T a)
Definition: DetourCommon.h:67
void dtVsub(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:139
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
dtStatus getEdgeMidPoint(dtPolyRef from, dtPolyRef to, float *mid) const
Returns edge mid point between two polygons.
Definition: DetourNavMeshQuery.cpp:2241
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:147
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:156
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1269
float cost
Cost from previous node to current node.
Definition: DetourNode.h:37
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:169
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:285
void modify(dtNode *node)
Definition: DetourNode.h:138
Definition: DetourNavMesh.h:279
float total
Cost up to the node.
Definition: DetourNode.h:38
void clear()
Definition: DetourNode.cpp:68
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
void push(dtNode *node)
Definition: DetourNode.h:132
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:84
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

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.

2967 {
2968  dtAssert(m_nav);
2970 
2971  *resultCount = 0;
2972 
2973  // Validate input
2974  if (!startRef || !m_nav->isValidPolyRef(startRef))
2975  return DT_FAILURE | DT_INVALID_PARAM;
2976 
2977  static const int MAX_STACK = 48;
2978  dtNode* stack[MAX_STACK];
2979  int nstack = 0;
2980 
2981  m_tinyNodePool->clear();
2982 
2983  dtNode* startNode = m_tinyNodePool->getNode(startRef);
2984  startNode->pidx = 0;
2985  startNode->id = startRef;
2986  startNode->flags = DT_NODE_CLOSED;
2987  stack[nstack++] = startNode;
2988 
2989  const float radiusSqr = dtSqr(radius);
2990 
2991  float pa[DT_VERTS_PER_POLYGON*3];
2992  float pb[DT_VERTS_PER_POLYGON*3];
2993 
2994  dtStatus status = DT_SUCCESS;
2995 
2996  int n = 0;
2997  if (n < maxResult)
2998  {
2999  resultRef[n] = startNode->id;
3000  if (resultParent)
3001  resultParent[n] = 0;
3002  ++n;
3003  }
3004  else
3005  {
3006  status |= DT_BUFFER_TOO_SMALL;
3007  }
3008 
3009  while (nstack)
3010  {
3011  // Pop front.
3012  dtNode* curNode = stack[0];
3013  for (int i = 0; i < nstack-1; ++i)
3014  stack[i] = stack[i+1];
3015  nstack--;
3016 
3017  // Get poly and tile.
3018  // The API input has been cheked already, skip checking internal data.
3019  const dtPolyRef curRef = curNode->id;
3020  const dtMeshTile* curTile = 0;
3021  const dtPoly* curPoly = 0;
3022  m_nav->getTileAndPolyByRefUnsafe(curRef, &curTile, &curPoly);
3023 
3024  for (unsigned int i = curPoly->firstLink; i != DT_NULL_LINK; i = curTile->links[i].next)
3025  {
3026  const dtLink* link = &curTile->links[i];
3027  dtPolyRef neighbourRef = link->ref;
3028  // Skip invalid neighbours.
3029  if (!neighbourRef)
3030  continue;
3031 
3032  // Skip if cannot alloca more nodes.
3033  dtNode* neighbourNode = m_tinyNodePool->getNode(neighbourRef);
3034  if (!neighbourNode)
3035  continue;
3036  // Skip visited.
3037  if (neighbourNode->flags & DT_NODE_CLOSED)
3038  continue;
3039 
3040  // Expand to neighbour
3041  const dtMeshTile* neighbourTile = 0;
3042  const dtPoly* neighbourPoly = 0;
3043  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
3044 
3045  // Skip off-mesh connections.
3046  if (neighbourPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
3047  continue;
3048 
3049  // Do not advance if the polygon is excluded by the filter.
3050  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
3051  continue;
3052 
3053  // Find edge and calc distance to the edge.
3054  float va[3], vb[3];
3055  if (!getPortalPoints(curRef, curPoly, curTile, neighbourRef, neighbourPoly, neighbourTile, va, vb))
3056  continue;
3057 
3058  // If the circle is not touching the next polygon, skip it.
3059  float tseg;
3060  float distSqr = dtDistancePtSegSqr2D(centerPos, va, vb, tseg);
3061  if (distSqr > radiusSqr)
3062  continue;
3063 
3064  // Mark node visited, this is done before the overlap test so that
3065  // we will not visit the poly again if the test fails.
3066  neighbourNode->flags |= DT_NODE_CLOSED;
3067  neighbourNode->pidx = m_tinyNodePool->getNodeIdx(curNode);
3068 
3069  // Check that the polygon does not collide with existing polygons.
3070 
3071  // Collect vertices of the neighbour poly.
3072  const int npa = neighbourPoly->vertCount;
3073  for (int k = 0; k < npa; ++k)
3074  dtVcopy(&pa[k*3], &neighbourTile->verts[neighbourPoly->verts[k]*3]);
3075 
3076  bool overlap = false;
3077  for (int j = 0; j < n; ++j)
3078  {
3079  dtPolyRef pastRef = resultRef[j];
3080 
3081  // Connected polys do not overlap.
3082  bool connected = false;
3083  for (unsigned int k = curPoly->firstLink; k != DT_NULL_LINK; k = curTile->links[k].next)
3084  {
3085  if (curTile->links[k].ref == pastRef)
3086  {
3087  connected = true;
3088  break;
3089  }
3090  }
3091  if (connected)
3092  continue;
3093 
3094  // Potentially overlapping.
3095  const dtMeshTile* pastTile = 0;
3096  const dtPoly* pastPoly = 0;
3097  m_nav->getTileAndPolyByRefUnsafe(pastRef, &pastTile, &pastPoly);
3098 
3099  // Get vertices and test overlap
3100  const int npb = pastPoly->vertCount;
3101  for (int k = 0; k < npb; ++k)
3102  dtVcopy(&pb[k*3], &pastTile->verts[pastPoly->verts[k]*3]);
3103 
3104  if (dtOverlapPolyPoly2D(pa,npa, pb,npb))
3105  {
3106  overlap = true;
3107  break;
3108  }
3109  }
3110  if (overlap)
3111  continue;
3112 
3113  // This poly is fine, store and advance to the poly.
3114  if (n < maxResult)
3115  {
3116  resultRef[n] = neighbourRef;
3117  if (resultParent)
3118  resultParent[n] = curRef;
3119  ++n;
3120  }
3121  else
3122  {
3123  status |= DT_BUFFER_TOO_SMALL;
3124  }
3125 
3126  if (nstack < MAX_STACK)
3127  {
3128  stack[nstack++] = neighbourNode;
3129  }
3130  }
3131  }
3132 
3133  *resultCount = n;
3134 
3135  return status;
3136 }
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
Definition: DetourNode.h:34
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:125
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:2146
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1139
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1131
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
Definition: BnetFileGenerator.h:49
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:64
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:160
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 char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:185
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
Definition: DetourNavMesh.h:153
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:286
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
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:287
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:106
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
T dtSqr(T a)
Definition: DetourCommon.h:67
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:521
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:147
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:156
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:169
Definition: DetourNavMesh.h:279
void clear()
Definition: DetourNode.cpp:68
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:57
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:84
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

dtStatus dtNavMeshQuery::findNearestPoly ( const float *  center,
const float *  extents,
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]extentsThe 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.
Warning
This function is not suitable for large area searches. If the search extents overlaps more than MAX_SEARCH (128) polygons it may return an invalid result.
713 {
714  dtAssert(m_nav);
715 
716  *nearestRef = 0;
717 
718  // Get nearby polygons from proximity grid.
719  const int MAX_SEARCH = 128;
720  dtPolyRef polys[MAX_SEARCH];
721  int polyCount = 0;
722  if (dtStatusFailed(queryPolygons(center, extents, filter, polys, &polyCount, MAX_SEARCH)))
723  return DT_FAILURE | DT_INVALID_PARAM;
724 
725  // Find nearest polygon amongst the nearby polygons.
726  dtPolyRef nearest = 0;
727  float nearestDistanceSqr = FLT_MAX;
728  for (int i = 0; i < polyCount; ++i)
729  {
730  dtPolyRef ref = polys[i];
731  float closestPtPoly[3];
732  float diff[3];
733  bool posOverPoly = false;
734  float d = 0;
735  closestPointOnPoly(ref, center, closestPtPoly, &posOverPoly);
736 
737  // If a point is directly over a polygon and closer than
738  // climb height, favor that instead of straight line nearest point.
739  dtVsub(diff, center, closestPtPoly);
740  if (posOverPoly)
741  {
742  const dtMeshTile* tile = 0;
743  const dtPoly* poly = 0;
744  m_nav->getTileAndPolyByRefUnsafe(polys[i], &tile, &poly);
745  d = dtAbs(diff[1]) - tile->header->walkableClimb;
746  d = d > 0 ? d*d : 0;
747  }
748  else
749  {
750  d = dtVlenSqr(diff);
751  }
752 
753  if (d < nearestDistanceSqr)
754  {
755  if (nearestPt)
756  dtVcopy(nearestPt, closestPtPoly);
757  nearestDistanceSqr = d;
758  nearest = ref;
759  }
760  }
761 
762  if (nearestRef)
763  *nearestRef = nearest;
764 
765  return DT_SUCCESS;
766 }
dtStatus queryPolygons(const float *center, const float *extents, const dtQueryFilter *filter, dtPolyRef *polys, int *polyCount, const int maxPolys) const
Definition: DetourNavMeshQuery.cpp:872
float dtVlenSqr(const float *v)
Definition: DetourCommon.h:208
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:284
float walkableClimb
The maximum climb height of the agents using the tile.
Definition: DetourNavMesh.h:269
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1131
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
T dtAbs(T a)
Definition: DetourCommon.h:62
Definition: DetourNavMesh.h:153
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
void dtVsub(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:139
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
Definition: DetourNavMesh.h:279
dtStatus closestPointOnPoly(dtPolyRef ref, const float *pos, float *closest, bool *posOverPoly) const
Definition: DetourNavMeshQuery.cpp:505
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:

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.)

927 {
928  dtAssert(m_nav);
931 
932  *pathCount = 0;
933 
934  if (!startRef || !endRef)
935  return DT_FAILURE | DT_INVALID_PARAM;
936 
937  if (!maxPath)
938  return DT_FAILURE | DT_INVALID_PARAM;
939 
940  // Validate input
941  if (!m_nav->isValidPolyRef(startRef) || !m_nav->isValidPolyRef(endRef))
942  return DT_FAILURE | DT_INVALID_PARAM;
943 
944  if (startRef == endRef)
945  {
946  path[0] = startRef;
947  *pathCount = 1;
948  return DT_SUCCESS;
949  }
950 
951  m_nodePool->clear();
952  m_openList->clear();
953 
954  dtNode* startNode = m_nodePool->getNode(startRef);
955  dtVcopy(startNode->pos, startPos);
956  startNode->pidx = 0;
957  startNode->cost = 0;
958  startNode->total = dtVdist(startPos, endPos) * H_SCALE;
959  startNode->id = startRef;
960  startNode->flags = DT_NODE_OPEN;
961  m_openList->push(startNode);
962 
963  dtNode* lastBestNode = startNode;
964  float lastBestNodeCost = startNode->total;
965 
966  dtStatus status = DT_SUCCESS;
967 
968  while (!m_openList->empty())
969  {
970  // Remove node from open list and put it in closed list.
971  dtNode* bestNode = m_openList->pop();
972  bestNode->flags &= ~DT_NODE_OPEN;
973  bestNode->flags |= DT_NODE_CLOSED;
974 
975  // Reached the goal, stop searching.
976  if (bestNode->id == endRef)
977  {
978  lastBestNode = bestNode;
979  break;
980  }
981 
982  // Get current poly and tile.
983  // The API input has been cheked already, skip checking internal data.
984  const dtPolyRef bestRef = bestNode->id;
985  const dtMeshTile* bestTile = 0;
986  const dtPoly* bestPoly = 0;
987  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
988 
989  // Get parent poly and tile.
990  dtPolyRef parentRef = 0;
991  const dtMeshTile* parentTile = 0;
992  const dtPoly* parentPoly = 0;
993  if (bestNode->pidx)
994  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
995  if (parentRef)
996  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
997 
998  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
999  {
1000  dtPolyRef neighbourRef = bestTile->links[i].ref;
1001 
1002  // Skip invalid ids and do not expand back to where we came from.
1003  if (!neighbourRef || neighbourRef == parentRef)
1004  continue;
1005 
1006  // Get neighbour poly and tile.
1007  // The API input has been cheked already, skip checking internal data.
1008  const dtMeshTile* neighbourTile = 0;
1009  const dtPoly* neighbourPoly = 0;
1010  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
1011 
1012  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
1013  continue;
1014 
1015  // deal explicitly with crossing tile boundaries
1016  unsigned char crossSide = 0;
1017  if (bestTile->links[i].side != 0xff)
1018  crossSide = bestTile->links[i].side >> 1;
1019 
1020  // get the node
1021  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef, crossSide);
1022  if (!neighbourNode)
1023  {
1024  status |= DT_OUT_OF_NODES;
1025  continue;
1026  }
1027 
1028  // If the node is visited the first time, calculate node position.
1029  if (neighbourNode->flags == 0)
1030  {
1031  getEdgeMidPoint(bestRef, bestPoly, bestTile,
1032  neighbourRef, neighbourPoly, neighbourTile,
1033  neighbourNode->pos);
1034  }
1035 
1036  // Calculate cost and heuristic.
1037  float cost = 0;
1038  float heuristic = 0;
1039 
1040  // Special case for last node.
1041  if (neighbourRef == endRef)
1042  {
1043  // Cost
1044  const float curCost = filter->getCost(bestNode->pos, neighbourNode->pos,
1045  parentRef, parentTile, parentPoly,
1046  bestRef, bestTile, bestPoly,
1047  neighbourRef, neighbourTile, neighbourPoly);
1048  const float endCost = filter->getCost(neighbourNode->pos, endPos,
1049  bestRef, bestTile, bestPoly,
1050  neighbourRef, neighbourTile, neighbourPoly,
1051  0, 0, 0);
1052 
1053  cost = bestNode->cost + curCost + endCost;
1054  heuristic = 0;
1055  }
1056  else
1057  {
1058  // Cost
1059  const float curCost = filter->getCost(bestNode->pos, neighbourNode->pos,
1060  parentRef, parentTile, parentPoly,
1061  bestRef, bestTile, bestPoly,
1062  neighbourRef, neighbourTile, neighbourPoly);
1063  cost = bestNode->cost + curCost;
1064  heuristic = dtVdist(neighbourNode->pos, endPos)*H_SCALE;
1065  }
1066 
1067  const float total = cost + heuristic;
1068 
1069  // The node is already in open list and the new result is worse, skip.
1070  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
1071  continue;
1072  // The node is already visited and process, and the new result is worse, skip.
1073  if ((neighbourNode->flags & DT_NODE_CLOSED) && total >= neighbourNode->total)
1074  continue;
1075 
1076  // Add or update the node.
1077  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
1078  neighbourNode->id = neighbourRef;
1079  neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED);
1080  neighbourNode->cost = cost;
1081  neighbourNode->total = total;
1082 
1083  if (neighbourNode->flags & DT_NODE_OPEN)
1084  {
1085  // Already in open, update node location.
1086  m_openList->modify(neighbourNode);
1087  }
1088  else
1089  {
1090  // Put the node in open list.
1091  neighbourNode->flags |= DT_NODE_OPEN;
1092  m_openList->push(neighbourNode);
1093  }
1094 
1095  // Update nearest node to target so far.
1096  if (heuristic < lastBestNodeCost)
1097  {
1098  lastBestNodeCost = heuristic;
1099  lastBestNode = neighbourNode;
1100  }
1101  }
1102  }
1103 
1104  if (lastBestNode->id != endRef)
1105  status |= DT_PARTIAL_RESULT;
1106 
1107  // Reverse the path.
1108  dtNode* prev = 0;
1109  dtNode* node = lastBestNode;
1110  do
1111  {
1112  dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
1113  node->pidx = m_nodePool->getNodeIdx(prev);
1114  prev = node;
1115  node = next;
1116  }
1117  while (node);
1118 
1119  // Store path
1120  node = prev;
1121  int n = 0;
1122  do
1123  {
1124  path[n++] = node->id;
1125  if (n >= maxPath)
1126  {
1127  status |= DT_BUFFER_TOO_SMALL;
1128  break;
1129  }
1130  node = m_nodePool->getNodeAtIdx(node->pidx);
1131  }
1132  while (node);
1133 
1134  *pathCount = n;
1135 
1136  return status;
1137 }
bool empty() const
Definition: DetourNode.h:150
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
void clear()
Definition: DetourNode.h:114
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:523
Definition: DetourNode.h:34
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:217
int next(int i, int n)
Definition: RecastContour.cpp:469
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1139
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1131
float pos[3]
Position of the node.
Definition: DetourNode.h:36
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
Definition: DetourNode.h:26
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:64
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
unsigned int dtStatus
Definition: DetourStatus.h:22
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 unsigned int DT_OUT_OF_NODES
Definition: DetourStatus.h:36
dtNode * pop()
Definition: DetourNode.h:124
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
Definition: DetourNavMesh.h:153
static const unsigned int DT_PARTIAL_RESULT
Definition: DetourStatus.h:37
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:287
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:70
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:106
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
dtStatus getEdgeMidPoint(dtPolyRef from, dtPolyRef to, float *mid) const
Returns edge mid point between two polygons.
Definition: DetourNavMeshQuery.cpp:2241
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:156
float cost
Cost from previous node to current node.
Definition: DetourNode.h:37
void modify(dtNode *node)
Definition: DetourNode.h:138
static const float H_SCALE
Definition: DetourNavMeshQuery.cpp:104
Definition: DetourNavMesh.h:279
float total
Cost up to the node.
Definition: DetourNode.h:38
void clear()
Definition: DetourNode.cpp:68
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
void push(dtNode *node)
Definition: DetourNode.h:132
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:84
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:

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.

2612 {
2613  dtAssert(m_nav);
2616 
2617  *resultCount = 0;
2618 
2619  // Validate input
2620  if (!startRef || !m_nav->isValidPolyRef(startRef))
2621  return DT_FAILURE | DT_INVALID_PARAM;
2622 
2623  m_nodePool->clear();
2624  m_openList->clear();
2625 
2626  dtNode* startNode = m_nodePool->getNode(startRef);
2627  dtVcopy(startNode->pos, centerPos);
2628  startNode->pidx = 0;
2629  startNode->cost = 0;
2630  startNode->total = 0;
2631  startNode->id = startRef;
2632  startNode->flags = DT_NODE_OPEN;
2633  m_openList->push(startNode);
2634 
2635  dtStatus status = DT_SUCCESS;
2636 
2637  int n = 0;
2638  if (n < maxResult)
2639  {
2640  if (resultRef)
2641  resultRef[n] = startNode->id;
2642  if (resultParent)
2643  resultParent[n] = 0;
2644  if (resultCost)
2645  resultCost[n] = 0;
2646  ++n;
2647  }
2648  else
2649  {
2650  status |= DT_BUFFER_TOO_SMALL;
2651  }
2652 
2653  const float radiusSqr = dtSqr(radius);
2654 
2655  while (!m_openList->empty())
2656  {
2657  dtNode* bestNode = m_openList->pop();
2658  bestNode->flags &= ~DT_NODE_OPEN;
2659  bestNode->flags |= DT_NODE_CLOSED;
2660 
2661  // Get poly and tile.
2662  // The API input has been cheked already, skip checking internal data.
2663  const dtPolyRef bestRef = bestNode->id;
2664  const dtMeshTile* bestTile = 0;
2665  const dtPoly* bestPoly = 0;
2666  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
2667 
2668  // Get parent poly and tile.
2669  dtPolyRef parentRef = 0;
2670  const dtMeshTile* parentTile = 0;
2671  const dtPoly* parentPoly = 0;
2672  if (bestNode->pidx)
2673  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
2674  if (parentRef)
2675  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
2676 
2677  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
2678  {
2679  const dtLink* link = &bestTile->links[i];
2680  dtPolyRef neighbourRef = link->ref;
2681  // Skip invalid neighbours and do not follow back to parent.
2682  if (!neighbourRef || neighbourRef == parentRef)
2683  continue;
2684 
2685  // Expand to neighbour
2686  const dtMeshTile* neighbourTile = 0;
2687  const dtPoly* neighbourPoly = 0;
2688  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
2689 
2690  // Do not advance if the polygon is excluded by the filter.
2691  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
2692  continue;
2693 
2694  // Find edge and calc distance to the edge.
2695  float va[3], vb[3];
2696  if (!getPortalPoints(bestRef, bestPoly, bestTile, neighbourRef, neighbourPoly, neighbourTile, va, vb))
2697  continue;
2698 
2699  // If the circle is not touching the next polygon, skip it.
2700  float tseg;
2701  float distSqr = dtDistancePtSegSqr2D(centerPos, va, vb, tseg);
2702  if (distSqr > radiusSqr)
2703  continue;
2704 
2705  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
2706  if (!neighbourNode)
2707  {
2708  status |= DT_OUT_OF_NODES;
2709  continue;
2710  }
2711 
2712  if (neighbourNode->flags & DT_NODE_CLOSED)
2713  continue;
2714 
2715  // Cost
2716  if (neighbourNode->flags == 0)
2717  dtVlerp(neighbourNode->pos, va, vb, 0.5f);
2718 
2719  const float total = bestNode->total + dtVdist(bestNode->pos, neighbourNode->pos);
2720 
2721  // The node is already in open list and the new result is worse, skip.
2722  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
2723  continue;
2724 
2725  neighbourNode->id = neighbourRef;
2726  neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED);
2727  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
2728  neighbourNode->total = total;
2729 
2730  if (neighbourNode->flags & DT_NODE_OPEN)
2731  {
2732  m_openList->modify(neighbourNode);
2733  }
2734  else
2735  {
2736  if (n < maxResult)
2737  {
2738  if (resultRef)
2739  resultRef[n] = neighbourNode->id;
2740  if (resultParent)
2741  resultParent[n] = m_nodePool->getNodeAtIdx(neighbourNode->pidx)->id;
2742  if (resultCost)
2743  resultCost[n] = neighbourNode->total;
2744  ++n;
2745  }
2746  else
2747  {
2748  status |= DT_BUFFER_TOO_SMALL;
2749  }
2750  neighbourNode->flags = DT_NODE_OPEN;
2751  m_openList->push(neighbourNode);
2752  }
2753  }
2754  }
2755 
2756  *resultCount = n;
2757 
2758  return status;
2759 }
bool empty() const
Definition: DetourNode.h:150
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
void clear()
Definition: DetourNode.h:114
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:523
Definition: DetourNode.h:34
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:117
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:217
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:125
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:2146
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1139
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1131
float pos[3]
Position of the node.
Definition: DetourNode.h:36
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
Definition: DetourNode.h:26
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:64
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
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:124
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
Definition: DetourNavMesh.h:153
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:287
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:70
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:106
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
T dtSqr(T a)
Definition: DetourCommon.h:67
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:156
float cost
Cost from previous node to current node.
Definition: DetourNode.h:37
void modify(dtNode *node)
Definition: DetourNode.h:138
Definition: DetourNavMesh.h:279
float total
Cost up to the node.
Definition: DetourNode.h:38
void clear()
Definition: DetourNode.cpp:68
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
void push(dtNode *node)
Definition: DetourNode.h:132
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:84
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

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.

2787 {
2788  dtAssert(m_nav);
2791 
2792  *resultCount = 0;
2793 
2794  // Validate input
2795  if (!startRef || !m_nav->isValidPolyRef(startRef))
2796  return DT_FAILURE | DT_INVALID_PARAM;
2797 
2798  m_nodePool->clear();
2799  m_openList->clear();
2800 
2801  float centerPos[3] = {0,0,0};
2802  for (int i = 0; i < nverts; ++i)
2803  dtVadd(centerPos,centerPos,&verts[i*3]);
2804  dtVscale(centerPos,centerPos,1.0f/nverts);
2805 
2806  dtNode* startNode = m_nodePool->getNode(startRef);
2807  dtVcopy(startNode->pos, centerPos);
2808  startNode->pidx = 0;
2809  startNode->cost = 0;
2810  startNode->total = 0;
2811  startNode->id = startRef;
2812  startNode->flags = DT_NODE_OPEN;
2813  m_openList->push(startNode);
2814 
2815  dtStatus status = DT_SUCCESS;
2816 
2817  int n = 0;
2818  if (n < maxResult)
2819  {
2820  if (resultRef)
2821  resultRef[n] = startNode->id;
2822  if (resultParent)
2823  resultParent[n] = 0;
2824  if (resultCost)
2825  resultCost[n] = 0;
2826  ++n;
2827  }
2828  else
2829  {
2830  status |= DT_BUFFER_TOO_SMALL;
2831  }
2832 
2833  while (!m_openList->empty())
2834  {
2835  dtNode* bestNode = m_openList->pop();
2836  bestNode->flags &= ~DT_NODE_OPEN;
2837  bestNode->flags |= DT_NODE_CLOSED;
2838 
2839  // Get poly and tile.
2840  // The API input has been cheked already, skip checking internal data.
2841  const dtPolyRef bestRef = bestNode->id;
2842  const dtMeshTile* bestTile = 0;
2843  const dtPoly* bestPoly = 0;
2844  m_nav->getTileAndPolyByRefUnsafe(bestRef, &bestTile, &bestPoly);
2845 
2846  // Get parent poly and tile.
2847  dtPolyRef parentRef = 0;
2848  const dtMeshTile* parentTile = 0;
2849  const dtPoly* parentPoly = 0;
2850  if (bestNode->pidx)
2851  parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
2852  if (parentRef)
2853  m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly);
2854 
2855  for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
2856  {
2857  const dtLink* link = &bestTile->links[i];
2858  dtPolyRef neighbourRef = link->ref;
2859  // Skip invalid neighbours and do not follow back to parent.
2860  if (!neighbourRef || neighbourRef == parentRef)
2861  continue;
2862 
2863  // Expand to neighbour
2864  const dtMeshTile* neighbourTile = 0;
2865  const dtPoly* neighbourPoly = 0;
2866  m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly);
2867 
2868  // Do not advance if the polygon is excluded by the filter.
2869  if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
2870  continue;
2871 
2872  // Find edge and calc distance to the edge.
2873  float va[3], vb[3];
2874  if (!getPortalPoints(bestRef, bestPoly, bestTile, neighbourRef, neighbourPoly, neighbourTile, va, vb))
2875  continue;
2876 
2877  // If the poly is not touching the edge to the next polygon, skip the connection it.
2878  float tmin, tmax;
2879  int segMin, segMax;
2880  if (!dtIntersectSegmentPoly2D(va, vb, verts, nverts, tmin, tmax, segMin, segMax))
2881  continue;
2882  if (tmin > 1.0f || tmax < 0.0f)
2883  continue;
2884 
2885  dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
2886  if (!neighbourNode)
2887  {
2888  status |= DT_OUT_OF_NODES;
2889  continue;
2890  }
2891 
2892  if (neighbourNode->flags & DT_NODE_CLOSED)
2893  continue;
2894 
2895  // Cost
2896  if (neighbourNode->flags == 0)
2897  dtVlerp(neighbourNode->pos, va, vb, 0.5f);
2898 
2899  const float total = bestNode->total + dtVdist(bestNode->pos, neighbourNode->pos);
2900 
2901  // The node is already in open list and the new result is worse, skip.
2902  if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total)
2903  continue;
2904 
2905  neighbourNode->id = neighbourRef;
2906  neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED);
2907  neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
2908  neighbourNode->total = total;
2909 
2910  if (neighbourNode->flags & DT_NODE_OPEN)
2911  {
2912  m_openList->modify(neighbourNode);
2913  }
2914  else
2915  {
2916  if (n < maxResult)
2917  {
2918  if (resultRef)
2919  resultRef[n] = neighbourNode->id;
2920  if (resultParent)
2921  resultParent[n] = m_nodePool->getNodeAtIdx(neighbourNode->pidx)->id;
2922  if (resultCost)
2923  resultCost[n] = neighbourNode->total;
2924  ++n;
2925  }
2926  else
2927  {
2928  status |= DT_BUFFER_TOO_SMALL;
2929  }
2930  neighbourNode->flags = DT_NODE_OPEN;
2931  m_openList->push(neighbourNode);
2932  }
2933  }
2934  }
2935 
2936  *resultCount = n;
2937 
2938  return status;
2939 }
bool empty() const
Definition: DetourNode.h:150
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
void clear()
Definition: DetourNode.h:114
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:523
Definition: DetourNode.h:34
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:117
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:217
Position const centerPos
Definition: boss_blood_queen_lana_thel.cpp:125
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:2146
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1139
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1131
float pos[3]
Position of the node.
Definition: DetourNode.h:36
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
Definition: DetourNode.h:26
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:64
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
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 dtVadd(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:128
static const unsigned int DT_OUT_OF_NODES
Definition: DetourStatus.h:36
dtNode * pop()
Definition: DetourNode.h:124
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
Definition: DetourNavMesh.h:153
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:287
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:70
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:106
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:156
float cost
Cost from previous node to current node.
Definition: DetourNode.h:37
void modify(dtNode *node)
Definition: DetourNode.h:138
void dtVscale(float *dest, const float *v, const float t)
Definition: DetourCommon.h:150
Definition: DetourNavMesh.h:279
float total
Cost up to the node.
Definition: DetourNode.h:38
void clear()
Definition: DetourNode.cpp:68
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
void push(dtNode *node)
Definition: DetourNode.h:132
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:84
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

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

+ Here is the call graph for this function:

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

+ Here is the call graph for this function:

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.

1711 {
1712  dtAssert(m_nav);
1713 
1714  *straightPathCount = 0;
1715 
1716  if (!maxStraightPath)
1717  return DT_FAILURE | DT_INVALID_PARAM;
1718 
1719  if (!path[0])
1720  return DT_FAILURE | DT_INVALID_PARAM;
1721 
1722  dtStatus stat = 0;
1723 
1724  // TODO: Should this be callers responsibility?
1725  float closestStartPos[3];
1726  if (dtStatusFailed(closestPointOnPolyBoundary(path[0], startPos, closestStartPos)))
1727  return DT_FAILURE | DT_INVALID_PARAM;
1728 
1729  float closestEndPos[3];
1730  if (dtStatusFailed(closestPointOnPolyBoundary(path[pathSize-1], endPos, closestEndPos)))
1731  return DT_FAILURE | DT_INVALID_PARAM;
1732 
1733  // Add start point.
1734  stat = appendVertex(closestStartPos, DT_STRAIGHTPATH_START, path[0],
1735  straightPath, straightPathFlags, straightPathRefs,
1736  straightPathCount, maxStraightPath);
1737  if (stat != DT_IN_PROGRESS)
1738  return stat;
1739 
1740  if (pathSize > 1)
1741  {
1742  float portalApex[3], portalLeft[3], portalRight[3];
1743  dtVcopy(portalApex, closestStartPos);
1744  dtVcopy(portalLeft, portalApex);
1745  dtVcopy(portalRight, portalApex);
1746  int apexIndex = 0;
1747  int leftIndex = 0;
1748  int rightIndex = 0;
1749 
1750  unsigned char leftPolyType = 0;
1751  unsigned char rightPolyType = 0;
1752 
1753  dtPolyRef leftPolyRef = path[0];
1754  dtPolyRef rightPolyRef = path[0];
1755 
1756  for (int i = 0; i < pathSize; ++i)
1757  {
1758  float left[3], right[3];
1759  unsigned char fromType, toType;
1760 
1761  if (i+1 < pathSize)
1762  {
1763  // Next portal.
1764  if (dtStatusFailed(getPortalPoints(path[i], path[i+1], left, right, fromType, toType)))
1765  {
1766  // Failed to get portal points, in practice this means that path[i+1] is invalid polygon.
1767  // Clamp the end point to path[i], and return the path so far.
1768 
1769  if (dtStatusFailed(closestPointOnPolyBoundary(path[i], endPos, closestEndPos)))
1770  {
1771  // This should only happen when the first polygon is invalid.
1772  return DT_FAILURE | DT_INVALID_PARAM;
1773  }
1774 
1775  // Apeend portals along the current straight path segment.
1777  {
1778  stat = appendPortals(apexIndex, i, closestEndPos, path,
1779  straightPath, straightPathFlags, straightPathRefs,
1780  straightPathCount, maxStraightPath, options);
1781  }
1782 
1783  stat = appendVertex(closestEndPos, 0, path[i],
1784  straightPath, straightPathFlags, straightPathRefs,
1785  straightPathCount, maxStraightPath);
1786 
1787  return DT_SUCCESS | DT_PARTIAL_RESULT | ((*straightPathCount >= maxStraightPath) ? DT_BUFFER_TOO_SMALL : 0);
1788  }
1789 
1790  // If starting really close the portal, advance.
1791  if (i == 0)
1792  {
1793  float t;
1794  if (dtDistancePtSegSqr2D(portalApex, left, right, t) < dtSqr(0.001f))
1795  continue;
1796  }
1797  }
1798  else
1799  {
1800  // End of the path.
1801  dtVcopy(left, closestEndPos);
1802  dtVcopy(right, closestEndPos);
1803 
1804  fromType = toType = DT_POLYTYPE_GROUND;
1805  }
1806 
1807  // Right vertex.
1808  if (dtTriArea2D(portalApex, portalRight, right) <= 0.0f)
1809  {
1810  if (dtVequal(portalApex, portalRight) || dtTriArea2D(portalApex, portalLeft, right) > 0.0f)
1811  {
1812  dtVcopy(portalRight, right);
1813  rightPolyRef = (i+1 < pathSize) ? path[i+1] : 0;
1814  rightPolyType = toType;
1815  rightIndex = i;
1816  }
1817  else
1818  {
1819  // Append portals along the current straight path segment.
1821  {
1822  stat = appendPortals(apexIndex, leftIndex, portalLeft, path,
1823  straightPath, straightPathFlags, straightPathRefs,
1824  straightPathCount, maxStraightPath, options);
1825  if (stat != DT_IN_PROGRESS)
1826  return stat;
1827  }
1828 
1829  dtVcopy(portalApex, portalLeft);
1830  apexIndex = leftIndex;
1831 
1832  unsigned char flags = 0;
1833  if (!leftPolyRef)
1834  flags = DT_STRAIGHTPATH_END;
1835  else if (leftPolyType == DT_POLYTYPE_OFFMESH_CONNECTION)
1837  dtPolyRef ref = leftPolyRef;
1838 
1839  // Append or update vertex
1840  stat = appendVertex(portalApex, flags, ref,
1841  straightPath, straightPathFlags, straightPathRefs,
1842  straightPathCount, maxStraightPath);
1843  if (stat != DT_IN_PROGRESS)
1844  return stat;
1845 
1846  dtVcopy(portalLeft, portalApex);
1847  dtVcopy(portalRight, portalApex);
1848  leftIndex = apexIndex;
1849  rightIndex = apexIndex;
1850 
1851  // Restart
1852  i = apexIndex;
1853 
1854  continue;
1855  }
1856  }
1857 
1858  // Left vertex.
1859  if (dtTriArea2D(portalApex, portalLeft, left) >= 0.0f)
1860  {
1861  if (dtVequal(portalApex, portalLeft) || dtTriArea2D(portalApex, portalRight, left) < 0.0f)
1862  {
1863  dtVcopy(portalLeft, left);
1864  leftPolyRef = (i+1 < pathSize) ? path[i+1] : 0;
1865  leftPolyType = toType;
1866  leftIndex = i;
1867  }
1868  else
1869  {
1870  // Append portals along the current straight path segment.
1872  {
1873  stat = appendPortals(apexIndex, rightIndex, portalRight, path,
1874  straightPath, straightPathFlags, straightPathRefs,
1875  straightPathCount, maxStraightPath, options);
1876  if (stat != DT_IN_PROGRESS)
1877  return stat;
1878  }
1879 
1880  dtVcopy(portalApex, portalRight);
1881  apexIndex = rightIndex;
1882 
1883  unsigned char flags = 0;
1884  if (!rightPolyRef)
1885  flags = DT_STRAIGHTPATH_END;
1886  else if (rightPolyType == DT_POLYTYPE_OFFMESH_CONNECTION)
1888  dtPolyRef ref = rightPolyRef;
1889 
1890  // Append or update vertex
1891  stat = appendVertex(portalApex, flags, ref,
1892  straightPath, straightPathFlags, straightPathRefs,
1893  straightPathCount, maxStraightPath);
1894  if (stat != DT_IN_PROGRESS)
1895  return stat;
1896 
1897  dtVcopy(portalLeft, portalApex);
1898  dtVcopy(portalRight, portalApex);
1899  leftIndex = apexIndex;
1900  rightIndex = apexIndex;
1901 
1902  // Restart
1903  i = apexIndex;
1904 
1905  continue;
1906  }
1907  }
1908  }
1909 
1910  // Append portals along the current straight path segment.
1912  {
1913  stat = appendPortals(apexIndex, pathSize-1, closestEndPos, path,
1914  straightPath, straightPathFlags, straightPathRefs,
1915  straightPathCount, maxStraightPath, options);
1916  if (stat != DT_IN_PROGRESS)
1917  return stat;
1918  }
1919  }
1920 
1921  stat = appendVertex(closestEndPos, DT_STRAIGHTPATH_END, 0,
1922  straightPath, straightPathFlags, straightPathRefs,
1923  straightPathCount, maxStraightPath);
1924 
1925  return DT_SUCCESS | ((*straightPathCount >= maxStraightPath) ? DT_BUFFER_TOO_SMALL : 0);
1926 }
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
float dtTriArea2D(const float *a, const float *b, const float *c)
Definition: DetourCommon.h:316
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:1610
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:2146
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int dtStatus
Definition: DetourStatus.h:22
dtStatus closestPointOnPolyBoundary(dtPolyRef ref, const float *pos, float *closest) const
Definition: DetourNavMeshQuery.cpp:601
The vertex is the start position in the path.
Definition: DetourNavMesh.h:110
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:111
Add a vertex at every polygon edge crossing.
Definition: DetourNavMesh.h:119
static const unsigned int DT_PARTIAL_RESULT
Definition: DetourStatus.h:37
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:278
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
Add a vertex at every polygon edge crossing where area changes.
Definition: DetourNavMesh.h:118
T dtSqr(T a)
Definition: DetourCommon.h:67
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:147
uint8 flags
Definition: DisableMgr.cpp:44
static const unsigned int DT_IN_PROGRESS
Definition: DetourStatus.h:27
The vertex is the start of an off-mesh connection.
Definition: DetourNavMesh.h:112
The polygon is a standard convex polygon that is part of the surface of the mesh. ...
Definition: DetourNavMesh.h:145
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:1640
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:

const dtNavMesh* dtNavMeshQuery::getAttachedNavMesh ( ) const
inline

Gets the navigation mesh the query object is using.

Returns
The navigation mesh the query object is using.
470 { return m_nav; }
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
dtStatus dtNavMeshQuery::getEdgeMidPoint ( dtPolyRef  from,
dtPolyRef  to,
float *  mid 
) const
private

Returns edge mid point between two polygons.

2242 {
2243  float left[3], right[3];
2244  unsigned char fromType, toType;
2245  if (dtStatusFailed(getPortalPoints(from, to, left,right, fromType, toType)))
2246  return DT_FAILURE | DT_INVALID_PARAM;
2247  mid[0] = (left[0]+right[0])*0.5f;
2248  mid[1] = (left[1]+right[1])*0.5f;
2249  mid[2] = (left[2]+right[2])*0.5f;
2250  return DT_SUCCESS;
2251 }
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:2146
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
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:

dtStatus dtNavMeshQuery::getEdgeMidPoint ( dtPolyRef  from,
const dtPoly fromPoly,
const dtMeshTile fromTile,
dtPolyRef  to,
const dtPoly toPoly,
const dtMeshTile toTile,
float *  mid 
) const
private
2256 {
2257  float left[3], right[3];
2258  if (dtStatusFailed(getPortalPoints(from, fromPoly, fromTile, to, toPoly, toTile, left, right)))
2259  return DT_FAILURE | DT_INVALID_PARAM;
2260  mid[0] = (left[0]+right[0])*0.5f;
2261  mid[1] = (left[1]+right[1])*0.5f;
2262  mid[2] = (left[2]+right[2])*0.5f;
2263  return DT_SUCCESS;
2264 }
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:2146
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
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:

dtMeshTile* dtNavMeshQuery::getNeighbourTileAt ( int  x,
int  y,
int  side 
) const
private

Returns neighbour tile based on side.

class dtNodePool* dtNavMeshQuery::getNodePool ( ) const
inline

Gets the node pool.

Returns
The node pool.
466 { return m_nodePool; }
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
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.

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

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.

3181 {
3182  dtAssert(m_nav);
3183 
3184  *segmentCount = 0;
3185 
3186  const dtMeshTile* tile = 0;
3187  const dtPoly* poly = 0;
3188  if (dtStatusFailed(m_nav->getTileAndPolyByRef(ref, &tile, &poly)))
3189  return DT_FAILURE | DT_INVALID_PARAM;
3190 
3191  int n = 0;
3192  static const int MAX_INTERVAL = 16;
3193  dtSegInterval ints[MAX_INTERVAL];
3194  int nints;
3195 
3196  const bool storePortals = segmentRefs != 0;
3197 
3198  dtStatus status = DT_SUCCESS;
3199 
3200  for (int i = 0, j = (int)poly->vertCount-1; i < (int)poly->vertCount; j = i++)
3201  {
3202  // Skip non-solid edges.
3203  nints = 0;
3204  if (poly->neis[j] & DT_EXT_LINK)
3205  {
3206  // Tile border.
3207  for (unsigned int k = poly->firstLink; k != DT_NULL_LINK; k = tile->links[k].next)
3208  {
3209  const dtLink* link = &tile->links[k];
3210  if (link->edge == j)
3211  {
3212  if (link->ref != 0)
3213  {
3214  const dtMeshTile* neiTile = 0;
3215  const dtPoly* neiPoly = 0;
3216  m_nav->getTileAndPolyByRefUnsafe(link->ref, &neiTile, &neiPoly);
3217  if (filter->passFilter(link->ref, neiTile, neiPoly))
3218  {
3219  insertInterval(ints, nints, MAX_INTERVAL, link->bmin, link->bmax, link->ref);
3220  }
3221  }
3222  }
3223  }
3224  }
3225  else
3226  {
3227  // Internal edge
3228  dtPolyRef neiRef = 0;
3229  if (poly->neis[j])
3230  {
3231  const unsigned int idx = (unsigned int)(poly->neis[j]-1);
3232  neiRef = m_nav->getPolyRefBase(tile) | idx;
3233  if (!filter->passFilter(neiRef, tile, &tile->polys[idx]))
3234  neiRef = 0;
3235  }
3236 
3237  // If the edge leads to another polygon and portals are not stored, skip.
3238  if (neiRef != 0 && !storePortals)
3239  continue;
3240 
3241  if (n < maxSegments)
3242  {
3243  const float* vj = &tile->verts[poly->verts[j]*3];
3244  const float* vi = &tile->verts[poly->verts[i]*3];
3245  float* seg = &segmentVerts[n*6];
3246  dtVcopy(seg+0, vj);
3247  dtVcopy(seg+3, vi);
3248  if (segmentRefs)
3249  segmentRefs[n] = neiRef;
3250  n++;
3251  }
3252  else
3253  {
3254  status |= DT_BUFFER_TOO_SMALL;
3255  }
3256 
3257  continue;
3258  }
3259 
3260  // Add sentinels
3261  insertInterval(ints, nints, MAX_INTERVAL, -1, 0, 0);
3262  insertInterval(ints, nints, MAX_INTERVAL, 255, 256, 0);
3263 
3264  // Store segments.
3265  const float* vj = &tile->verts[poly->verts[j]*3];
3266  const float* vi = &tile->verts[poly->verts[i]*3];
3267  for (int k = 1; k < nints; ++k)
3268  {
3269  // Portal segment.
3270  if (storePortals && ints[k].ref)
3271  {
3272  const float tmin = ints[k].tmin/255.0f;
3273  const float tmax = ints[k].tmax/255.0f;
3274  if (n < maxSegments)
3275  {
3276  float* seg = &segmentVerts[n*6];
3277  dtVlerp(seg+0, vj,vi, tmin);
3278  dtVlerp(seg+3, vj,vi, tmax);
3279  if (segmentRefs)
3280  segmentRefs[n] = ints[k].ref;
3281  n++;
3282  }
3283  else
3284  {
3285  status |= DT_BUFFER_TOO_SMALL;
3286  }
3287  }
3288 
3289  // Wall segment.
3290  const int imin = ints[k-1].tmax;
3291  const int imax = ints[k].tmin;
3292  if (imin != imax)
3293  {
3294  const float tmin = imin/255.0f;
3295  const float tmax = imax/255.0f;
3296  if (n < maxSegments)
3297  {
3298  float* seg = &segmentVerts[n*6];
3299  dtVlerp(seg+0, vj,vi, tmin);
3300  dtVlerp(seg+3, vj,vi, tmax);
3301  if (segmentRefs)
3302  segmentRefs[n] = 0;
3303  n++;
3304  }
3305  else
3306  {
3307  status |= DT_BUFFER_TOO_SMALL;
3308  }
3309  }
3310  }
3311  }
3312 
3313  *segmentCount = n;
3314 
3315  return status;
3316 }
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
static void insertInterval(dtSegInterval *ints, int &nints, const int maxInts, const short tmin, const short tmax, const dtPolyRef ref)
Definition: DetourNavMeshQuery.cpp:3145
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:117
short tmax
Definition: DetourNavMeshQuery.cpp:3142
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1131
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:160
unsigned int dtStatus
Definition: DetourStatus.h:22
unsigned short neis[DT_VERTS_PER_POLYGON]
Packed data representing neighbor polygons references and flags for each edge.
Definition: DetourNavMesh.h:163
Definition: DetourNavMesh.h:153
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1113
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:286
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:287
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:81
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
short tmin
Definition: DetourNavMeshQuery.cpp:3142
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:156
dtPolyRef ref
Definition: DetourNavMeshQuery.cpp:3141
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1269
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:169
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:285
Definition: DetourNavMesh.h:279
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
Definition: DetourNavMeshQuery.cpp:3139
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:84
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

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.

2148 {
2149  dtAssert(m_nav);
2150 
2151  const dtMeshTile* fromTile = 0;
2152  const dtPoly* fromPoly = 0;
2153  if (dtStatusFailed(m_nav->getTileAndPolyByRef(from, &fromTile, &fromPoly)))
2154  return DT_FAILURE | DT_INVALID_PARAM;
2155  fromType = fromPoly->getType();
2156 
2157  const dtMeshTile* toTile = 0;
2158  const dtPoly* toPoly = 0;
2159  if (dtStatusFailed(m_nav->getTileAndPolyByRef(to, &toTile, &toPoly)))
2160  return DT_FAILURE | DT_INVALID_PARAM;
2161  toType = toPoly->getType();
2162 
2163  return getPortalPoints(from, fromPoly, fromTile, to, toPoly, toTile, left, right);
2164 }
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:2146
#define dtAssert
Definition: DetourAssert.h:30
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:185
Definition: DetourNavMesh.h:153
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1113
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:506
Definition: DetourNavMesh.h:279
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:

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
2170 {
2171  // Find the link that points to the 'to' polygon.
2172  const dtLink* link = 0;
2173  for (unsigned int i = fromPoly->firstLink; i != DT_NULL_LINK; i = fromTile->links[i].next)
2174  {
2175  if (fromTile->links[i].ref == to)
2176  {
2177  link = &fromTile->links[i];
2178  break;
2179  }
2180  }
2181  if (!link)
2182  return DT_FAILURE | DT_INVALID_PARAM;
2183 
2184  // Handle off-mesh connections.
2185  if (fromPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
2186  {
2187  // Find link that points to first vertex.
2188  for (unsigned int i = fromPoly->firstLink; i != DT_NULL_LINK; i = fromTile->links[i].next)
2189  {
2190  if (fromTile->links[i].ref == to)
2191  {
2192  const int v = fromTile->links[i].edge;
2193  dtVcopy(left, &fromTile->verts[fromPoly->verts[v]*3]);
2194  dtVcopy(right, &fromTile->verts[fromPoly->verts[v]*3]);
2195  return DT_SUCCESS;
2196  }
2197  }
2198  return DT_FAILURE | DT_INVALID_PARAM;
2199  }
2200 
2201  if (toPoly->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
2202  {
2203  for (unsigned int i = toPoly->firstLink; i != DT_NULL_LINK; i = toTile->links[i].next)
2204  {
2205  if (toTile->links[i].ref == from)
2206  {
2207  const int v = toTile->links[i].edge;
2208  dtVcopy(left, &toTile->verts[toPoly->verts[v]*3]);
2209  dtVcopy(right, &toTile->verts[toPoly->verts[v]*3]);
2210  return DT_SUCCESS;
2211  }
2212  }
2213  return DT_FAILURE | DT_INVALID_PARAM;
2214  }
2215 
2216  // Find portal vertices.
2217  const int v0 = fromPoly->verts[link->edge];
2218  const int v1 = fromPoly->verts[(link->edge+1) % (int)fromPoly->vertCount];
2219  dtVcopy(left, &fromTile->verts[v0*3]);
2220  dtVcopy(right, &fromTile->verts[v1*3]);
2221 
2222  // If the link is at tile boundary, dtClamp the vertices to
2223  // the link width.
2224  if (link->side != 0xff)
2225  {
2226  // Unpack portal limits.
2227  if (link->bmin != 0 || link->bmax != 255)
2228  {
2229  const float s = 1.0f/255.0f;
2230  const float tmin = link->bmin*s;
2231  const float tmax = link->bmax*s;
2232  dtVlerp(left, &fromTile->verts[v0*3], &fromTile->verts[v1*3], tmin);
2233  dtVlerp(right, &fromTile->verts[v0*3], &fromTile->verts[v1*3], tmax);
2234  }
2235  }
2236 
2237  return DT_SUCCESS;
2238 }
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:117
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:160
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:185
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:286
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:287
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:147
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:156
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:169
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:84
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

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 <= 65536]
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.

168 {
169  m_nav = nav;
170 
171  if (!m_nodePool || m_nodePool->getMaxNodes() < maxNodes)
172  {
173  if (m_nodePool)
174  {
177  m_nodePool = 0;
178  }
179  m_nodePool = new (dtAlloc(sizeof(dtNodePool), DT_ALLOC_PERM)) dtNodePool(maxNodes, dtNextPow2(maxNodes/4));
180  if (!m_nodePool)
181  return DT_FAILURE | DT_OUT_OF_MEMORY;
182  }
183  else
184  {
185  m_nodePool->clear();
186  }
187 
188  if (!m_tinyNodePool)
189  {
190  m_tinyNodePool = new (dtAlloc(sizeof(dtNodePool), DT_ALLOC_PERM)) dtNodePool(64, 32);
191  if (!m_tinyNodePool)
192  return DT_FAILURE | DT_OUT_OF_MEMORY;
193  }
194  else
195  {
197  }
198 
199  // TODO: check the open list size too.
200  if (!m_openList || m_openList->getCapacity() < maxNodes)
201  {
202  if (m_openList)
203  {
206  m_openList = 0;
207  }
208  m_openList = new (dtAlloc(sizeof(dtNodeQueue), DT_ALLOC_PERM)) dtNodeQueue(maxNodes);
209  if (!m_openList)
210  return DT_FAILURE | DT_OUT_OF_MEMORY;
211  }
212  else
213  {
214  m_openList->clear();
215  }
216 
217  return DT_SUCCESS;
218 }
void clear()
Definition: DetourNode.h:114
void * dtAlloc(int size, dtAllocHint hint)
Definition: DetourAlloc.cpp:41
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:523
~dtNodeQueue()
Definition: DetourNode.cpp:152
Memory persist after a function call.
Definition: DetourAlloc.h:26
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
Definition: DetourNode.h:107
int getCapacity() const
Definition: DetourNode.h:158
~dtNodePool()
Definition: DetourNode.cpp:61
int getMaxNodes() const
Definition: DetourNode.h:90
unsigned int dtNextPow2(unsigned int v)
Definition: DetourCommon.h:417
Definition: DetourNode.h:50
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:521
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
void clear()
Definition: DetourNode.cpp:68
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:

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.

1150 {
1151  dtAssert(m_nav);
1154 
1155  // Init path state.
1156  memset(&m_query, 0, sizeof(dtQueryData));
1158  m_query.startRef = startRef;
1159  m_query.endRef = endRef;
1160  dtVcopy(m_query.startPos, startPos);
1161  dtVcopy(m_query.endPos, endPos);
1162  m_query.filter = filter;
1163  m_query.options = options;
1164  m_query.raycastLimitSqr = FLT_MAX;
1165 
1166  if (!startRef || !endRef)
1167  return DT_FAILURE | DT_INVALID_PARAM;
1168 
1169  // Validate input
1170  if (!m_nav->isValidPolyRef(startRef) || !m_nav->isValidPolyRef(endRef))
1171  return DT_FAILURE | DT_INVALID_PARAM;
1172 
1173  // trade quality with performance?
1174  if (options & DT_FINDPATH_ANY_ANGLE)
1175  {
1176  // limiting to several times the character radius yields nice results. It is not sensitive
1177  // so it is enough to compute it from the first tile.
1178  const dtMeshTile* tile = m_nav->getTileByRef(startRef);
1179  float agentRadius = tile->header->walkableRadius;
1181  }
1182 
1183  if (startRef == endRef)
1184  {
1186  return DT_SUCCESS;
1187  }
1188 
1189  m_nodePool->clear();
1190  m_openList->clear();
1191 
1192  dtNode* startNode = m_nodePool->getNode(startRef);
1193  dtVcopy(startNode->pos, startPos);
1194  startNode->pidx = 0;
1195  startNode->cost = 0;
1196  startNode->total = dtVdist(startPos, endPos) * H_SCALE;
1197  startNode->id = startRef;
1198  startNode->flags = DT_NODE_OPEN;
1199  m_openList->push(startNode);
1200 
1202  m_query.lastBestNode = startNode;
1203  m_query.lastBestNodeCost = startNode->total;
1204 
1205  return m_query.status;
1206 }
void clear()
Definition: DetourNode.h:114
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:284
static const float DT_RAY_CAST_LIMIT_PROPORTIONS
Definition: DetourNavMesh.h:139
class dtNodeQueue * m_openList
Pointer to open list queue.
Definition: DetourNavMeshQuery.h:523
Definition: DetourNode.h:34
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:217
float walkableRadius
The radius of the agents using the tile.
Definition: DetourNavMesh.h:268
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1139
float pos[3]
Position of the node.
Definition: DetourNode.h:36
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
Definition: DetourNode.h:26
const dtMeshTile * getTileByRef(dtTileRef ref) const
Definition: DetourNavMesh.cpp:1078
struct dtNode * lastBestNode
Definition: DetourNavMeshQuery.h:511
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
dtStatus status
Definition: DetourNavMeshQuery.h:510
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
float lastBestNodeCost
Definition: DetourNavMeshQuery.h:512
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtPolyRef startRef
Definition: DetourNavMeshQuery.h:513
dtPolyRef endRef
Definition: DetourNavMeshQuery.h:513
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:106
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
T dtSqr(T a)
Definition: DetourCommon.h:67
use raycasts during pathfind to "shortcut" (raycast still consider costs)
Definition: DetourNavMesh.h:127
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
float cost
Cost from previous node to current node.
Definition: DetourNode.h:37
unsigned int options
Definition: DetourNavMeshQuery.h:516
dtQueryData m_query
Sliced query state.
Definition: DetourNavMeshQuery.h:519
static const float H_SCALE
Definition: DetourNavMeshQuery.cpp:104
const dtQueryFilter * filter
Definition: DetourNavMeshQuery.h:515
Definition: DetourNavMesh.h:279
float total
Cost up to the node.
Definition: DetourNode.h:38
void clear()
Definition: DetourNode.cpp:68
float startPos[3]
Definition: DetourNavMeshQuery.h:514
static const unsigned int DT_IN_PROGRESS
Definition: DetourStatus.h:27
float endPos[3]
Definition: DetourNavMeshQuery.h:514
float raycastLimitSqr
Definition: DetourNavMeshQuery.h:517
void push(dtNode *node)
Definition: DetourNode.h:132
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25

+ Here is the call graph for this function:

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)

3530 {
3531  if (!m_nodePool) return false;
3532 
3534  int n= m_nodePool->findNodes(ref, nodes, DT_MAX_STATES_PER_NODE);
3535 
3536  for (int i=0; i<n; i++)
3537  {
3538  if (nodes[i]->flags & DT_NODE_CLOSED)
3539  return true;
3540  }
3541 
3542  return false;
3543 }
Definition: DetourNode.h:34
class dtNodePool * m_nodePool
Pointer to node pool.
Definition: DetourNavMeshQuery.h:522
unsigned int findNodes(dtPolyRef id, dtNode **nodes, const int maxNodes)
Definition: DetourNode.cpp:74
Definition: DetourNode.h:27
static const int DT_MAX_STATES_PER_NODE
Definition: DetourNode.h:46
uint8 flags
Definition: DisableMgr.cpp:44

+ Here is the call graph for this function:

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.
3511 {
3512  const dtMeshTile* tile = 0;
3513  const dtPoly* poly = 0;
3514  dtStatus status = m_nav->getTileAndPolyByRef(ref, &tile, &poly);
3515  // If cannot get polygon, assume it does not exists and boundary is invalid.
3516  if (dtStatusFailed(status))
3517  return false;
3518  // If cannot pass filter, assume flags has changed and boundary is invalid.
3519  if (!filter->passFilter(ref, tile, poly))
3520  return false;
3521  return true;
3522 }
unsigned int dtStatus
Definition: DetourStatus.h:22
Definition: DetourNavMesh.h:153
dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1113
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
Definition: DetourNavMesh.h:279
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87

+ Here is the call graph for this function:

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.

1951 {
1952  dtAssert(m_nav);
1954 
1955  *visitedCount = 0;
1956 
1957  // Validate input
1958  if (!startRef)
1959  return DT_FAILURE | DT_INVALID_PARAM;
1960  if (!m_nav->isValidPolyRef(startRef))
1961  return DT_FAILURE | DT_INVALID_PARAM;
1962 
1963  dtStatus status = DT_SUCCESS;
1964 
1965  static const int MAX_STACK = 48;
1966  dtNode* stack[MAX_STACK];
1967  int nstack = 0;
1968 
1969  m_tinyNodePool->clear();
1970 
1971  dtNode* startNode = m_tinyNodePool->getNode(startRef);
1972  startNode->pidx = 0;
1973  startNode->cost = 0;
1974  startNode->total = 0;
1975  startNode->id = startRef;
1976  startNode->flags = DT_NODE_CLOSED;
1977  stack[nstack++] = startNode;
1978 
1979  float bestPos[3];
1980  float bestDist = FLT_MAX;
1981  dtNode* bestNode = 0;
1982  dtVcopy(bestPos, startPos);
1983 
1984  // Search constraints
1985  float searchPos[3], searchRadSqr;
1986  dtVlerp(searchPos, startPos, endPos, 0.5f);
1987  searchRadSqr = dtSqr(dtVdist(startPos, endPos)/2.0f + 0.001f);
1988 
1989  float verts[DT_VERTS_PER_POLYGON*3];
1990 
1991  while (nstack)
1992  {
1993  // Pop front.
1994  dtNode* curNode = stack[0];
1995  for (int i = 0; i < nstack-1; ++i)
1996  stack[i] = stack[i+1];
1997  nstack--;
1998 
1999  // Get poly and tile.
2000  // The API input has been cheked already, skip checking internal data.
2001  const dtPolyRef curRef = curNode->id;
2002  const dtMeshTile* curTile = 0;
2003  const dtPoly* curPoly = 0;
2004  m_nav->getTileAndPolyByRefUnsafe(curRef, &curTile, &curPoly);
2005 
2006  // Collect vertices.
2007  const int nverts = curPoly->vertCount;
2008  for (int i = 0; i < nverts; ++i)
2009  dtVcopy(&verts[i*3], &curTile->verts[curPoly->verts[i]*3]);
2010 
2011  // If target is inside the poly, stop search.
2012  if (dtPointInPolygon(endPos, verts, nverts))
2013  {
2014  bestNode = curNode;
2015  dtVcopy(bestPos, endPos);
2016  break;
2017  }
2018 
2019  // Find wall edges and find nearest point inside the walls.
2020  for (int i = 0, j = (int)curPoly->vertCount-1; i < (int)curPoly->vertCount; j = i++)
2021  {
2022  // Find links to neighbours.
2023  static const int MAX_NEIS = 8;
2024  int nneis = 0;
2025  dtPolyRef neis[MAX_NEIS];
2026 
2027  if (curPoly->neis[j] & DT_EXT_LINK)
2028  {
2029  // Tile border.
2030  for (unsigned int k = curPoly->firstLink; k != DT_NULL_LINK; k = curTile->links[k].next)
2031  {
2032  const dtLink* link = &curTile->links[k];
2033  if (link->edge == j)
2034  {
2035  if (link->ref != 0)
2036  {
2037  const dtMeshTile* neiTile = 0;
2038  const dtPoly* neiPoly = 0;
2039  m_nav->getTileAndPolyByRefUnsafe(link->ref, &neiTile, &neiPoly);
2040  if (filter->passFilter(link->ref, neiTile, neiPoly))
2041  {
2042  if (nneis < MAX_NEIS)
2043  neis[nneis++] = link->ref;
2044  }
2045  }
2046  }
2047  }
2048  }
2049  else if (curPoly->neis[j])
2050  {
2051  const unsigned int idx = (unsigned int)(curPoly->neis[j]-1);
2052  const dtPolyRef ref = m_nav->getPolyRefBase(curTile) | idx;
2053  if (filter->passFilter(ref, curTile, &curTile->polys[idx]))
2054  {
2055  // Internal edge, encode id.
2056  neis[nneis++] = ref;
2057  }
2058  }
2059 
2060  if (!nneis)
2061  {
2062  // Wall edge, calc distance.
2063  const float* vj = &verts[j*3];
2064  const float* vi = &verts[i*3];
2065  float tseg;
2066  const float distSqr = dtDistancePtSegSqr2D(endPos, vj, vi, tseg);
2067  if (distSqr < bestDist)
2068  {
2069  // Update nearest distance.
2070  dtVlerp(bestPos, vj,vi, tseg);
2071  bestDist = distSqr;
2072  bestNode = curNode;
2073  }
2074  }
2075  else
2076  {
2077  for (int k = 0; k < nneis; ++k)
2078  {
2079  // Skip if no node can be allocated.
2080  dtNode* neighbourNode = m_tinyNodePool->getNode(neis[k]);
2081  if (!neighbourNode)
2082  continue;
2083  // Skip if already visited.
2084  if (neighbourNode->flags & DT_NODE_CLOSED)
2085  continue;
2086 
2087  // Skip the link if it is too far from search constraint.
2088  // TODO: Maybe should use getPortalPoints(), but this one is way faster.
2089  const float* vj = &verts[j*3];
2090  const float* vi = &verts[i*3];
2091  float tseg;
2092  float distSqr = dtDistancePtSegSqr2D(searchPos, vj, vi, tseg);
2093  if (distSqr > searchRadSqr)
2094  continue;
2095 
2096  // Mark as the node as visited and push to queue.
2097  if (nstack < MAX_STACK)
2098  {
2099  neighbourNode->pidx = m_tinyNodePool->getNodeIdx(curNode);
2100  neighbourNode->flags |= DT_NODE_CLOSED;
2101  stack[nstack++] = neighbourNode;
2102  }
2103  }
2104  }
2105  }
2106  }
2107 
2108  int n = 0;
2109  if (bestNode)
2110  {
2111  // Reverse the path.
2112  dtNode* prev = 0;
2113  dtNode* node = bestNode;
2114  do
2115  {
2117  node->pidx = m_tinyNodePool->getNodeIdx(prev);
2118  prev = node;
2119  node = next;
2120  }
2121  while (node);
2122 
2123  // Store result
2124  node = prev;
2125  do
2126  {
2127  visited[n++] = node->id;
2128  if (n >= maxVisitedSize)
2129  {
2130  status |= DT_BUFFER_TOO_SMALL;
2131  break;
2132  }
2133  node = m_tinyNodePool->getNodeAtIdx(node->pidx);
2134  }
2135  while (node);
2136  }
2137 
2138  dtVcopy(resultPos, bestPos);
2139 
2140  *visitedCount = n;
2141 
2142  return status;
2143 }
uint64_d dtPolyRef
Definition: DetourNavMesh.h:49
Definition: DetourNode.h:34
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:117
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:217
int next(int i, int n)
Definition: RecastContour.cpp:469
bool isValidPolyRef(dtPolyRef ref) const
Definition: DetourNavMesh.cpp:1139
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1131
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
#define dtAssert
Definition: DetourAssert.h:30
bool dtPointInPolygon(const float *pt, const float *verts, const int nverts)
Definition: DetourCommon.cpp:239
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
unsigned int getNodeIdx(const dtNode *node) const
Definition: DetourNode.h:64
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:160
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:163
unsigned int flags
Node flags. A combination of dtNodeFlags.
Definition: DetourNode.h:41
Definition: DetourNavMesh.h:153
dtPolyRef id
Polygon ref the node corresponds to.
Definition: DetourNode.h:42
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:286
unsigned int pidx
Index to parent node.
Definition: DetourNode.h:39
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:287
dtNode * getNodeAtIdx(unsigned int idx)
Definition: DetourNode.h:70
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:81
Definition: DetourNode.h:27
dtNode * getNode(dtPolyRef id, unsigned char state=0)
Definition: DetourNode.cpp:106
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:190
T dtSqr(T a)
Definition: DetourCommon.h:67
class dtNodePool * m_tinyNodePool
Pointer to small node pool.
Definition: DetourNavMeshQuery.h:521
const dtNavMesh * m_nav
Pointer to navmesh data.
Definition: DetourNavMeshQuery.h:506
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:156
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1269
float cost
Cost from previous node to current node.
Definition: DetourNode.h:37
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:169
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:285
Definition: DetourNavMesh.h:279
float total
Cost up to the node.
Definition: DetourNode.h:38
void clear()
Definition: DetourNode.cpp:68
bool passFilter(const dtPolyRef ref, const dtMeshTile *tile, const dtPoly *poly) const
Definition: DetourNavMeshQuery.cpp:87
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:57
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:84
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: