#include <DetourNavMeshQuery.h>

Public Member Functions
NAVMESH_API	dtNavMeshQuery ()

NAVMESH_API	~dtNavMeshQuery ()

NAVMESH_API dtStatus	init (const dtNavMesh nav, const int maxNodes, dtQuerySpecialLinkFilter linkFilter=0)

NAVMESH_API void	updateLinkFilter (dtQuerySpecialLinkFilter *linkFilter)
	UE: updates special link filter for this query.

NAVMESH_API dtStatus	getPortalPoints (dtPolyRef from, dtPolyRef to, dtReal left, dtReal right, unsigned char &fromType, unsigned char &toType) const
	Returns portal points between two polygons.

NAVMESH_API dtStatus	getPortalPoints (dtPolyRef from, const dtPoly fromPoly, const dtMeshTile fromTile, dtPolyRef to, const dtPoly toPoly, const dtMeshTile toTile, dtReal left, dtReal right) const

NAVMESH_API dtStatus	getEdgeMidPoint (dtPolyRef from, dtPolyRef to, dtReal *mid) const
	Returns edge mid point between two polygons.

NAVMESH_API dtStatus	getEdgeMidPoint (dtPolyRef from, const dtPoly fromPoly, const dtMeshTile fromTile, dtPolyRef to, const dtPoly toPoly, const dtMeshTile toTile, dtReal *mid) const

NAVMESH_API dtStatus	appendVertex (const dtReal *pos, const unsigned char flags, const dtPolyRef ref, dtQueryResult &result, const bool bOverrideIdenticalPosition=true) const

NAVMESH_API dtStatus	appendPortals (const int startIdx, const int endIdx, const dtReal endPos, const dtPolyRef path, dtQueryResult &result, const int options) const

bool	passLinkFilterByRef (const dtMeshTile *tile, const dtPolyRef ref) const

bool	passLinkFilter (const dtMeshTile *tile, const int polyIdx) const

void	setRequireNavigableEndLocation (const bool value)

bool	isRequiringNavigableEndLocation () const

Standard Pathfinding Functions
NAVMESH_API dtStatus	findPath (dtPolyRef startRef, dtPolyRef endRef, const dtReal startPos, const dtReal endPos, const dtReal costLimit, const dtQueryFilter filter, dtQueryResult &result, dtReal totalCost) const

NAVMESH_API dtStatus	findStraightPath (const dtReal startPos, const dtReal endPos, const dtPolyRef *path, const int pathSize, dtQueryResult &result, const int options=0) const

Sliced Pathfinding Functions
Common use case: Call initSlicedFindPath() to initialize the sliced path query. Call updateSlicedFindPath() until it returns complete. Call finalizeSlicedFindPath() to get the path.
NAVMESH_API dtStatus	initSlicedFindPath (dtPolyRef startRef, dtPolyRef endRef, const dtReal startPos, const dtReal endPos, const dtReal costLimit, const bool requireNavigableEndLocation, const dtQueryFilter *filter)

NAVMESH_API dtStatus	updateSlicedFindPath (const int maxIter, int *doneIters)

NAVMESH_API dtStatus	finalizeSlicedFindPath (dtPolyRef path, int pathCount, const int maxPath)

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

Dijkstra Search Functions

NAVMESH_API dtStatus	findPolysAroundCircle (dtPolyRef startRef, const dtReal centerPos, const dtReal radius, const dtQueryFilter filter, dtPolyRef resultRef, dtPolyRef resultParent, dtReal resultCost, int resultCount, const int maxResult) const

NAVMESH_API dtStatus	findPolysAroundShape (dtPolyRef startRef, const dtReal verts, const int nverts, const dtQueryFilter filter, dtPolyRef resultRef, dtPolyRef resultParent, dtReal resultCost, int resultCount, const int maxResult) const

NAVMESH_API dtStatus	findPolysInPathDistance (dtPolyRef startRef, const dtReal centerPos, const dtReal pathDistance, const dtQueryFilter filter, dtPolyRef resultRef, int resultCount, const int maxResult) const

Local Query Functions
NAVMESH_API dtStatus	findNearestPoly (const dtReal center, const dtReal extents, const dtQueryFilter filter, dtPolyRef nearestRef, dtReal nearestPt, const dtReal referencePt=0) const

NAVMESH_API dtStatus	findNearestPoly2D (const dtReal center, const dtReal extents, const dtQueryFilter filter, dtPolyRef outProjectedRef, dtReal outProjectedPt, const dtReal referencePt=0, dtReal tolerance=0) const

NAVMESH_API dtStatus	findNearestContainingPoly (const dtReal center, const dtReal extents, const dtQueryFilter filter, dtPolyRef nearestRef, dtReal *nearestPt) const

NAVMESH_API dtStatus	queryPolygons (const dtReal center, const dtReal extents, const dtQueryFilter filter, dtPolyRef polys, int *polyCount, const int maxPolys) const

NAVMESH_API dtStatus	findLocalNeighbourhood (dtPolyRef startRef, const dtReal centerPos, const dtReal radius, const dtQueryFilter filter, dtPolyRef resultRef, dtPolyRef resultParent, int *resultCount, const int maxResult) const

NAVMESH_API dtStatus	findWallsInNeighbourhood (dtPolyRef startRef, const dtReal centerPos, const dtReal radius, const dtQueryFilter filter, dtPolyRef neiRefs, int neiCount, const int maxNei, dtReal resultWalls, dtPolyRef resultRefs, int *resultCount, const int maxResult) const
	[UE] Finds the wall segments in local neighbourhood

NAVMESH_API dtStatus	findWallsOverlappingShape (dtPolyRef startRef, const dtReal verts, const int nverts, const dtQueryFilter filter, dtPolyRef neiRefs, int neiCount, const int maxNei, dtReal resultWalls, dtPolyRef resultRefs, int *resultCount, const int maxResult) const
	[UE] Finds the wall segments that overlap the polygon shape.

NAVMESH_API dtStatus	findWallsAroundPath (const dtPolyRef path, const int pathCount, const dtReal searchAreaPoly, const int searchAreaPolyCount, const dtReal maxAreaEnterCost, const dtQueryFilter filter, dtPolyRef neiRefs, int neiCount, const int maxNei, dtReal resultWalls, dtPolyRef resultRefs, int resultCount, const int maxResult) const
	[UE] Finds the wall segments that overlap the polygon shape.

NAVMESH_API dtStatus	moveAlongSurface (dtPolyRef startRef, const dtReal startPos, const dtReal endPos, const dtQueryFilter filter, dtReal resultPos, dtPolyRef visited, int visitedCount, const int maxVisitedSize) const

NAVMESH_API dtStatus	raycast (dtPolyRef startRef, const dtReal startPos, const dtReal endPos, const dtQueryFilter filter, dtReal t, dtReal hitNormal, dtPolyRef path, int *pathCount, const int maxPath) const

NAVMESH_API dtStatus	findDistanceToWall (dtPolyRef startRef, const dtReal centerPos, const dtReal maxRadius, const dtQueryFilter filter, dtReal hitDist, dtReal hitPos, dtReal *hitNormal) const

NAVMESH_API dtStatus	getPolyWallSegments (dtPolyRef ref, const dtQueryFilter filter, dtReal segmentVerts, dtPolyRef segmentRefs, int segmentCount, const int maxSegments) const

NAVMESH_API dtStatus	findRandomPoint (const dtQueryFilter filter, float(frand)(), dtPolyRef randomRef, dtReal randomPt) const

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

NAVMESH_API dtStatus	findRandomPointInPoly (dtPolyRef ref, float(frand)(), dtReal randomPt) const

NAVMESH_API dtStatus	closestPointOnPoly (dtPolyRef ref, const dtReal pos, dtReal closest) const

NAVMESH_API dtStatus	closestPointOnPolyBoundary (dtPolyRef ref, const dtReal pos, dtReal closest) const

NAVMESH_API dtStatus	projectedPointOnPoly (dtPolyRef ref, const dtReal pos, dtReal projected) const

NAVMESH_API dtStatus	isPointInsidePoly (dtPolyRef ref, const dtReal *pos, bool &result) const

NAVMESH_API dtStatus	getPolyHeight (dtPolyRef ref, const dtReal pos, dtReal height) const

Miscellaneous Functions
NAVMESH_API bool	isValidPolyRef (dtPolyRef ref, const dtQueryFilter *filter) const

NAVMESH_API bool	isInClosedList (dtPolyRef ref) const

NAVMESH_API bool	wasClusterLinkSearched (dtPolyRef cFrom, dtPolyRef cTo) const

class dtNodePool *	getNodePool () const

const dtNavMesh *	getAttachedNavMesh () const

void	getCurrentBestResult (struct dtNode *&bestNode, dtReal &bestCost) const
	Gets best node ref and cost from sliced pathfinding data.

int	getQueryNodes () const

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::dtNavMeshQuery ( )

◆ ~dtNavMeshQuery()

dtNavMeshQuery::~dtNavMeshQuery ( )

Member Function Documentation

◆ appendPortals()

dtStatus dtNavMeshQuery::appendPortals	(	const int	startIdx,
		const int	endIdx,
		const dtReal *	endPos,
		const dtPolyRef *	path,
		dtQueryResult &	result,
		const int	options
	)		const

◆ appendVertex()

dtStatus dtNavMeshQuery::appendVertex	(	const dtReal *	pos,
		const unsigned char	flags,
		const dtPolyRef	ref,
		dtQueryResult &	result,
		const bool	bOverrideIdenticalPosition = `true`
	)		const

◆ closestPointOnPoly()

dtStatus dtNavMeshQuery::closestPointOnPoly	(	dtPolyRef	ref,
		const dtReal *	pos,
		dtReal *	closest
	)		const

Finds the closest point on the specified polygon.

Parameters

[in]	ref	The reference id of the polygon.
[in]	pos	The position to check. [(x, y, z)]
[out]	closest	The closest point on the polygon. [(x, y, z)]

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.

◆ closestPointOnPolyBoundary()

dtStatus dtNavMeshQuery::closestPointOnPolyBoundary	(	dtPolyRef	ref,
		const dtReal *	pos,
		dtReal *	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]	ref	The reference id to the polygon.
[in]	pos	The position to check. [(x, y, z)]
[out]	closest	The 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.

◆ finalizeSlicedFindPath()

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

Finalizes and returns the results of a sliced path query.

Parameters

[out]	path	An ordered list of polygon references representing the path. (Start to end.) [(polyRef) * `pathCount`]
[out]	pathCount	The number of polygons returned in the `path` array.
[in]	maxPath	The max number of polygons the path array can hold. [Limit: >= 1]

Returns: The status flags for the query.

◆ finalizeSlicedFindPathPartial()

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

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

Parameters

[out]	existing	An array of polygon references for the existing path.
[out]	existingSize	The number of polygon in the `existing` array.
[out]	path	An ordered list of polygon references representing the path. (Start to end.) [(polyRef) * `pathCount`]
[out]	pathCount	The number of polygons returned in the `path` array.
[in]	maxPath	The max number of polygons the `path` array can hold. [Limit: >= 1]

Returns: The status flags for the query.

◆ findDistanceToWall()

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

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

Parameters

[in]	startRef	The reference id of the polygon containing `centerPos`.
[in]	centerPos	The center of the search circle. [(x, y, z)]
[in]	maxRadius	The radius of the search circle.
[in]	filter	The polygon filter to apply to the query.
[out]	hitDist	The distance to the nearest wall from `centerPos`.
[out]	hitPos	The nearest position on the wall that was hit. [(x, y, z)]
[out]	hitNormal	The 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.

◆ findLocalNeighbourhood()

dtStatus dtNavMeshQuery::findLocalNeighbourhood	(	dtPolyRef	startRef,
		const dtReal *	centerPos,
		const dtReal	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]	startRef	The reference id of the polygon where the search starts.
[in]	centerPos	The center of the query circle. [(x, y, z)]
[in]	radius	The radius of the query circle.
[in]	filter	The polygon filter to apply to the query.
[out]	resultRef	The reference ids of the polygons touched by the circle.
[out]	resultParent	The reference ids of the parent polygons for each result. Zero if a result polygon has no parent. [opt]
[out]	resultCount	The number of polygons found.
[in]	maxResult	The 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 method 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.

