A* Pathfinding Project  4.1.2
The A* Pathfinding Project for Unity 3D
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Events Macros Groups Pages
PointKDTree Class Reference

Represents a collection of GraphNodes. More...

Detailed Description

Represents a collection of GraphNodes.

It allows for fast lookups of the closest node to a point.

See Also
https://en.wikipedia.org/wiki/K-d_tree

Classes

class  CompareX
 
class  CompareY
 
class  CompareZ
 
struct  Node
 

Public Member Functions

 PointKDTree ()
 
void Add (GraphNode node)
 Add the node to the tree.
 
void GetInRange (Int3 point, long sqrRadius, List< GraphNode > buffer)
 Add all nodes within a squared distance of the point to the buffer.
 
GraphNode GetNearest (Int3 point, NNConstraint constraint)
 Closest node to the point which satisfies the constraint.
 
void Rebuild (GraphNode[] nodes, int start, int end)
 Rebuild the tree starting with all nodes in the array between index start (inclusive) and end (exclusive)
 

Public Attributes

const int LeafArraySize = LeafSize*2 + 1
 
const int LeafSize = 10
 

Private Member Functions

void Add (GraphNode point, int index, int depth=0)
 
void Build (int index, List< GraphNode > nodes, int start, int end)
 
void CollectAndClear (int index, List< GraphNode > buffer)
 
void EnsureSize (int index)
 
void GetInRangeInternal (int index, Int3 point, long sqrRadius, List< GraphNode > buffer)
 
void GetNearestInternal (int index, Int3 point, NNConstraint constraint, ref GraphNode best, ref long bestSqrDist)
 
GraphNode[] GetOrCreateList ()
 
void Rebalance (int index)
 
int Size (int index)
 

Static Private Member Functions

static int MaxAllowedSize (int numNodes, int depth)
 

Private Attributes

readonly Stack< GraphNode[]> arrayCache = new Stack<GraphNode[]>()
 
readonly List< GraphNodelargeList = new List<GraphNode>()
 
int numNodes = 0
 
Node[] tree = new Node[16]
 

Static Private Attributes

static readonly IComparer
< GraphNode >[] 
comparers = new IComparer<GraphNode>[] { new CompareX(), new CompareY(), new CompareZ() }
 

Constructor & Destructor Documentation

Member Function Documentation

void Add ( GraphNode  node)

Add the node to the tree.

void Add ( GraphNode  point,
int  index,
int  depth = 0 
)
private
void Build ( int  index,
List< GraphNode nodes,
int  start,
int  end 
)
private
void CollectAndClear ( int  index,
List< GraphNode buffer 
)
private
void EnsureSize ( int  index)
private
void GetInRange ( Int3  point,
long  sqrRadius,
List< GraphNode buffer 
)

Add all nodes within a squared distance of the point to the buffer.

Parameters
pointNodes around this point will be added to the buffer.
sqrRadiussquared maximum distance in Int3 space. If you are converting from world space you will need to multiply by Int3.Precision:
var sqrRadius = (worldSpaceRadius * Int3.Precision) * (worldSpaceRadius * Int3.Precision);
bufferAll nodes will be added to this list.
void GetInRangeInternal ( int  index,
Int3  point,
long  sqrRadius,
List< GraphNode buffer 
)
private
GraphNode GetNearest ( Int3  point,
NNConstraint  constraint 
)

Closest node to the point which satisfies the constraint.

void GetNearestInternal ( int  index,
Int3  point,
NNConstraint  constraint,
ref GraphNode  best,
ref long  bestSqrDist 
)
private
GraphNode [] GetOrCreateList ( )
private
static int MaxAllowedSize ( int  numNodes,
int  depth 
)
staticprivate
void Rebalance ( int  index)
private
void Rebuild ( GraphNode[]  nodes,
int  start,
int  end 
)

Rebuild the tree starting with all nodes in the array between index start (inclusive) and end (exclusive)

int Size ( int  index)
private

Member Data Documentation

readonly Stack<GraphNode[]> arrayCache = new Stack<GraphNode[]>()
private
readonly IComparer<GraphNode> [] comparers = new IComparer<GraphNode>[] { new CompareX(), new CompareY(), new CompareZ() }
staticprivate
readonly List<GraphNode> largeList = new List<GraphNode>()
private
const int LeafArraySize = LeafSize*2 + 1
const int LeafSize = 10
int numNodes = 0
private
Node [] tree = new Node[16]
private

The documentation for this class was generated from the following file: