A* Pathfinding Project  4.1.19
The A* Pathfinding Project for Unity 3D
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. More...
 
void GetInRange (Int3 point, long sqrRadius, List< GraphNode > buffer)
 Add all nodes within a squared distance of the point to the buffer. More...
 
GraphNode GetNearest (Int3 point, NNConstraint constraint)
 Closest node to the point which satisfies the constraint. More...
 
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) More...
 

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

◆ PointKDTree()

Member Function Documentation

◆ Add() [1/2]

void Add ( GraphNode  node)

Add the node to the tree.

◆ Add() [2/2]

void Add ( GraphNode  point,
int  index,
int  depth = 0 
)
private

◆ Build()

void Build ( int  index,
List< GraphNode nodes,
int  start,
int  end 
)
private

◆ CollectAndClear()

void CollectAndClear ( int  index,
List< GraphNode buffer 
)
private

◆ EnsureSize()

void EnsureSize ( int  index)
private

◆ GetInRange()

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.

◆ GetInRangeInternal()

void GetInRangeInternal ( int  index,
Int3  point,
long  sqrRadius,
List< GraphNode buffer 
)
private

◆ GetNearest()

GraphNode GetNearest ( Int3  point,
NNConstraint  constraint 
)

Closest node to the point which satisfies the constraint.

◆ GetNearestInternal()

void GetNearestInternal ( int  index,
Int3  point,
NNConstraint  constraint,
ref GraphNode  best,
ref long  bestSqrDist 
)
private

◆ GetOrCreateList()

GraphNode [] GetOrCreateList ( )
private

◆ MaxAllowedSize()

static int MaxAllowedSize ( int  numNodes,
int  depth 
)
staticprivate

◆ Rebalance()

void Rebalance ( int  index)
private

◆ Rebuild()

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)

◆ Size()

int Size ( int  index)
private

Member Data Documentation

◆ arrayCache

readonly Stack<GraphNode[]> arrayCache = new Stack<GraphNode[]>()
private

◆ comparers

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

◆ largeList

readonly List<GraphNode> largeList = new List<GraphNode>()
private

◆ LeafArraySize

const int LeafArraySize = LeafSize*2 + 1

◆ LeafSize

const int LeafSize = 10

◆ numNodes

int numNodes = 0
private

◆ tree

Node [] tree = new Node[16]
private

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