◆ findNearestContainingPoly()

dtStatus dtNavMeshQuery::findNearestContainingPoly	(	const dtReal *	center,
		const dtReal *	extents,
		const dtQueryFilter *	filter,
		dtPolyRef *	nearestRef,
		dtReal *	nearestPt
	)		const

Finds the nearest polygon in height containing the specified center point.

Parameters

[in]	center	The center of the search box. [(x, y, z)]
[in]	extents	The search distance along each axis. [(x, y, z)]
[in]	filter	The polygon filter to apply to the query.
[out]	nearestRef	The reference id of the nearest polygon.
[out]	nearestPt	The 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 128 polygons it may return an invalid result.

◆ findNearestPoly()

dtStatus dtNavMeshQuery::findNearestPoly	(	const dtReal *	center,
		const dtReal *	extents,
		const dtQueryFilter *	filter,
		dtPolyRef *	nearestRef,
		dtReal *	nearestPt,
		const dtReal *	referencePt = `0`
	)		const

Finds the polygon nearest to the specified center point.

Parameters

[in]	center	The center of the search box. [(x, y, z)]
[in]	extents	The search distance along each axis. [(x, y, z)]
[in]	filter	The polygon filter to apply to the query.
[out]	nearestRef	The reference id of the nearest polygon.
[out]	nearestPt	The nearest point on the polygon. [opt] [(x, y, z)]
[in]	referencePt	If supplied replaces
	center	in terms of distance measurements. Note that extents are not precise when using a referencePt. [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 128 polygons it may return an invalid result.

◆ findNearestPoly2D()

dtStatus dtNavMeshQuery::findNearestPoly2D	(	const dtReal *	center,
		const dtReal *	extents,
		const dtQueryFilter *	filter,
		dtPolyRef *	outProjectedRef,
		dtReal *	outProjectedPt,
		const dtReal *	referencePt = `0`,
		dtReal	tolerance = `0`
	)		const

Finds the polygon 2D-nearest to the specified center point.

Parameters

[in]	center	The center of the search box. [(x, y, z)]
[in]	extents	The search distance along each axis. [(x, y, z)]
[in]	filter	The polygon filter to apply to the query.
[out]	nearestRef	The reference id of the nearest polygon.
[out]	nearestPt	The nearest point on the polygon. [opt] [(x, y, z)]
[in]	referencePt	If supplied replaces
	center	in terms of distance measurements. Note that extents are not precise when using a referencePt. [opt] [(x, y, z)]
[in]	tolerance	Radius around best 2D point for picking vertical match

Returns: The status flags for the query.

◆ findPath()

dtStatus dtNavMeshQuery::findPath	(	dtPolyRef	startRef,
		dtPolyRef	endRef,
		const dtReal *	startPos,
		const dtReal *	endPos,
		const dtReal	costLimit,
		const dtQueryFilter *	filter,
		dtQueryResult &	result,
		dtReal *	totalCost
	)		const

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

Parameters

[in]	startRef	The reference id of the start polygon.
[in]	endRef	The reference id of the end polygon.
[in]	startPos	A position within the start polygon. [(x, y, z)]
[in]	endPos	A position within the end polygon. [(x, y, z)]
[in]	costLimit	Cost limit of nodes allowed to be added to the open list //@UE
[in]	filter	The polygon filter to apply to the query.
[out]	result	Results for path corridor, fills in refs and costs for each poly from start to end
[out]	totalCost	If provided will get filled will total cost of path

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

◆ findPolysAroundCircle()

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

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

Parameters

[in]	startRef	The reference id of the polygon where the search starts.
[in]	centerPos	The center of the search circle. [(x, y, z)]
[in]	radius	The radius of the search circle.
[in]	filter	The polygon filter to apply to the query.
[out]	resultRef	The reference ids of the polygons touched by the circle. [opt]
[out]	resultParent	The reference ids of the parent polygons for each result. Zero if a result polygon has no parent. [opt]
[out]	resultCost	The search cost from `centerPos` to the polygon. [opt]
[out]	resultCount	The number of polygons found.
[in]	maxResult	The 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.

◆ findPolysAroundShape()

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

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

Parameters

[in]	startRef	The reference id of the polygon where the search starts.
[in]	verts	The vertices describing the convex polygon. (CCW) [(x, y, z) * `nverts`]
[in]	nverts	The number of vertices in the polygon.
[in]	filter	The polygon filter to apply to the query.
[out]	resultRef	The reference ids of the polygons touched by the search polygon. [opt]
[out]	resultParent	The reference ids of the parent polygons for each result. Zero if a result polygon has no parent. [opt]
[out]	resultCost	The search cost from the centroid point to the polygon. [opt]
[out]	resultCount	The number of polygons found.
[in]	maxResult	The 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.

◆ findPolysInPathDistance()

dtStatus dtNavMeshQuery::findPolysInPathDistance	(	dtPolyRef	startRef,
		const dtReal *	centerPos,
		const dtReal	pathDistance,
		const dtQueryFilter *	filter,
		dtPolyRef *	resultRef,
		int *	resultCount,
		const int	maxResult
	)		const

Finds the polygons along the navigation graph that are no more than given path length away from centerPos.

Parameters

[in]	startRef	The reference id of the polygon where the search starts.
[in]	centerPos	The center of the search circle. [(x, y, z)]
[in]	pathDistance	The path distance limit of the search
[in]	filter	The polygon filter to apply to the query.
[out]	resultRef	The reference ids of the polygons touched by the circle. [opt]
[out]	resultCount	The number of polygons found. [opt]
[in]	maxResult	The maximum number of polygons the result arrays can hold.

Returns: The status flags for the querydtReal

◆ findRandomPoint()

dtStatus dtNavMeshQuery::findRandomPoint	(	const dtQueryFilter *	filter,
		float(*)()	frand,
		dtPolyRef *	randomRef,
		dtReal *	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]	filter	The polygon filter to apply to the query.
[in]	frand	Function returning a random number [0..1).
[out]	randomRef	The reference id of the random location.
[out]	randomPt	The random location.

Returns: The status flags for the query.

◆ findRandomPointAroundCircle()

dtStatus dtNavMeshQuery::findRandomPointAroundCircle	(	dtPolyRef	startRef,
		const dtReal *	centerPos,
		const dtReal	maxRadius,
		const dtQueryFilter *	filter,
		float(*)()	frand,
		dtPolyRef *	randomRef,
		dtReal *	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]	startRef	The reference id of the polygon where the search starts.
[in]	centerPos	The center of the search circle. [(x, y, z)]
[in]	filter	The polygon filter to apply to the query.
[in]	frand	Function returning a random number [0..1).
[out]	randomRef	The reference id of the random location.
[out]	randomPt	The random location. [(x, y, z)]

Returns: The status flags for the query.

◆ findRandomPointInPoly()

dtStatus dtNavMeshQuery::findRandomPointInPoly	(	dtPolyRef	ref,
		float(*)()	frand,
		dtReal *	randomPt
	)		const

Returns random location inside the specified polygon.

Parameters

[in]	ref	The reference id of the polygon.
[in]	frand	Function returning a random number [0..1).
[out]	randomPt	The random location. [(x, y, z)]

Returns: The status flags for the query.

◆ findStraightPath()

dtStatus dtNavMeshQuery::findStraightPath	(	const dtReal *	startPos,
		const dtReal *	endPos,
		const dtPolyRef *	path,
		const int	pathSize,
		dtQueryResult &	result,
		const int	options = `0`
	)		const

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

Parameters

[in]	startPos	Path start position. [(x, y, z)]
[in]	endPos	Path end position. [(x, y, z)]
[in]	path	An array of polygon references that represent the path corridor.
[in]	pathSize	The number of polygons in the `path` array.
[out]	result	Fills in positions, refs and flags
[in]	options	Query 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.

◆ findWallsAroundPath()

dtStatus dtNavMeshQuery::findWallsAroundPath	(	const dtPolyRef *	path,
		const int	pathCount,
		const dtReal *	searchAreaPoly,
		const int	searchAreaPolyCount,
		const dtReal	maxAreaEnterCost,
		const dtQueryFilter *	filter,
		dtPolyRef *	neiRefs,
		int *	neiCount,
		const int	maxNei,
		dtReal *	resultWalls,
		dtPolyRef *	resultRefs,
		int *	resultCount,
		const int	maxResult
	)		const

[UE] Finds the wall segments that overlap the polygon shape.

◆ findWallsInNeighbourhood()

dtStatus dtNavMeshQuery::findWallsInNeighbourhood	(	dtPolyRef	startRef,
		const dtReal *	centerPos,
		const dtReal	radius,
		const dtQueryFilter *	filter,
		dtPolyRef *	neiRefs,
		int *	neiCount,
		const int	maxNei,
		dtReal *	resultWalls,
		dtPolyRef *	resultRefs,
		int *	resultCount,
		const int	maxResult
	)		const

[UE] Finds the wall segments in local neighbourhood

◆ findWallsOverlappingShape()

dtStatus dtNavMeshQuery::findWallsOverlappingShape	(	dtPolyRef	startRef,
		const dtReal *	verts,
		const int	nverts,
		const dtQueryFilter *	filter,
		dtPolyRef *	neiRefs,
		int *	neiCount,
		const int	maxNei,
		dtReal *	resultWalls,
		dtPolyRef *	resultRefs,
		int *	resultCount,
		const int	maxResult
	)		const

[UE] Finds the wall segments that overlap the polygon shape.

◆ getAttachedNavMesh()

const dtNavMesh * dtNavMeshQuery::getAttachedNavMesh ( ) const

inline

Gets the navigation mesh the query object is using.

Returns: The navigation mesh the query object is using.

◆ getCurrentBestResult()

void dtNavMeshQuery::getCurrentBestResult	(	struct dtNode *&	bestNode,
		dtReal &	bestCost
	)		const

inline

Gets best node ref and cost from sliced pathfinding data.

◆ getEdgeMidPoint() [1/2]

dtStatus dtNavMeshQuery::getEdgeMidPoint	(	dtPolyRef	from,
		const dtPoly *	fromPoly,
		const dtMeshTile *	fromTile,
		dtPolyRef	to,
		const dtPoly *	toPoly,
		const dtMeshTile *	toTile,
		dtReal *	mid
	)		const

◆ getEdgeMidPoint() [2/2]

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

Returns edge mid point between two polygons.

◆ getNodePool()

class dtNodePool * dtNavMeshQuery::getNodePool ( ) const

inline

Gets the node pool.

Returns: The node pool.

◆ getPolyHeight()

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

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

Parameters

[in]	ref	The reference id of the polygon.
[in]	pos	A position within the xz-bounds of the polygon. [(x, y, z)]
[out]	height	The 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.

◆ getPolyWallSegments()

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

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

Parameters

[in]	ref	The reference id of the polygon.
[in]	filter	The polygon filter to apply to the query.
[out]	segmentVerts	The segments. [(ax, ay, az, bx, by, bz) * segmentCount]
[out]	segmentRefs	The reference ids of each segment's neighbor polygon. Or zero if the segment is a wall. [opt] [(parentRef) * `segmentCount`]
[out]	segmentCount	The number of segments returned.
[in]	maxSegments	The 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.

◆ getPortalPoints() [1/2]

dtStatus dtNavMeshQuery::getPortalPoints	(	dtPolyRef	from,
		const dtPoly *	fromPoly,
		const dtMeshTile *	fromTile,
		dtPolyRef	to,
		const dtPoly *	toPoly,
		const dtMeshTile *	toTile,
		dtReal *	left,
		dtReal *	right
	)		const

◆ getPortalPoints() [2/2]

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

Returns portal points between two polygons.

◆ getQueryNodes()

int dtNavMeshQuery::getQueryNodes ( ) const

inline

◆ init()

dtStatus dtNavMeshQuery::init	(	const dtNavMesh *	nav,
		const int	maxNodes,
		dtQuerySpecialLinkFilter *	linkFilter = `0`
	)

Initializes the query object.

Parameters

[in]	nav	Pointer to the dtNavMesh object to use for all queries.
[in]	maxNodes	Maximum number of search nodes. [Limits: 0 < value <= 65536]
[in]	linkFilter	Special link filter used for every query

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.

◆ initSlicedFindPath()

dtStatus dtNavMeshQuery::initSlicedFindPath	(	dtPolyRef	startRef,
		dtPolyRef	endRef,
		const dtReal *	startPos,
		const dtReal *	endPos,
		const dtReal	costLimit,
		const bool	requireNavigableEndLocation,
		const dtQueryFilter *	filter
	)

Initializes a sliced path query.

Parameters

[in]	startRef	The refrence id of the start polygon.
[in]	endRef	The reference id of the end polygon.
[in]	startPos	A position within the start polygon. [(x, y, z)]
[in]	endPos	A position within the end polygon. [(x, y, z)]
[in]	costLimit	Cost limit of nodes allowed to be added to the open list //@UE
[in]	requireNavigableEndLocation	Define if the end location is required to be a valid navmesh polygon //@UE
[in]	filter	The polygon filter to apply to the query.

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.

◆ isInClosedList()

bool dtNavMeshQuery::isInClosedList ( dtPolyRef ref ) const

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

Parameters

[in] ref The 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)

