A* Pathfinding Project  4.1.22
The A* Pathfinding Project for Unity 3D
EuclideanEmbedding Class Reference

Implements heuristic optimizations. More...

Detailed Description

Implements heuristic optimizations.

See also
heuristic-opt
Game AI Pro - Pathfinding Architecture Optimizations by Steve Rabin and Nathan R. Sturtevant

A* Pro Feature:
This is an A* Pathfinding Project Pro feature only. This function/class/variable might not exist in the Free version of the A* Pathfinding Project or the functionality might be limited
The Pro version can be bought here

Public Member Functions

uint GetHeuristic (int nodeIndex1, int nodeIndex2)
 
void OnDrawGizmos ()
 
void RecalculateCosts ()
 
void RecalculatePivots ()
 

Public Attributes

bool dirty
 
HeuristicOptimizationMode mode
 
Transform pivotPointRoot
 All children of this transform will be used as pivot points. More...
 
int seed
 
int spreadOutCount = 1
 

Private Member Functions

void ApplyGridGraphEndpointSpecialCase ()
 Special case necessary for paths to unwalkable nodes right next to walkable nodes to be able to use good heuristics. More...
 
void EnsureCapacity (int index)
 
void GetClosestWalkableNodesToChildrenRecursively (Transform tr, List< GraphNode > nodes)
 
uint GetRandom ()
 Simple linear congruential generator. More...
 
GraphNode PickAnyWalkableNode ()
 
void PickNRandomNodes (int count, List< GraphNode > buffer)
 Pick N random walkable nodes from all nodes in all graphs and add them to the buffer. More...
 

Private Attributes

uint [] costs = new uint[8]
 Costs laid out as n*[int],n*[int],n*[int] where n is the number of pivot points. More...
 
System.Object lockObj = new object ()
 
int maxNodeIndex
 
int pivotCount
 
GraphNode [] pivots
 
const uint ra = 12820163
 
const uint rc = 1140671485
 
uint rval
 

Member Function Documentation

◆ ApplyGridGraphEndpointSpecialCase()

void ApplyGridGraphEndpointSpecialCase ( )
private

Special case necessary for paths to unwalkable nodes right next to walkable nodes to be able to use good heuristics.

This will find all unwalkable nodes in all grid graphs with walkable nodes as neighbours and set the cost to reach them from each of the pivots as the minimum of the cost to reach the neighbours of each node.

See also
ABPath.EndPointGridGraphSpecialCase

◆ EnsureCapacity()

void EnsureCapacity ( int  index)
private

◆ GetClosestWalkableNodesToChildrenRecursively()

void GetClosestWalkableNodesToChildrenRecursively ( Transform  tr,
List< GraphNode nodes 
)
private

◆ GetHeuristic()

uint GetHeuristic ( int  nodeIndex1,
int  nodeIndex2 
)

◆ GetRandom()

uint GetRandom ( )
private

Simple linear congruential generator.

See also
http://en.wikipedia.org/wiki/Linear_congruential_generator

◆ OnDrawGizmos()

void OnDrawGizmos ( )

◆ PickAnyWalkableNode()

GraphNode PickAnyWalkableNode ( )
private

◆ PickNRandomNodes()

void PickNRandomNodes ( int  count,
List< GraphNode buffer 
)
private

Pick N random walkable nodes from all nodes in all graphs and add them to the buffer.

Here we select N random nodes from a stream of nodes. Probability of choosing the first N nodes is 1 Probability of choosing node i is min(N/i,1) A selected node will replace a random node of the previously selected ones.

See also
https://en.wikipedia.org/wiki/Reservoir_sampling

◆ RecalculateCosts()

void RecalculateCosts ( )

◆ RecalculatePivots()

void RecalculatePivots ( )

Member Data Documentation

◆ costs

uint [] costs = new uint[8]
private

Costs laid out as n*[int],n*[int],n*[int] where n is the number of pivot points.

Each node has n integers which is the cost from that node to the pivot node. They are at around the same place in the array for simplicity and for cache locality.

cost(nodeIndex, pivotIndex) = costs[nodeIndex*pivotCount+pivotIndex]

◆ dirty

bool dirty

◆ lockObj

System.Object lockObj = new object ()
private

◆ maxNodeIndex

int maxNodeIndex
private

◆ mode

◆ pivotCount

int pivotCount
private

◆ pivotPointRoot

Transform pivotPointRoot

All children of this transform will be used as pivot points.

◆ pivots

GraphNode [] pivots
private

◆ ra

const uint ra = 12820163
private

◆ rc

const uint rc = 1140671485
private

◆ rval

uint rval
private

◆ seed

int seed

◆ spreadOutCount

int spreadOutCount = 1

The documentation for this class was generated from the following file: