A* Pathfinding Project
4.1.7
The A* Pathfinding Project for Unity 3D
|
Axis Aligned Bounding Box Tree. More...
Axis Aligned Bounding Box Tree.
Holds a bounding box tree of triangles.
Classes | |
struct | BBTreeBox |
Public Member Functions | |
void | Clear () |
Clear the tree. More... | |
void | OnDrawGizmos () |
NNInfoInternal | QueryClosest (Vector3 p, NNConstraint constraint, out float distance) |
Queries the tree for the closest node to p constrained by the NNConstraint. More... | |
NNInfoInternal | QueryClosest (Vector3 p, NNConstraint constraint, ref float distance, NNInfoInternal previous) |
Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution. More... | |
NNInfoInternal | QueryClosestXZ (Vector3 p, NNConstraint constraint, ref float distance, NNInfoInternal previous) |
Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution. More... | |
TriangleMeshNode | QueryInside (Vector3 p, NNConstraint constraint) |
Searches for a node which contains the specified point. More... | |
void | RebuildFrom (TriangleMeshNode[] nodes) |
Rebuilds the tree using the specified nodes. More... | |
Properties | |
Rect | Size [get] |
Private Member Functions | |
void | EnsureCapacity (int c) |
void | EnsureNodeCapacity (int c) |
int | GetBox (IntRect rect) |
void | GetOrderedChildren (ref int first, ref int second, out float firstDist, out float secondDist, Vector3 p) |
Orders the box indices first and second by the approximate distance to the point p. More... | |
void | OnDrawGizmos (int boxi, int depth) |
void IAstarPooledObject. | OnEnterPool () |
int | RebuildFromInternal (TriangleMeshNode[] nodes, int[] permutation, IntRect[] nodeBounds, int from, int to, bool odd) |
void | SearchBoxClosest (int boxi, Vector3 p, ref float closestSqrDist, NNConstraint constraint, ref NNInfoInternal nnInfo) |
void | SearchBoxClosestXZ (int boxi, Vector3 p, ref float closestSqrDist, NNConstraint constraint, ref NNInfoInternal nnInfo) |
TriangleMeshNode | SearchBoxInside (int boxi, Vector3 p, NNConstraint constraint) |
Static Private Member Functions | |
static void | DrawDebugNode (TriangleMeshNode node, float yoffset, Color color) |
static void | DrawDebugRect (IntRect rect) |
static IntRect | NodeBounds (int[] permutation, IntRect[] nodeBounds, int from, int to) |
Calculates the bounding box in XZ space of all nodes between from (inclusive) and to (exclusive) More... | |
static bool | NodeIntersectsCircle (TriangleMeshNode node, Vector3 p, float radius) |
static bool | RectIntersectsCircle (IntRect r, Vector3 p, float radius) |
Returns true if p is within radius from r. More... | |
static int | SplitByX (TriangleMeshNode[] nodes, int[] permutation, int from, int to, int divider) |
static int | SplitByZ (TriangleMeshNode[] nodes, int[] permutation, int from, int to, int divider) |
static float | SquaredRectPointDistance (IntRect r, Vector3 p) |
Returns distance from p to the rectangle r. More... | |
Private Attributes | |
int | count |
int | leafNodes |
const int | MaximumLeafSize = 4 |
TriangleMeshNode [] | nodeLookup = null |
BBTreeBox [] | tree = null |
Holds all tree nodes. More... | |
void Clear | ( | ) |
Clear the tree.
Note that references to old nodes will still be intact so the GC cannot immediately collect them.
|
staticprivate |
|
staticprivate |
|
private |
|
private |
|
private |
|
private |
Orders the box indices first and second by the approximate distance to the point p.
|
staticprivate |
Calculates the bounding box in XZ space of all nodes between from (inclusive) and to (exclusive)
|
staticprivate |
void OnDrawGizmos | ( | ) |
|
private |
|
private |
Implements IAstarPooledObject.
NNInfoInternal 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 only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None
NNInfoInternal QueryClosest | ( | Vector3 | p, |
NNConstraint | constraint, | ||
ref float | distance, | ||
NNInfoInternal | 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 only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None
p | Point to search around |
constraint | Optionally set to constrain which nodes to return |
distance | The 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. |
previous | 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. |
NNInfoInternal QueryClosestXZ | ( | Vector3 | p, |
NNConstraint | constraint, | ||
ref float | distance, | ||
NNInfoInternal | 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 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 method will completely ignore any Y-axis differences in positions.
p | Point to search around |
constraint | Optionally set to constrain which nodes to return |
distance | The 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. |
previous | 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. Note that the distance parameter need to be configured with the distance for the previous result otherwise it may get overwritten even though it was actually closer. |
TriangleMeshNode QueryInside | ( | Vector3 | p, |
NNConstraint | constraint | ||
) |
Searches for a node which contains the specified point.
If there are multiple nodes that contain the point any one of them may be returned.
void RebuildFrom | ( | TriangleMeshNode [] | nodes | ) |
Rebuilds the tree using the specified nodes.
|
private |
|
staticprivate |
Returns true if p is within radius from r.
Correctly handles cases where radius is positive infinity.
|
private |
|
private |
|
private |
|
staticprivate |
|
staticprivate |
|
staticprivate |
Returns distance from p to the rectangle r.
|
private |
|
private |
|
private |
|
private |
|
private |
Holds all tree nodes.
|
get |