◆ isPointInsidePoly()

dtStatus dtNavMeshQuery::isPointInsidePoly	(	dtPolyRef	ref,
		const dtReal *	pos,
		bool &	result
	)		const

Checks if specified pos is inside given polygon specified by ref

Parameters

[in]	ref	The reference id of the polygon.
[in]	pos	The position to check. [(x, y, z)]
[out]	result	The result of the check, whether the point is inside (true) or not (false)

Returns: The status flags for the query.

◆ isRequiringNavigableEndLocation()

bool dtNavMeshQuery::isRequiringNavigableEndLocation ( ) const

inline

◆ isValidPolyRef()

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

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

Parameters

[in]	ref	The polygon reference to check.
[in]	filter	The filter to apply.

◆ moveAlongSurface()

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

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

Parameters

[in]	startRef	The reference id of the start polygon.
[in]	startPos	A position of the mover within the start polygon. [(x, y, x)]
[in]	endPos	The desired end position of the mover. [(x, y, z)]
[in]	filter	The polygon filter to apply to the query.
[out]	resultPos	The result position of the mover. [(x, y, z)]
[out]	visited	The reference ids of the polygons visited during the move.
[out]	visitedCount	The number of polygons visited during the move.
[in]	maxVisitedSize	The 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.

◆ passLinkFilter()

