FGraphAStar

Generic graph A* implementation

Choose your operating system:

Windows

macOS

Linux

Inheritance Hierarchy

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: float GetHeuristicScale() const; - used as GetHeuristicCost's multiplier float GetHeuristicCost(const FSearchNode& StartNode, const FSearchNode& EndNode) const; - estimate of cost from StartNode to EndNode from a search node float 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 float GetHeuristicCost(const FNodeRef StartNodeRef, const FNodeRef EndNodeRef) const; - estimate of cost from StartNode to EndNode from a NodeRef float 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 float GetCostLimit() const - whether to limit the search to a maximum cost

Variables

Name Description

Public variable

const TGraph &

 

Graph

Public variable

FNodePool

 

NodePool

Public variable

FNodeSorter

 

NodeSorter

Public variable

FOpenList

 

OpenList

Constructors

Name Description

Public function

FGraphAStar

(
    const TGraph& InGraph
)

Functions

Name Description

Public function

EGraphAStarR...

 

FindPath

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

Performs the actual search.

Public function

EGraphAStarR...

 

FloodFrom

(
    const FSearchNode& StartNode,
    const TQueryFilter& Filter
)

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

Public function Static

TEnableIf< T...

 

GetCostLimit

(
    const TemplateClass& Obj
)

Public function Static

TEnableIf<&#...

 

GetCostLimit

(
    const TemplateClass& Obj
)

Public function Static

TEnableIf< T...

 

GetHeuristicCost

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

Public function Static

TEnableIf<&#...

 

GetHeuristicCost

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

Public function Static

TEnableIf< T...

 

GetNeighbour

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

Public function Static

TEnableIf<&#...

 

GetNeighbour

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

Public function Static

TEnableIf< T...

 

GetNeighbourCount

(
    const TemplateClass& Obj,
    const FGraphNodeRef Param1
)

Public function Static

TEnableIf<&#...

 

GetNeighbourCount

(
    const TemplateClass& Obj,
    const FGraphNodeRef Param1
)

Public function Static

TEnableIf< T...

 

GetNeighbourCountV2

(
    const TemplateClass& Obj,
    const FSearchNode& Param1
)

Public function Static

TEnableIf<&#...

 

GetNeighbourCountV2

(
    const TemplateClass& Obj,
    const FSearchNode& Param1
)

Public function Static

TEnableIf< T...

 

GetTraversalCost

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

Public function Static

TEnableIf<&#...

 

GetTraversalCost

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

Public function Static

TEnableIf< T...

 

HasExceededCostLimit

(
    const TemplateClass& Obj,
    float Cost
)

Public function Static

TEnableIf<&#...

 

HasExceededCostLimit

(
    const TemplateClass& Obj,
    float Cost
)

Public function Const

bool

 

HasReachMaxSearchNodes

(
    const TQueryFilter& Filter
)

Public function Static

TEnableIf< T...

 

HasReachMaxSearchNodes

(
    const TemplateClass& Obj,
    uint32 NodeCount
)

Public function Static

TEnableIf<&#...

 

HasReachMaxSearchNodes

(
    const TemplateClass& Obj,
    uint32 NodeCount
)

Public function

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 Static

TEnableIf< T...

 

SetPathInfo

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

Public function Static

TEnableIf<&#...

 

SetPathInfo

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

Public function Static

TEnableIf< T...

 

ShouldIgnoreClosedNodes

(
    const TemplateClass& Obj
)

Public function Static

TEnableIf<&#...

 

ShouldIgnoreClosedNodes

(
    const TemplateClass& Obj
)

Public function Static

TEnableIf< T...

 

ShouldIncludeStartNodeInPath

(
    const TemplateClass& Obj
)

Public function Static

TEnableIf<&#...

 

ShouldIncludeStartNodeInPath

(
    const TemplateClass& Obj
)

Classes

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