ezEngine  Milestone 7
ezPathSearch< PathStateType > Class Template Reference

Implements a directed breadth-first search through a graph (A*). More...

#include <GraphSearch.h>

Classes

struct  PathResultData
 FindPath() and FindClosest() return an array of these objects as the path result. More...
 

Public Types

typedef bool(* IsSearchedObjectCallback )(ezInt64 iStartNodeIndex, const PathStateType &StartState)
 Used by FindClosest() to query whether the currently visited node fulfills the termination criteria.
 

Public Member Functions

void SetPathStateGenerator (ezPathStateGenerator< PathStateType > *pStateGenerator)
 Sets the ezPathStateGenerator that should be used by this ezPathSearch object.
 
ezResult FindPath (ezInt64 iStartNodeIndex, const PathStateType &StartState, ezInt64 iTargetNodeIndex, ezDeque< PathResultData > &out_Path, float fMaxPathCost=ezMath::BasicType< float >::GetInfinity())
 Searches for a path that starts at the graph node iStartNodeIndex with the start state StartState and shall terminate when the graph node iTargetNodeIndex was reached. More...
 
ezResult FindClosest (ezInt64 iStartNodeIndex, const PathStateType &StartState, IsSearchedObjectCallback Callback, ezDeque< PathResultData > &out_Path, float fMaxPathCost=ezMath::BasicType< float >::GetInfinity())
 Searches for a path that starts at the graph node iStartNodeIndex with the start state StartState and shall terminate when a graph node is reached for which Callback return true. More...
 
void AddPathNode (ezInt64 iNodeIndex, const PathStateType &NewState)
 Needs to be called by the used ezPathStateGenerator to add nodes to evaluate.
 

Private Member Functions

void ClearPathStates ()
 
ezInt64 FindBestNodeToExpand (PathStateType *&out_pPathState)
 
void FillOutPathResult (ezInt64 iEndNodeIndex, ezDeque< PathResultData > &out_Path)
 

Private Attributes

ezPathStateGenerator
< PathStateType > * 
m_pStateGenerator
 
ezHashTable< ezInt64,
PathStateType > 
m_PathStates
 
ezDeque< ezInt64 > m_StateQueue
 
ezInt64 m_iCurNodeIndex
 
PathStateType m_CurState
 

Detailed Description

template<typename PathStateType>
class ezPathSearch< PathStateType >

Implements a directed breadth-first search through a graph (A*).

You can search for a path to a specific location using FindPath() or to the closest node that fulfills some arbitrary criteria using FindClosest().

PathStateType must be derived from ezPathStateBase and can be used for keeping track of certain state along a path and to modify the path search dynamically.

Member Function Documentation

template<typename PathStateType >
ezResult ezPathSearch< PathStateType >::FindClosest ( ezInt64  iStartNodeIndex,
const PathStateType &  StartState,
IsSearchedObjectCallback  Callback,
ezDeque< PathResultData > &  out_Path,
float  fMaxPathCost = ezMath::BasicType<float>::GetInfinity() 
)

Searches for a path that starts at the graph node iStartNodeIndex with the start state StartState and shall terminate when a graph node is reached for which Callback return true.

Returns EZ_FAILURE if no path could be found. Returns the path result as a list of PathResultData objects in out_Path.

The path search is stopped (and thus fails) if the path reaches costs of fMaxPathCost or higher.

template<typename PathStateType >
ezResult ezPathSearch< PathStateType >::FindPath ( ezInt64  iStartNodeIndex,
const PathStateType &  StartState,
ezInt64  iTargetNodeIndex,
ezDeque< PathResultData > &  out_Path,
float  fMaxPathCost = ezMath::BasicType<float>::GetInfinity() 
)

Searches for a path that starts at the graph node iStartNodeIndex with the start state StartState and shall terminate when the graph node iTargetNodeIndex was reached.

Returns EZ_FAILURE if no path could be found. Returns the path result as a list of PathResultData objects in out_Path.

The path search is stopped (and thus fails) if the path reaches costs of fMaxPathCost or higher.


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