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

Axis Aligned Bounding Box Tree. More...

Detailed Description

Axis Aligned Bounding Box Tree.

Holds a bounding box tree of triangles.
Performance: Insertion - Practically O(1) - About 0.003 ms

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

Classes

struct  BBTreeBox
 

Public Member Functions

 BBTree (INavmeshHolder graph)
 
void Clear ()
 Clear the tree.
 
void Insert (MeshNode node)
 Inserts a mesh node in the tree.
 
void OnDrawGizmos ()
 
NNInfo Query (Vector3 p, NNConstraint constraint)
 
NNInfo QueryCircle (Vector3 p, float radius, NNConstraint constraint)
 Queries the tree for the best node, searching within a circle around p with the specified radius.
 
NNInfo QueryClosest (Vector3 p, NNConstraint constraint, out float distance)
 Queries the tree for the closest node to p constrained by the NNConstraint.
 
NNInfo QueryClosest (Vector3 p, NNConstraint constraint, ref float distance, NNInfo previous)
 Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.
 
NNInfo QueryClosestXZ (Vector3 p, NNConstraint constraint, ref float distance, NNInfo previous)
 Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.
 
MeshNode QueryInside (Vector3 p, NNConstraint constraint)
 

Public Attributes

INavmeshHolder graph
 

Properties

Rect Size [get]
 

Private Member Functions

void EnsureCapacity (int c)
 
int GetBox (MeshNode node)
 
void OnDrawGizmos (int boxi, int depth)
 
void SearchBox (int boxi, Vector3 p, NNConstraint constraint, ref NNInfo nnInfo)
 
void SearchBoxCircle (int boxi, Vector3 p, float radius, NNConstraint constraint, ref NNInfo nnInfo)
 
void SearchBoxClosest (int boxi, Vector3 p, ref float closestDist, NNConstraint constraint, ref NNInfo nnInfo)
 
void SearchBoxClosestXZ (int boxi, Vector3 p, ref float closestDist, NNConstraint constraint, ref NNInfo nnInfo)
 
MeshNode SearchBoxInside (int boxi, Vector3 p, NNConstraint constraint)
 

Static Private Member Functions

static Rect ExpandToContain (Rect r, Rect r2)
 Returns a new rect which contains both r and r2.
 
static float ExpansionRequired (Rect r, Rect r2)
 Returns the difference in area between r and r expanded to contain r2.
 
static bool NodeIntersectsCircle (MeshNode node, Vector3 p, float radius)
 
static float RectArea (Rect r)
 Returns the area of a rect.
 
static bool RectContains (Rect r, Vector3 p)
 Returns if a rect contains the 3D point in XZ space.
 
static bool RectIntersectsCircle (Rect r, Vector3 p, float radius)
 Returns true if p is within radius from r.
 

Private Attributes

BBTreeBox[] arr = new BBTreeBox[6]
 Holds an Axis Aligned Bounding Box Tree used for faster node lookups.
 
int count = 0
 

Constructor & Destructor Documentation

BBTree ( INavmeshHolder  graph)

Member Function Documentation

void Clear ( )

Clear the tree.

Note that references to old nodes will still be intact so the GC cannot immediately collect them.

void EnsureCapacity ( int  c)
private
static Rect ExpandToContain ( Rect  r,
Rect  r2 
)
staticprivate

Returns a new rect which contains both r and r2.

static float ExpansionRequired ( Rect  r,
Rect  r2 
)
staticprivate

Returns the difference in area between r and r expanded to contain r2.

int GetBox ( MeshNode  node)
private
void Insert ( MeshNode  node)

Inserts a mesh node in the tree.

static bool NodeIntersectsCircle ( MeshNode  node,
Vector3  p,
float  radius 
)
staticprivate
void OnDrawGizmos ( )
void OnDrawGizmos ( int  boxi,
int  depth 
)
private
NNInfo Query ( Vector3  p,
NNConstraint  constraint 
)
NNInfo QueryCircle ( Vector3  p,
float  radius,
NNConstraint  constraint 
)

Queries the tree for the best node, searching within a circle around p with the specified radius.

Will fill in both the constrained node and the not constrained node in the NNInfo.

See Also
QueryClosest
NNInfo QueryClosest ( Vector3  p,
NNConstraint  constraint,
out float  distance 
)

Queries the tree for the closest node to p constrained by the NNConstraint.

Note that this function will, unlike QueryCircle, only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None

See Also
QueryCircle
NNInfo QueryClosest ( Vector3  p,
NNConstraint  constraint,
ref float  distance,
NNInfo  previous 
)

Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.

Note that this function will, unlike QueryCircle, only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None

This search will start from the previous NNInfo and improve it if possible. Even if the search fails on this call, the solution will never be worse than previous.

Parameters
distanceThe best distance for the previous solution. Will be updated with the best distance after this search. Will be positive infinity if no node could be found. Set to positive infinity if there was no previous solution.
See Also
QueryCircle
NNInfo QueryClosestXZ ( Vector3  p,
NNConstraint  constraint,
ref float  distance,
NNInfo  previous 
)

Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.

Note that this function will, unlike QueryCircle, only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None

This search will start from the previous NNInfo and improve it if possible. Even if the search fails on this call, the solution will never be worse than previous.

This method will completely ignore any Y-axis differences in positions.

Parameters
distanceThe best distance for the previous solution. Will be updated with the best distance after this search. Will be positive infinity if no node could be found. Set to positive infinity if there was no previous solution.
See Also
QueryCircle
MeshNode QueryInside ( Vector3  p,
NNConstraint  constraint 
)
static float RectArea ( Rect  r)
staticprivate

Returns the area of a rect.

static bool RectContains ( Rect  r,
Vector3  p 
)
staticprivate

Returns if a rect contains the 3D point in XZ space.

static bool RectIntersectsCircle ( Rect  r,
Vector3  p,
float  radius 
)
staticprivate

Returns true if p is within radius from r.

Correctly handles cases where radius is positive infinity.

void SearchBox ( int  boxi,
Vector3  p,
NNConstraint  constraint,
ref NNInfo  nnInfo 
)
private
void SearchBoxCircle ( int  boxi,
Vector3  p,
float  radius,
NNConstraint  constraint,
ref NNInfo  nnInfo 
)
private
void SearchBoxClosest ( int  boxi,
Vector3  p,
ref float  closestDist,
NNConstraint  constraint,
ref NNInfo  nnInfo 
)
private
void SearchBoxClosestXZ ( int  boxi,
Vector3  p,
ref float  closestDist,
NNConstraint  constraint,
ref NNInfo  nnInfo 
)
private
MeshNode SearchBoxInside ( int  boxi,
Vector3  p,
NNConstraint  constraint 
)
private

Member Data Documentation

BBTreeBox [] arr = new BBTreeBox[6]
private

Holds an Axis Aligned Bounding Box Tree used for faster node lookups.

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
int count = 0
private

Property Documentation

Rect Size
get

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