1. Epic GamesDeveloper
  3. FGraphAStar

FGraphAStar

Generic graph A* implementation

Unreal Engine C++ API Reference > Runtime > AIModule

References

   
Module AIModule
Header /Engine/Source/Runtime/AIModule/Public/GraphAStar.h
Include #include "GraphAStar.h"

Syntax

template<typename TGraph, typename Policy, typename TSearchNode, bool DoRangeCheck>  
struct FGraphAStar

Remarks

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

Variables

  Type Name Description
Public variable const TGraph & Graph  
Public variable FNodePool NodePool  
Public variable FNodeSorter NodeSorter  
Public variable FOpenList OpenList  

Constructors

  Type Name Description
Public function  

FGraphAStar ( const TGraph& InGraph
)

  

Functions

  Type Name Description
Public function EGraphAStarResult

FindPath ( const FSearchNode& StartNode,
const FSearchNode& EndNode,
const TQueryFilter& Filter,
TResultPathInfo& OutPath
)

 Performs the actual search.
Public function EGraphAStarResult

FloodFrom ( const FSearchNode& StartNode,
const TQueryFilter& Filter
)

 Floods node pool until running out of either free nodes or open set
Public function Static decltype(auto)

GetCostLimit ( const TemplateClass& Obj
)

  
Public function Static decltype(auto)

GetHeuristicCost ( const TemplateClass& Obj,
const FSearchNode& Param1,
const FSearchNode& Param2
)

  
Public function Static decltype(auto)

GetNeighbour ( const TemplateClass& Obj,
const FSearchNode& Param1,
const int32 Param2
)

  
Public function Static decltype(auto)

GetNeighbourCount ( const TemplateClass& Obj,
const FGraphNodeRef Param1
)

  
Public function Static decltype(auto)

GetNeighbourCountV2 ( const TemplateClass& Obj,
const FSearchNode& Param1
)

  
Public function Static decltype(auto)

GetTraversalCost ( const TemplateClass& Obj,
const FSearchNode& Param1,
const FSearchNode& Param2
)

  
Public function Static bool

HasExceededCostLimit ( const TemplateClass& Obj,
FVector::FReal Cost
)

  
Public function Const bool

HasReachMaxSearchNodes ( const TQueryFilter& Filter
)

  
Public function Static bool

HasReachMaxSearchNodes ( const TemplateClass& Obj,
uint32 NodeCount
)

  
Public function FORCEINLINE_DEBUGGABLE bool

ProcessSingleNode ( const FSearchNode& EndNode,
const bool bIsBound,
const TQueryFilter& Filter,
int32& OutBestNodeIndex,
float& OutBestNodeCost
)

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

ProcessSingleNode ( const FSearchNode& EndNode,
const bool bIsBound,
const TQueryFilter& Filter,
int32& OutBestNodeIndex,
FVector::FReal& OutBestNodeCost
)

 Single run of A* loop: get node from open set and process neighbors returns true if loop should be continued
Public function Static decltype(auto)

SetPathInfo ( TemplateClass& Obj,
const int32 Param1,
const FSearchNode& Param2
)

  
Public function Static decltype(auto)

ShouldIgnoreClosedNodes ( const TemplateClass& Obj
)

  
Public function Static decltype(auto)

ShouldIncludeStartNodeInPath ( const TemplateClass& Obj
)

  

Classes

  Type Name Description
Public struct CQueryGetCostLimit    
Public struct CQueryGetHeuristicCost    
Public struct CQueryGetNeighbour    
Public struct CQueryGetNeighbourCount TGraph optionally implemented wrapper methods.  
Public struct CQueryGetNeighbourCountV2    
Public struct CQueryGetTraversalCost TQueryFilter optionally implemented wrapper methods.  
Public struct CQueryHasExceededCostLimit    
Public struct CQueryHasReachMaxSearchNodes Custom methods implemented over TQueryFilter optionally implemented methods.  
Public struct CQuerySetPathInfo TResultPathInfo optionally implemented wrapper methods.  
Public struct CQueryShouldIgnoreClosedNodes    
Public struct CQueryShouldIncludeStartNodeInPath    
Public struct FNodePool    
Public struct FNodeSorter    
Public struct FOpenList    

Typedefs

Name Description
FGraphNodeRef  
FIndexArray  
FNodeArray  
FNodeMap  
FRangeChecklessSetAllocator  
FSearchNode  

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page