#include <astarquery.h>

Class Description

template<class TraverseLogic>
class Kaim::AStarQuery< TraverseLogic >

Runs an A-star algorithm to find a Path through the navigation data (NavMesh & NavGraph) from a starting point to a destination, refines the path found, and fills an object of type Path.

The template argument must be a class that have at least these three static functions :

bool CanTraverseNavTriangle(void* traverseLogicUserData, const NavTag& navTag)
bool CanTraverseAndGetCostMultiplier(void* traverseLogicUserData, const Kaim::NavTag& navTag, const Kaim::Vec3f& start,
    const Kaim::Vec3f& end, CostMultiplierCallContext callContext, KyFloat32& costMultiplier);
KyFloat32 GetHeuristicFromDistanceToDest(KyFloat32 distance3DToDestination)

The template argument must also have to define a type CanEnterNavTagMode with typedef as follow, depending whether or not you have one-way navTag transition :

typedef DoNotUseCanEnterNavTag CanEnterNavTagMode; // this to indicate there is no One-Way navTag switch at all`

or

typedef UseCanEnterNavTag CanEnterNavTagMode; // this to indicate there can be some One-Way navTag switched that need to be considered during pathFinding

If you are using UseCanEnterNavTag, you also have to implement this function :

bool CanEnterNavTag(const NavTag& exitNavTag, const NavTag& enterNavTag, const Vec3f& pos)

This function must tell if, at position pos, we can go from exitNavTag to enterNavTag. Please refer to the SimpleTraverseLogic class documentation for details on these functions

Note that the template argument is stored in value within this class.

The propagation of the AStarQuery is bound to 2d oriented bounding box computed by inflating the segment going from startPos to destPos by a boxExtent that can be modified by calling the SetPropagationBoxExtent method. Note that bounds are only in 2D.

                     Propagation bounding box
 ____________________________________________________________________________
|                                                                           ^
|                                                                           |
|<----------->                                                 <----------->| boxExtent
|  boxExtent                                                      boxExtent |
|             x===============================================x             x
|        startPos                                         destPos           |
|                                                                           | boxExtent
|                                                                           |
|___________________________________________________________________________v

Examples:: gamekit/Tutorial_GameKitTraverseLogic.cpp, performance/Tutorial_MultiThreading.cpp, performance/Tutorial_MultiThreading_5_worlds.cpp, performance/Tutorial_NoTimeSlicing.cpp, Tutorial_FirstIntegration.cpp, Tutorial_Generation_postProcess.cpp, Tutorial_QueryQueue.cpp, and Tutorial_TrackingMemoryLeak.cpp.

Inherits Kaim::BaseAStarQuery.

Public Types
enum	PathFinderResult { PathFinderNotInitialized, PathFinderNotComputed, PathFinderUnderProcess, PathFinderSuccess, PathFinderFailure, PathFinderFailure_NavDataChanged }
	Enumerates the possible status of a IPathFinderQuery. More...

Public Member Functions
virtual void	Advance (WorkingMemory *workingMemory)
	This function is called by the QueryQueue to process one step on the query. More...

virtual void	ReleaseWorkingMemoryOnCancelDuringProcess (WorkingMemory *workingMemory=nullptr)
	Called when a query is canceled in FlushCommands while its status is QueryInProcess to make sure that the WorkingMemory is left in valid state (typically, no WorkingMemory buffer should be in used after this call). More...

Public Attributes
QueryProcessStatus	m_processStatus
	Modified by the query within Advance(). Do not modify. More...

Ptr< IOnDone >	m_onDone
	The optional IOnDone instance to be called. Must be set manually by the user. See IOnDone. More...

For internal use only
bool	TraversalHasVisitedNavDataChanged ()

Functions
void	SetNavigationProfileId (KyUInt32 navigationProfileId)

KyUInt32	GetNavigationProfileId () const

Public Data Members
KyUInt32	m_navigationProfileId

Vec3f	m_startPos3f
	The starting position for the Path request. More...

PathFinderQueryComputeChannelMode	m_computeChannelMode
	The mode toggling Channels computation. More...

ChannelComputerConfig	m_channelComputerConfig
	The parameter set specific to Channels computation. More...

FullDebug	m_fullDebug

bool	m_doClampRawPath

KyUInt32	m_lastAdvanceDatabaseChangeIdx

Ptr< Path >	m_path
	The Path found by the query. More...

IQuery implementation
virtual QueryType	GetType () const
	Get query type. More...

virtual void	BuildQueryBlob (BaseBlobHandler *blobHandler)

virtual void	InitFromQueryBlob (World world, void blob)

virtual Ptr< BaseBlobHandler >	CreateQueryBlobHandler ()

IPathFinderQuery implementation
virtual void	GetPathFinderTextResult (String &) const
	Fills the String with an explanation of the result. Use this to debug your pathfinder query. More...

virtual void	DisplayPropagationBounds (DisplayList &displayList) const
	Fill the displayList with display info that may help to understand a PathFinderFailure (mainly propagation bounds) More...

virtual PathFinderResult	GetPathFinderResult () const

virtual const Vec3f *	GetDestination () const
	This function is virtual because not all the PathFinders have a preset destination, it may return nullptr. More...

BindToDatabase
void	BindToDatabase (Database *database)
	Binds the query with database, clears inputs and results, sets the configuration to defaults. More...

inputs setters
void	Initialize (const Vec3f &startPos, const Vec3f &destPos)
	Clears inputs and results, leaves configuration unchanged. More...

void	SetStartTrianglePtr (const NavTrianglePtr &startTrianglePtr)
	If no startTrianglePtr is set, it will be automatically computed during the query. More...

void	SetStartNavGraphEdgePtr (const NavGraphEdgePtr &startNavGraphEdgePtr, NavGraphEdgeDirection startNavGraphEdgeDirection)
	Sets start inside a NavGraphEdge. if startNavGraphEdgeDirection specifies if query can start in reverse edge if it exists. More...

void	SetStartNavGraphVertexPtr (const NavGraphVertexPtr &startNavGraphVertexPtr)
	Sets start to a NavGraphVertex. Optional input. More...

void	SetDestTrianglePtr (const NavTrianglePtr &destTrianglePtr)
	If no destTrianglePtr is set, it will be automatically computed during the query. Optional input. More...

void	SetDestNavGraphEdgePtr (const NavGraphEdgePtr &destNavGraphEdgePtr, NavGraphEdgeDirection destNavGraphEdgeDirection)
	Sets destination inside a NavGraphEdge. destNavGraphEdgeDirection specifies if query can start in reverse edge if it exists. More...

void	SetDestNavGraphVertexPtr (const NavGraphVertexPtr &destNavGraphVertexPtr)
	Sets destination to a NavGraphVertex. More...

configuration setters
void	SetTryCanGoMode (PathFinderQueryTryCanGoMode tryCanGoMode)

void	SetPropagationBoxExtent (KyFloat32 propagationBoxExtent)

void	SetFromOutsideNavMeshDistance (KyFloat32 fromOutsideNavMeshDistance)

void	SetToOutsideNavMeshDistance (KyFloat32 toOutsideNavMeshDistance)

void	SetAbstractGraphTraversalMode (PathFinderAbstractGraphTraversalMode abstractGraphTraversalMode)

void	SetComputeChannelMode (PathFinderQueryComputeChannelMode computeChannelMode)

void	SetChannelComputerConfig (const ChannelComputerConfig &channelComputerConfig)

void	SetPositionSpatializationRange (const PositionSpatializationRange &positionSpatializationRange)

void	SetNumberOfProcessedNodePerFrame (KyUInt32 numberOfProcessedNodePerFrame)

void	SetPathClamperFlagMask (PathClamperFlagMask pathClamperFlagMask)

results getter
Path *	GetPath () const

Path *	GetAbstractPath () const

AStarQueryResult	GetResult () const

ChannelArrayComputerResult	GetChannelResult () const

inputs getters
const Vec3f &	GetStartPos () const

const NavTrianglePtr &	GetStartTrianglePtr () const

const NavGraphEdgePtr &	GetStartNavGraphEdgePtr () const

const NavGraphVertexPtr &	GetStartNavGraphVertexPtr () const

const Vec3f &	GetDestPos () const

const NavTrianglePtr &	GetDestTrianglePtr () const

const NavGraphEdgePtr &	GetDestNavGraphEdgePtr () const

const NavGraphVertexPtr &	GetDestNavGraphVertexPtr () const

configuration getters
PathFinderQueryTryCanGoMode	GetTryCanGoMode () const

KyFloat32	GetPropagationBoxExtent () const

KyFloat32	GetFromOutsideNavMeshDistance () const

KyFloat32	GetToOutsideNavMeshDistance () const

PathClamperFlagMask	GetPathClamperFlagMask () const

PathFinderAbstractGraphTraversalMode	GetAbstractGraphTraversalMode () const

PathFinderQueryComputeChannelMode	GetComputeChannelMode () const

const ChannelComputerConfig &	GetChannelComputerConfig () const

const PositionSpatializationRange &	GetPositionSpatializationRange () const

KyUInt32	GetNumberOfProcessedNodePerFrame () const

For internal use only
void	ComputePathRefinerConfigInternals ()

const PathRefinerConfig &	GetPathRefinerConfig () const

start
NavTrianglePtr	m_startTrianglePtr
	If no m_startTrianglePtr is set, it will be automatically computed from m_startPos3f. More...

NavGraphEdgePtr	m_startNavGraphEdgePtr
	if valid, query starts inside a NavGraphEdge More...

NavGraphEdgeDirection	m_startNavGraphEdgeDirection
	if NAVGRAPHEDGE_BIDIRECTIONAL query starts also inside m_startNavGraphEdgePtr reverse edge if it exists. More...

NavGraphVertexPtr	m_startNavGraphVertexPtr
	if valid, query starts at m_startNavGraphVertexPtr More...

destination
Vec3f	m_destPos3f
	The destination position. More...

NavTrianglePtr	m_destTrianglePtr
	If no m_destTrianglePtr is set, it will be automatically computed from m_destPos3f. More...

NavGraphEdgePtr	m_destNavGraphEdgePtr
	if valid, query ends inside a NavGraphEdge More...

NavGraphEdgeDirection	m_destNavGraphEdgeDirection
	if NAVGRAPHEDGE_BIDIRECTIONAL query ends also inside m_startNavGraphEdgePtr reverse edge if it exists. More...

NavGraphVertexPtr	m_destNavGraphVertexPtr
	if valid, query ends at m_startNavGraphVertexPtr More...

configuration
PathFinderQueryTryCanGoMode	m_tryCanGoMode
	default PATHFINDER_TRY_RAYCANGO_IF_NO_COST More...

PathRefinerConfig	m_pathRefinerConfig

PathClamperFlagMask	m_pathClamperFlagMask
	default PathClamperFlag_ClampAll More...

PathFinderAbstractGraphTraversalMode	m_abstractGraphTraversalMode
	default PATHFINDER_TRAVERSE_ABSTRACT_GRAPHS More...

KyFloat32	m_propagationBoxExtent
	limits propagation to the (start-dest) segment inflated by m_propagationBoxExtent. default 200.0f More...

computed
Vec3f	m_startInsidePos3f
	if m_startPos3f is outside NavMesh it is the computed inside pos in the 2d range of m_fromOutsideNavMeshDistance More...

Vec3f	m_destInsidePos3f
	if m_destInsidePos3f is outside NavMesh it is the computed inside pos in the 2d range of m_toOutsideNavMeshDistance More...

bool	m_isStartTriangleHooked

TraversalParameters	m_traversalParams

Ptr< CellFilter >	m_propagationCellFilter

results
Ptr< Path >	m_abstractPath
	The Abstract Path found by the query. More...

AStarQueryResult	m_result
	Updated during processing to indicate the result of the PathFinderQueryResult query. More...

ChannelArrayComputerResult	m_channelResult

IQuery Functions
bool	CanBeInitialized () const
	In the case of a query processed in a QueryQueue, this must be tested before initializing the query, to prevent modifying the query during the process. More...

bool	IsInAQueryQueue () const
	Returns true if the query is currently registered in a QueryQueue. More...

bool	IsSafeToReadResult () const
	Returns true if the query has been processed, is no longer in a queue, and OnDone (if there is one) has been called. More...

KyUInt32	PerformQueryBlocking (WorkingMemory *workingMemory=nullptr)
	Calls Advance() untill the query is done. More...

void	OnDone ()
	Calls m_onDone IOnDone::OnDone() if m_onDone is not null. More...

KyResult	SendVisualDebug ()
	Sends the query to the NavigationLab. More...

void	SetTraverseLogicUserData (void *traverseLogicUserData)
	Sets m_traverseLogicUserData for queries that have a custom TraverseLogic, useless otherwise. More...

void *	GetTraverseLogicUserData () const
	Gets m_traverseLogicUserData. More...

For internal use only
static const char *	GetQueryTypeName (QueryType queryType)

Database *	m_database
	The database on which the query will be performed. Set in Initialize(), do not directly modify. More...

void *	m_traverseLogicUserData
	This userData is typically passed by the Bot. More...

QueryQueue *	m_queue
	Updated by the QueryQueue. Do not modify. More...

QueryStatusInQueue	m_inQueueStatus
	Used by the QueryQueue. Do not modify. More...

KyUInt32	m_queryInfoId

Member Enumeration Documentation

enum Kaim::IPathFinderQuery::PathFinderResult

inherited

Enumerates the possible status of a IPathFinderQuery.

Enumerator
PathFinderNotInitialized	The IPathFinderQuery is not yet initialized.
PathFinderNotComputed	The IPathFinderQuery is initialized but has not been processed.
PathFinderUnderProcess	The IPathFinderQuery is currently under process.
PathFinderSuccess	The IPathFinderQuery has been completed and a Path has been found.
PathFinderFailure	The IPathFinderQuery has been completed but no Path has been found.
PathFinderFailure_NavDataChanged	The IPathFinderQuery ended prematurely due to changes into NavData.

Member Function Documentation

template<class TLogic >

void Kaim::AStarQuery< TLogic >::Advance ( WorkingMemory * workingMemory )

inlinevirtual

This function is called by the QueryQueue to process one step on the query.

One call to Advance should be short (< 0.1ms as too long). It's Advance() responsibility to update m_processStatus. If the query is atomic, one call to Advance() will fully perform the query and set m_processStatus to QueryDone. If the query is time-sliced, several calls to Advance() will be needed to complete the query. the first call should set m_processStatus to Kaim::QueryInProcess and the last one to Kaim::QueryDone.

Parameters

workingMemory Sandbox memory used to perform queries.

Implements Kaim::IQuery.

void Kaim::BaseAStarQuery::BindToDatabase ( Database * database )

inherited

Binds the query with database, clears inputs and results, sets the configuration to defaults.

Examples:: performance/Tutorial_MultiThreading.cpp, and Tutorial_FirstIntegration.cpp.

bool Kaim::IQuery::CanBeInitialized ( ) const

inlineinherited

In the case of a query processed in a QueryQueue, this must be tested before initializing the query, to prevent modifying the query during the process.

void Kaim::BaseAStarQuery::DisplayPropagationBounds ( DisplayList & ) const

virtualinherited

Fill the displayList with display info that may help to understand a PathFinderFailure (mainly propagation bounds)

Reimplemented from Kaim::IPathFinderQuery.

virtual const Vec3f* Kaim::BaseAStarQuery::GetDestination ( ) const

inlinevirtualinherited

This function is virtual because not all the PathFinders have a preset destination, it may return nullptr.

Implements Kaim::IPathFinderQuery.

void Kaim::BaseAStarQuery::GetPathFinderTextResult ( String & ) const

virtualinherited

Fills the String with an explanation of the result. Use this to debug your pathfinder query.

Reimplemented from Kaim::IPathFinderQuery.

void* Kaim::IQuery::GetTraverseLogicUserData ( ) const

inlineinherited

Gets m_traverseLogicUserData.

virtual QueryType Kaim::BaseAStarQuery::GetType ( ) const

inlinevirtualinherited

Get query type.

Implements Kaim::IQuery.

void Kaim::BaseAStarQuery::Initialize	(	const Vec3f &	startPos,
		const Vec3f &	destPos
	)

inherited

Clears inputs and results, leaves configuration unchanged.

bool Kaim::IQuery::IsInAQueryQueue ( ) const

inlineinherited

Returns true if the query is currently registered in a QueryQueue.

If true, you must not push it again in QueryQueue (even the same one). If false, you must not try to cancel it from the QueryQueue.

bool Kaim::IQuery::IsSafeToReadResult ( ) const

inlineinherited

Returns true if the query has been processed, is no longer in a queue, and OnDone (if there is one) has been called.

If true, it's guaranteed to be safe to read the results of this query. Will return false if the Query has been cancelled or has not yet been processed.

void Kaim::IQuery::OnDone ( )

inlineinherited

Calls m_onDone IOnDone::OnDone() if m_onDone is not null.

Called automatically by the QueryQueue during the World::Update() (in the FlushQueries() step) when this query has been completed. OnDone() is not called if the query is canceled. Note that the member m_onDone is reset to nullptr at the end of this function.

KyUInt32 Kaim::IQuery::PerformQueryBlocking ( WorkingMemory * workingMemory = nullptr )

inherited

Calls Advance() untill the query is done.

Parameters

workingMemory Sandbox memory used to perform queries. If not set, m_database.GetWorkingMemory() will be used.

Returns: the number of call to Advance() (timesliced iterations) it took to perform the query.

template<class TLogic >

void Kaim::AStarQuery< TLogic >::ReleaseWorkingMemoryOnCancelDuringProcess ( WorkingMemory * workingMemory = nullptr )

inlinevirtual

Called when a query is canceled in FlushCommands while its status is QueryInProcess to make sure that the WorkingMemory is left in valid state (typically, no WorkingMemory buffer should be in used after this call).

Implements Kaim::ITimeSlicedQuery.

KyResult Kaim::IQuery::SendVisualDebug ( )

inherited

Sends the query to the NavigationLab.

Currently the implementation transform the query using a DisplayList, and the display list is shown only at the frame SendVisualDebug is called.

void Kaim::BaseAStarQuery::SetDestNavGraphEdgePtr	(	const NavGraphEdgePtr &	destNavGraphEdgePtr,
		NavGraphEdgeDirection	destNavGraphEdgeDirection
	)

inlineinherited

Sets destination inside a NavGraphEdge. destNavGraphEdgeDirection specifies if query can start in reverse edge if it exists.

void Kaim::BaseAStarQuery::SetDestNavGraphVertexPtr ( const NavGraphVertexPtr & destNavGraphVertexPtr )

inlineinherited

Sets destination to a NavGraphVertex.

void Kaim::BaseAStarQuery::SetDestTrianglePtr ( const NavTrianglePtr & destTrianglePtr )

inlineinherited

If no destTrianglePtr is set, it will be automatically computed during the query. Optional input.

void Kaim::BaseAStarQuery::SetStartNavGraphEdgePtr	(	const NavGraphEdgePtr &	startNavGraphEdgePtr,
		NavGraphEdgeDirection	startNavGraphEdgeDirection
	)

inlineinherited

Sets start inside a NavGraphEdge. if startNavGraphEdgeDirection specifies if query can start in reverse edge if it exists.

void Kaim::BaseAStarQuery::SetStartNavGraphVertexPtr ( const NavGraphVertexPtr & startNavGraphVertexPtr )

inlineinherited

Sets start to a NavGraphVertex. Optional input.

void Kaim::BaseAStarQuery::SetStartTrianglePtr ( const NavTrianglePtr & startTrianglePtr )

inlineinherited

If no startTrianglePtr is set, it will be automatically computed during the query.

void Kaim::IQuery::SetTraverseLogicUserData ( void * traverseLogicUserData )

inlineinherited

Sets m_traverseLogicUserData for queries that have a custom TraverseLogic, useless otherwise.

Member Data Documentation

PathFinderAbstractGraphTraversalMode Kaim::BaseAStarQuery::m_abstractGraphTraversalMode

protectedinherited

default PATHFINDER_TRAVERSE_ABSTRACT_GRAPHS

Ptr<Path> Kaim::BaseAStarQuery::m_abstractPath

protectedinherited

The Abstract Path found by the query.

ChannelComputerConfig Kaim::IPathFinderQuery::m_channelComputerConfig

inherited

The parameter set specific to Channels computation.

PathFinderQueryComputeChannelMode Kaim::IPathFinderQuery::m_computeChannelMode

inherited

The mode toggling Channels computation.

Database* Kaim::IQuery::m_database

inherited

The database on which the query will be performed. Set in Initialize(), do not directly modify.

Vec3f Kaim::BaseAStarQuery::m_destInsidePos3f

protectedinherited

if m_destInsidePos3f is outside NavMesh it is the computed inside pos in the 2d range of m_toOutsideNavMeshDistance

NavGraphEdgeDirection Kaim::BaseAStarQuery::m_destNavGraphEdgeDirection

protectedinherited

if NAVGRAPHEDGE_BIDIRECTIONAL query ends also inside m_startNavGraphEdgePtr reverse edge if it exists.

NavGraphEdgePtr Kaim::BaseAStarQuery::m_destNavGraphEdgePtr

protectedinherited

if valid, query ends inside a NavGraphEdge

NavGraphVertexPtr Kaim::BaseAStarQuery::m_destNavGraphVertexPtr

protectedinherited

if valid, query ends at m_startNavGraphVertexPtr

Vec3f Kaim::BaseAStarQuery::m_destPos3f

protectedinherited

The destination position.

NavTrianglePtr Kaim::BaseAStarQuery::m_destTrianglePtr

protectedinherited

If no m_destTrianglePtr is set, it will be automatically computed from m_destPos3f.

QueryStatusInQueue Kaim::IQuery::m_inQueueStatus

inherited

Used by the QueryQueue. Do not modify.

Ptr<IOnDone> Kaim::IQuery::m_onDone

inherited

The optional IOnDone instance to be called. Must be set manually by the user. See IOnDone.

Ptr<Path> Kaim::IPathFinderQuery::m_path

inherited

The Path found by the query.

PathClamperFlagMask Kaim::BaseAStarQuery::m_pathClamperFlagMask

protectedinherited

default PathClamperFlag_ClampAll

QueryProcessStatus Kaim::IQuery::m_processStatus

inherited

Modified by the query within Advance(). Do not modify.

Before reading m_processStatus, always ensure IsInAQueryQueue() returns false.

KyFloat32 Kaim::BaseAStarQuery::m_propagationBoxExtent

protectedinherited

limits propagation to the (start-dest) segment inflated by m_propagationBoxExtent. default 200.0f

QueryQueue* Kaim::IQuery::m_queue

inherited

Updated by the QueryQueue. Do not modify.

AStarQueryResult Kaim::BaseAStarQuery::m_result

protectedinherited

Updated during processing to indicate the result of the PathFinderQueryResult query.

Vec3f Kaim::BaseAStarQuery::m_startInsidePos3f

protectedinherited

if m_startPos3f is outside NavMesh it is the computed inside pos in the 2d range of m_fromOutsideNavMeshDistance

NavGraphEdgeDirection Kaim::BaseAStarQuery::m_startNavGraphEdgeDirection

protectedinherited

if NAVGRAPHEDGE_BIDIRECTIONAL query starts also inside m_startNavGraphEdgePtr reverse edge if it exists.

NavGraphEdgePtr Kaim::BaseAStarQuery::m_startNavGraphEdgePtr

protectedinherited

if valid, query starts inside a NavGraphEdge

NavGraphVertexPtr Kaim::BaseAStarQuery::m_startNavGraphVertexPtr

protectedinherited

if valid, query starts at m_startNavGraphVertexPtr

Vec3f Kaim::IPathFinderQuery::m_startPos3f

inherited

The starting position for the Path request.

NavTrianglePtr Kaim::BaseAStarQuery::m_startTrianglePtr

protectedinherited

If no m_startTrianglePtr is set, it will be automatically computed from m_startPos3f.

void* Kaim::IQuery::m_traverseLogicUserData

inherited

This userData is typically passed by the Bot.

PathFinderQueryTryCanGoMode Kaim::BaseAStarQuery::m_tryCanGoMode

protectedinherited

default PATHFINDER_TRY_RAYCANGO_IF_NO_COST

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

gwnavruntime/queries/astarquery.h
gwnavruntime/queries/astarquery.inl

Kaim::AStarQuery< TraverseLogic > Class Template Reference

Class Description

template<class TraverseLogic> class Kaim::AStarQuery< TraverseLogic >

Public Types

Public Member Functions

Public Attributes

For internal use only

Functions

Public Data Members

IQuery implementation

IPathFinderQuery implementation

BindToDatabase

inputs setters

configuration setters

results getter

inputs getters

configuration getters

For internal use only

start

destination

configuration

computed

results

IQuery Functions

For internal use only

Member Enumeration Documentation

Member Function Documentation

Member Data Documentation

template<class TraverseLogic>
class Kaim::AStarQuery< TraverseLogic >