A* Pathfinding Project
4.1.7
The A* Pathfinding Project for Unity 3D
|
Implements heuristic optimizations. More...
Implements heuristic optimizations.
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 |
|
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.
|
private |
|
private |
uint GetHeuristic | ( | int | nodeIndex1, |
int | nodeIndex2 | ||
) |
|
private |
Simple linear congruential generator.
void OnDrawGizmos | ( | ) |
|
private |
|
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.
void RecalculateCosts | ( | ) |
void RecalculatePivots | ( | ) |
|
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 |
|
private |
|
private |
|
private |
Transform pivotPointRoot |
All children of this transform will be used as pivot points.
|
private |
|
private |
|
private |
|
private |
int seed |
int spreadOutCount = 1 |