bool dtNavMeshQuery::passLinkFilter	(	const dtMeshTile *	tile,
		const int	polyIdx
	)		const

inline

◆ passLinkFilterByRef()

bool dtNavMeshQuery::passLinkFilterByRef	(	const dtMeshTile *	tile,
		const dtPolyRef	ref
	)		const

inline

◆ projectedPointOnPoly()

dtStatus dtNavMeshQuery::projectedPointOnPoly	(	dtPolyRef	ref,
		const dtReal *	pos,
		dtReal *	projected
	)		const

Finds the point's projection on the specified polygon.

Parameters

[in]	ref	The reference id of the polygon.
[in]	pos	The position to check. [(x, y, z)]
[out]	closest	The projected point on the polygon. [(x, y, z)]

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.

◆ queryPolygons()

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

Finds polygons that overlap the search box.

Parameters

[in]	center	The center of the search box. [(x, y, z)]
[in]	extents	The search distance along each axis. [(x, y, z)]
[in]	filter	The polygon filter to apply to the query.
[out]	polys	The reference ids of the polygons that overlap the query box.
[out]	polyCount	The number of polygons in the search result.
[in]	maxPolys	The maximum number of polygons the search result can hold.

Returns: The status flags for the query.

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

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

◆ raycast()

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

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

Parameters

[in]	startRef	The reference id of the start polygon.
[in]	startPos	A position within the start polygon representing the start of the ray. [(x, y, z)]
[in]	endPos	The position to cast the ray toward. [(x, y, z)]
[out]	t	The hit parameter. (DT_REAL_MAX if no wall hit.)
[out]	hitNormal	The normal of the nearest wall hit. [(x, y, z)]
[in]	filter	The polygon filter to apply to the query.
[out]	path	The reference ids of the visited polygons. [opt]
[out]	pathCount	The number of visited polygons. [opt]
[in]	maxPath	The maximum number of polygons the `path` array can hold.
[in]	walkableArea	Specific area that can be visited or 255 to skip it and test all areas.

Returns: The status flags for the query.

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

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

Using the Hit Parameter (t)

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

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

If 0 < t < 1.0 then the following applies:

distanceToHitBorder = distanceToEndPosition * t

hitPoint = startPos + (endPos - startPos) * t

StaticCastSharedRef

UE_FORCEINLINE_HINT TSharedRef< CastToType, Mode > StaticCastSharedRef(TSharedRef< CastFromType, Mode > const &InSharedRef)

Definition SharedPointer.h:127

Use Case Restriction

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

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

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

◆ setRequireNavigableEndLocation()

void dtNavMeshQuery::setRequireNavigableEndLocation ( const bool value )

inline

◆ updateLinkFilter()

void dtNavMeshQuery::updateLinkFilter ( dtQuerySpecialLinkFilter * linkFilter )

UE: updates special link filter for this query.

◆ updateSlicedFindPath()

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

Updates an in-progress sliced path query.

Parameters

[in]	maxIter	The maximum number of iterations to perform.
[out]	doneIters	The actual number of iterations completed. [opt]

Returns: The status flags for the query.

◆ wasClusterLinkSearched()

NAVMESH_API bool dtNavMeshQuery::wasClusterLinkSearched	(	dtPolyRef	cFrom,
		dtPolyRef	cTo
	)		const

Returns true if the cluster link was used in previous search.

Parameters

[in]	cFrom	The reference id of the start cluster.
[in]	cto	The reference id of the end cluster.

Returns: True if the cluster link was searched.

The documentation for this class was generated from the following files:

Engine/Source/Runtime/Navmesh/Public/Detour/DetourNavMeshQuery.h
Engine/Source/Runtime/Navmesh/Private/Detour/DetourNavMeshQuery.cpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ dtNavMeshQuery()

◆ ~dtNavMeshQuery()

Member Function Documentation

◆ appendPortals()

◆ appendVertex()

◆ closestPointOnPoly()

◆ closestPointOnPolyBoundary()

◆ finalizeSlicedFindPath()

◆ finalizeSlicedFindPathPartial()

◆ findDistanceToWall()

◆ findLocalNeighbourhood()

◆ findNearestContainingPoly()

◆ findNearestPoly()

◆ findNearestPoly2D()

◆ findPath()

◆ findPolysAroundCircle()

◆ findPolysAroundShape()

◆ findPolysInPathDistance()

◆ findRandomPoint()

◆ findRandomPointAroundCircle()

◆ findRandomPointInPoly()

◆ findStraightPath()

◆ findWallsAroundPath()

◆ findWallsInNeighbourhood()

◆ findWallsOverlappingShape()

◆ getAttachedNavMesh()

◆ getCurrentBestResult()

◆ getEdgeMidPoint() [1/2]

◆ getEdgeMidPoint() [2/2]

◆ getNodePool()

◆ getPolyHeight()

◆ getPolyWallSegments()

◆ getPortalPoints() [1/2]

◆ getPortalPoints() [2/2]

◆ getQueryNodes()

◆ init()

◆ initSlicedFindPath()

◆ isInClosedList()

◆ isPointInsidePoly()

◆ isRequiringNavigableEndLocation()

◆ isValidPolyRef()

◆ moveAlongSurface()

◆ passLinkFilter()

◆ passLinkFilterByRef()

◆ projectedPointOnPoly()

◆ queryPolygons()

◆ raycast()

◆ setRequireNavigableEndLocation()

◆ updateLinkFilter()

◆ updateSlicedFindPath()

◆ wasClusterLinkSearched()