A* Pathfinding Project  4.0.7
The A* Pathfinding Project for Unity 3D
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Events Macros Groups Pages
Classes | Public Member Functions | Static Public Attributes | Private Member Functions | Static Private Member Functions | Private Attributes | Static Private Attributes | List of all members
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

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 OnDrawGizmos ()
 Draw gizmos for the tree.
 
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)
 

Static Public Attributes

static 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 Draw (int index, Int3 mn, Int3 mx, int depth=0)
 
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)
 
List< GraphNode > GetOrCreateList ()
 
void Rebalance (int index)
 
int Size (int index)
 

Static Private Member Functions

static int MaxAllowedSize (int numNodes, int depth)
 

Private Attributes

readonly List< GraphNode > largeList = new List<GraphNode>()
 
readonly Stack< List< GraphNode > > listCache = new Stack<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

PointKDTree ( )

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 Draw ( int  index,
Int3  mn,
Int3  mx,
int  depth = 0 
)
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.

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
List<GraphNode> GetOrCreateList ( )
private
static int MaxAllowedSize ( int  numNodes,
int  depth 
)
staticprivate
void OnDrawGizmos ( )

Draw gizmos for the tree.

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 IComparer<GraphNode> [] comparers = new IComparer<GraphNode>[] { new CompareX(), new CompareY(), new CompareZ() }
staticprivate
readonly List<GraphNode> largeList = new List<GraphNode>()
private
int LeafSize = 10
static
readonly Stack<List<GraphNode> > listCache = new Stack<List<GraphNode> >()
private
int numNodes = 0
private
Node [] tree = new Node[16]
private
The documentation for this class was generated from the following file: