A* Pathfinding Project  4.1.20
The A* Pathfinding Project for Unity 3D
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Events Macros Groups Pages
Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | List of all members
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.
 
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.
 
void EnsureCapacity (int index)
 
void GetClosestWalkableNodesToChildrenRecursively (Transform tr, List< GraphNode > nodes)
 
uint GetRandom ()
 Simple linear congruential generator.
 
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.
 

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.
 
System.Object lockObj = new object ()
 
int maxNodeIndex
 
int pivotCount
 
GraphNode[] pivots
 
const uint ra = 12820163
 
const uint rc = 1140671485
 
uint rval
 

Member Function Documentation

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
void EnsureCapacity ( int  index)
private
void GetClosestWalkableNodesToChildrenRecursively ( Transform  tr,
List< GraphNode >  nodes 
)
private
uint GetHeuristic ( int  nodeIndex1,
int  nodeIndex2 
)
uint GetRandom ( )
private

Simple linear congruential generator.

See Also
http://en.wikipedia.org/wiki/Linear_congruential_generator
void OnDrawGizmos ( )
GraphNode PickAnyWalkableNode ( )
private
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
void RecalculateCosts ( )
void RecalculatePivots ( )

Member Data Documentation

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]

bool dirty
System.Object lockObj = new object ()
private
int maxNodeIndex
private
HeuristicOptimizationMode mode
int pivotCount
private
Transform pivotPointRoot

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

GraphNode [] pivots
private
const uint ra = 12820163
private
const uint rc = 1140671485
private
uint rval
private
int seed
int spreadOutCount = 1
The documentation for this class was generated from the following file: