Module |
|
Header |
/Engine/Source/Runtime/AIModule/Public/GraphAStar.h |
Include |
#include "GraphAStar.h" |
template<typename TGraph, typename Policy, typename TSearchNode>
struct FGraphAStar
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
Name | Description | ||
---|---|---|---|
|
const TGraph & |
Graph |
|
|
NodePool |
||
|
NodeSorter |
||
|
OpenList |
Name | Description | |
---|---|---|
|
FGraphAStar ( |
Name | Description | ||
---|---|---|---|
|
EGraphAStarR... |
FindPath ( |
Performs the actual search. |
|
EGraphAStarR... |
FloodFrom ( |
Floods node pool until running out of either free nodes or open set |
|
ProcessSingleNode ( |
Single run of A* loop: get node from open set and process neighbors returns true if loop should be continued |
Name |
Description |
|
---|---|---|
|
FNodePool |
|
|
FNodeSorter |
|
|
FOpenList |
Name |
Description |
---|---|
FGraphNodeRef |
|
FSearchNode |