Class EuclideanEmbedding

uint GetHeuristic (

int	nodeIndex1
int	nodeIndex2

)

void OnDrawGizmos ()

void RecalculateCosts ()

void RecalculatePivots ()

bool dirty

HeuristicOptimizationMode mode

If heuristic optimization should be used and how to place the pivot points.

Transform pivotPointRoot

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

int seed

int spreadOutCount = 1

void ApplyGridGraphEndpointSpecialCase ()

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.

uint[] costs = new uint[8]

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]

void EnsureCapacity (

int

index

)

void GetClosestWalkableNodesToChildrenRecursively (

Transform	tr
List<GraphNode>	nodes

)

uint GetRandom ()

Simple linear congruential generator.

System.Object lockObj = new object()

int maxNodeIndex

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.

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.

int pivotCount

GraphNode[] pivots

const uint ra = 12820163

const uint rc = 1140671485

uint rval