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
	If heuristic optimization should be used and how to place the pivot points. More...
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

HeuristicOptimizationMode mode

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

See also

heuristic-opt

Game AI Pro - Pathfinding Architecture Optimizations by Steve Rabin and Nathan R. Sturtevant

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:

• /Users/arong/Unity/a-pathfinding-project/Assets/AstarPathfindingProject/Generators/Utilities/EuclideanEmbedding.cs