FGraphAStar

Generic graph A* implementation

Windows
MacOS
Linux

References

Module

AIModule

Header

/Engine/Source/Runtime/AIModule/Public/GraphAStar.h

Include

#include "GraphAStar.h"

Syntax

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

Remarks

Generic graph A* implementation

TGraph holds graph representation. Needs to implement functions: int32 GetNeighbourCount(FNodeRef NodeRef) const; returns number of neighbours that the graph node identified with NodeRef has bool IsValidRef(FNodeRef NodeRef) const; returns whether given node identyfication is correct FNodeRef GetNeighbour(const FNodeRef 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 FNodeRef StartNodeRef, const FNodeRef EndNodeRef) const; estimate of cost from StartNodeRef to EndNodeRef float GetTraversalCost(const FNodeRef StartNodeRef, const FNodeRef EndNodeRef) const; real cost of traveling from StartNodeRef directly to EndNodeRef bool IsTraversalAllowed(const FNodeRef NodeA, const FNodeRef NodeB) const; whether traversing given edge is allowed bool WantsPartialSolution() const; - whether to accept solutions that do not reach the goal

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 FGraphNodeRef StartNodeRef,
    const FGraphNodeRef EndNodeRef,
    const TQueryFilter& Filter,
    TArray < FGraphNodeRef >& OutPath
)

Performs the actual search.

Public function

EGraphAStarR ...

 

FloodFrom

(
    const FGraphNodeRef StartNodeRef,
    const TQueryFilter& Filter
)

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

Public function

bool

 

ProcessSingleNode

(
    const FGraphNodeRef EndNodeRef,
    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

Classes

Name

Description

Public struct

FNodePool

Public struct

FNodeSorter

Public struct

FOpenList

Typedefs

Name

Description

FGraphNodeRef

FSearchNode

Select Skin
Light
Dark

Welcome to the new Unreal Engine 4 Documentation site!

We're working on lots of new features including a feedback system so you can tell us how we are doing. It's not quite ready for use in the wild yet, so head over to the Documentation Feedback forum to tell us about this page or call out any issues you are encountering in the meantime.

We'll be sure to let you know when the new system is up and running.

Post Feedback