QuadTree-Unity

QuadTree<Point> quadTree = new QuadTree<Point>(new Rectangle(0, 0, 100), maxNodesBeforeSubdividing);

A Generic Quad-Tree data-structure implemented in Unity3D.

Watch video to see an example of how it works : VIDEO LINK

This QuadTree accepts nodes which has inherited interfaces, IHasRect and IHasID.

Insert Method 🔑

You can Insert a node or objects which has inherited IHasRect and IHasID interfaces in the QuadTree and you can define how many nodes can a leaf accept before subdividing.

 float positionX = 5;
 float positionY = 5;
 float radius = 1;
 
 // Inserts a point in the QuadTree
 
 Point point = new Point(new Rectangle(positionX, positionY, radius));
 quadTree.Insert(point);

Here is an representational example of 3 nodes before subdividing.

Query Method 🔍

This Query Method returns a List of ID's of the points inside the searching area. You can Query an area of with an instance of Rectangle which has an X and Y and a Radius to search the points inside the QuadTree.

List<int> pointIDs = quadTree.Query(new Rectangle(mousePosition.x, mousePosition.y, searchingRadius));

ClearAllNodes ❌

This Method sets root = false to and numberOfNodesInserted = 0 which makes the Quadtree's array of nodes to be overwritten next time when inserting, I don't like to set the array of node to null because next time when inserting we should make a new instance of the array and it reduces performance, so what happens is next time when reusing the inserted nodes overwrites on the array nodes.

quadTree.ClearAllNodes();

Any suggestion or advice are welcome and would be appriciated.🙏

Some other good resources to take a look at. ✅

Microsoft Reference
Stackoverflow explanation
Stackoverflow explanation 2