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

Implements heuristic optimizations. More...

## Detailed Description

Implements heuristic optimizations.

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

## 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

## ◆ 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.

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.

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.

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

## ◆ RecalculateCosts()

 void RecalculateCosts ( )

## ◆ RecalculatePivots()

 void RecalculatePivots ( )

## ◆ 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

## ◆ 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