UDocumentation UE5.7 10.02.2026 (Source)
API documentation for Unreal Engine 5.7
Classes | Public Types | Public Member Functions | Public Attributes | List of all members
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck > Struct Template Reference

#include <GraphAStar.h>

Classes

struct  FNodePool
 
struct  FNodeSorter
 
struct  FOpenList
 

Public Types

typedef TGraph::FNodeRef FGraphNodeRef
 
typedef TSearchNode FSearchNode
 
using FNodeArray = TArray< FSearchNode, FRangeChecklessAllocator< DoRangeCheck > >
 
using FRangeChecklessSetAllocator = TSetAllocator< TSparseArrayAllocator< FRangeChecklessAllocator< DoRangeCheck >, TInlineAllocator< 4, FRangeChecklessAllocator< DoRangeCheck > > >, TInlineAllocator< 1, FRangeChecklessAllocator< DoRangeCheck > > >
 
using FNodeMap = TMap< FGraphNodeRef, int32, FRangeChecklessSetAllocator >
 
using FIndexArray = TArray< int32, FRangeChecklessAllocator< DoRangeCheck > >
 

Public Member Functions

 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_1PARAM_CONST (int32, GetNeighbourCount, const FGraphNodeRef, NO_COUNT)
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_1PARAM_CONST (int32, GetNeighbourCountV2, const FSearchNode &, Obj.GetNeighbourCount(Param1.NodeRef))
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_2PARAMS_CONST (FGraphNodeRef, GetNeighbour, const FSearchNode &, const int32, Obj.GetNeighbour(Param1.NodeRef, Param2))
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST (bool, ShouldIgnoreClosedNodes, false)
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST (bool, ShouldIncludeStartNodeInPath, false)
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST (bool, ShouldFailOnInvalidEndNode, true)
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST (FVector::FReal, GetCostLimit, TNumericLimits< FVector::FReal >::Max())
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CUSTOM (GetMaxSearchNodes, bool, HasReachMaxSearchNodes, uint32 NodeCount, false, NodeCount >=Obj.GetMaxSearchNodes())
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CUSTOM (GetCostLimit, bool, HasExceededCostLimit, FVector::FReal Cost, false, Cost > Obj.GetCostLimit())
 
 DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_2PARAMS (FGraphNodeRef, SetPathInfo, const int32, const FSearchNode &, Obj[Param1]=Param2.NodeRef)
 
 FGraphAStar (const TGraph &InGraph)
 
template<typename TQueryFilter >
bool ProcessSingleNode (const FSearchNode &EndNode, const bool bIsBound, const TQueryFilter &Filter, int32 &OutBestNodeIndex, float &OutBestNodeCost)
 
template<typename TQueryFilter >
bool ProcessSingleNode (const FSearchNode &EndNode, const bool bIsBound, const TQueryFilter &Filter, int32 &OutBestNodeIndex, FVector::FReal &OutBestNodeCost)
 
template<typename TQueryFilter , typename TResultPathInfo = TArray<FGraphNodeRef>>
EGraphAStarResult FindPath (const FSearchNode &StartNode, const FSearchNode &EndNode, const TQueryFilter &Filter, TResultPathInfo &OutPath)
 
template<typename TQueryFilter >
EGraphAStarResult FloodFrom (const FSearchNode &StartNode, const TQueryFilter &Filter)
 
template<typename TQueryFilter >
bool HasReachMaxSearchNodes (const TQueryFilter &Filter) const
 

Public Attributes

const TGraph & Graph
 
FNodePool NodePool
 
FNodeSorter NodeSorter
 
FOpenList OpenList
 

Detailed Description

template<typename TGraph, typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
struct FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >

Generic graph A* implementation

TGraph holds graph representation. Needs to implement functions: bool IsValidRef(FNodeRef NodeRef) const; - returns whether given node identyfication is correct FNodeRef GetNeighbour(const FSearchNode& NodeRef, const int32 NeighbourIndex) const; - returns neighbour ref

it also needs to specify node type FNodeRef - type used as identification of nodes in the graph

TQueryFilter (FindPath's parameter) filter class is what decides which graph edges can be used and at what cost. It needs to implement following functions: FVector::FReal GetHeuristicScale() const; - used as GetHeuristicCost's multiplier FVector::FReal GetHeuristicCost(const FSearchNode& StartNode, const FSearchNode& EndNode) const; - estimate of cost from StartNode to EndNode from a search node FVector::FReal GetTraversalCost(const FSearchNode& StartNode, const FSearchNode& EndNode) const; - real cost of traveling from StartNode directly to EndNode from a search node bool IsTraversalAllowed(const FNodeRef NodeA, const FNodeRef NodeB) const; - whether traversing given edge is allowed from a NodeRef bool WantsPartialSolution() const; - whether to accept solutions that do not reach the goal

// Backward compatible methods, please use the FSearchNode version. If the FSearchNode version are implemented, these methods will not be called at all. FNodeRef GetNeighbour(const FNodeRef NodeRef, const int32 NeighbourIndex) const; - returns neighbour ref FVector::FReal GetHeuristicCost(const FNodeRef StartNodeRef, const FNodeRef EndNodeRef) const; - estimate of cost from StartNode to EndNode from a NodeRef FVector::FReal GetTraversalCost(const FNodeRef StartNodeRef, const FNodeRef EndNodeRef) const; - real cost of traveling from StartNode directly to EndNode from a NodeRef

// Optionally implemented methods to parameterize the search int32 GetNeighbourCount(FNodeRef NodeRef) const; - returns number of neighbours that the graph node identified with NodeRef has, it is ok if not implemented, the logic will stop calling GetNeighbour once it received an invalid noderef bool ShouldIgnoreClosedNodes() const; - whether to revisit closed node or not bool ShouldIncludeStartNodeInPath() const; - whether to put the start node in the resulting path bool ShouldFailOnInvalidEndNode() const; - whether to early out if the end node is not valid int32 GetMaxSearchNodes() const; - whether to limit the number of search nodes to a maximum FVector::FReal GetCostLimit() const - whether to limit the search to a maximum cost

Member Typedef Documentation

◆ FGraphNodeRef

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
typedef TGraph::FNodeRef FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FGraphNodeRef

◆ FIndexArray

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
using FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FIndexArray = TArray<int32, FRangeChecklessAllocator<DoRangeCheck> >

◆ FNodeArray

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
using FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FNodeArray = TArray<FSearchNode, FRangeChecklessAllocator<DoRangeCheck> >

◆ FNodeMap

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
using FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FNodeMap = TMap<FGraphNodeRef, int32, FRangeChecklessSetAllocator>

◆ FRangeChecklessSetAllocator

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
using FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FRangeChecklessSetAllocator = TSetAllocator<TSparseArrayAllocator<FRangeChecklessAllocator<DoRangeCheck>, TInlineAllocator<4, FRangeChecklessAllocator<DoRangeCheck> >>, TInlineAllocator<1, FRangeChecklessAllocator<DoRangeCheck> >>

◆ FSearchNode

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
typedef TSearchNode FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FSearchNode

Constructor & Destructor Documentation

◆ FGraphAStar()

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FGraphAStar ( const TGraph &  InGraph)
inline

Member Function Documentation

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_1PARAM_CONST() [1/2]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_1PARAM_CONST ( int32  ,
GetNeighbourCount  ,
const FGraphNodeRef  ,
NO_COUNT   
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_1PARAM_CONST() [2/2]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_1PARAM_CONST ( int32  ,
GetNeighbourCountV2  ,
const FSearchNode &  ,
Obj.  GetNeighbourCountParam1.NodeRef 
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_2PARAMS()

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_2PARAMS ( FGraphNodeRef  ,
SetPathInfo  ,
const int32  ,
const FSearchNode &  ,
Obj  [Param1] = Param2.NodeRef 
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_2PARAMS_CONST()

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_2PARAMS_CONST ( FGraphNodeRef  ,
GetNeighbour  ,
const FSearchNode &  ,
const int32  ,
Obj.  GetNeighbourParam1.NodeRef, Param2 
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST() [1/4]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST ( bool  ,
ShouldFailOnInvalidEndNode  ,
true   
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST() [2/4]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST ( bool  ,
ShouldIgnoreClosedNodes  ,
false   
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST() [3/4]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST ( bool  ,
ShouldIncludeStartNodeInPath  ,
false   
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST() [4/4]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CONST ( FVector::FReal  ,
GetCostLimit  ,
TNumericLimits< FVector::FReal >  ::Max() 
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CUSTOM() [1/2]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CUSTOM ( GetCostLimit  ,
bool  ,
HasExceededCostLimit  ,
FVector::FReal  Cost,
false  ,
Cost  ,
Obj.  GetCostLimit() 
)

◆ DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CUSTOM() [2/2]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::DECLARE_OPTIONALLY_IMPLEMENTED_TEMPLATE_CLASS_FUNCTION_CUSTOM ( GetMaxSearchNodes  ,
bool  ,
HasReachMaxSearchNodes  ,
uint32  NodeCount,
false  ,
NodeCount >=Obj.  GetMaxSearchNodes() 
)

◆ FindPath()

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
template<typename TQueryFilter , typename TResultPathInfo = TArray<FGraphNodeRef>>
EGraphAStarResult FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FindPath ( const FSearchNode &  StartNode,
const FSearchNode &  EndNode,
const TQueryFilter &  Filter,
TResultPathInfo &  OutPath 
)
inline

Performs the actual search.

Parameters
[OUT]OutPath - on successful search contains a sequence of graph nodes representing solution optimal within given constraints

◆ FloodFrom()

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
template<typename TQueryFilter >
EGraphAStarResult FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::FloodFrom ( const FSearchNode &  StartNode,
const TQueryFilter &  Filter 
)
inline

Floods node pool until running out of either free nodes or open set

◆ HasReachMaxSearchNodes()

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
template<typename TQueryFilter >
bool FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::HasReachMaxSearchNodes ( const TQueryFilter &  Filter) const
inline

◆ ProcessSingleNode() [1/2]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
template<typename TQueryFilter >
bool FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::ProcessSingleNode ( const FSearchNode &  EndNode,
const bool  bIsBound,
const TQueryFilter &  Filter,
int32 &  OutBestNodeIndex,
float &  OutBestNodeCost 
)
inline

Single run of A* loop: get node from open set and process neighbors returns true if loop should be continued

◆ ProcessSingleNode() [2/2]

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
template<typename TQueryFilter >
bool FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::ProcessSingleNode ( const FSearchNode &  EndNode,
const bool  bIsBound,
const TQueryFilter &  Filter,
int32 &  OutBestNodeIndex,
FVector::FReal &  OutBestNodeCost 
)
inline

Single run of A* loop: get node from open set and process neighbors returns true if loop should be continued

Member Data Documentation

◆ Graph

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
const TGraph& FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::Graph

◆ NodePool

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FNodePool FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::NodePool

◆ NodeSorter

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FNodeSorter FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::NodeSorter

◆ OpenList

template<typename TGraph , typename Policy = FGraphAStarDefaultPolicy, typename TSearchNode = FGraphAStarDefaultNode<TGraph>, bool DoRangeCheck = false>
FOpenList FGraphAStar< TGraph, Policy, TSearchNode, DoRangeCheck >::OpenList
The documentation for this struct was generated from the following file: