QTree.MonoGame.Common 1.0.3

QTree

A simple quadtree implementation.

Installation

Raw:
dotnet add package QTree --version 1.0.5
MonoGame .net 8:
dotnet add package QTree.MonoGame.Common --version 1.0.2

Example usage

Quad tree

// create the quadtree:

// this tree is faster but constrained to the initial bounds
var quadTree = new QuadTree<string>(x: 0, y: 0, width: 2000, height: 2000);

// this tree is a bit slower but has no constrictions in space
var dynamicTree = new DynamicQuadTree<string>();

// add some objects to the tree
for(var x = 0; x < 2000; x += 20)
{
    for(var y = 0; y < 2000; y += 20)
    {
        quadTree.Add(x, y, 10, 10, "whatevs");
        dynamicTree.Add(x, y, 10, 10, "whatevs");
    }
}

// find some objects
var objectsInArea = quadTree.FindNode(500, 500, 50, 50);
var otherObjectsInSameArea = dynamicTree.FindNode(500, 500, 50, 50);

// remove an object
quadTree.Remove(objectsInArea.First());
dynamicTree.Remove(objectsInArea.First());

// clear the tree
quadTree.Clear();
dynamicTree.Clear();

Ray casting

MonoGame

Small disclaimer: In the monogame framework there is already a class called Ray which is used with Vector3, and BoundingBox. To avoid collision, the Ray class in this project is called QTreeRay inside the QTree.MonoGame namespace

// create a ray with a start point and direction
var searchStartPosition = new Vector2(100, 100);
var direction = new Vector2(.5f, .5f);
var ray = new QTreeRay(searchStartPosition, direction);

// if you want to use an angle in radians instead you can do
var rayFromRadians = new QTreeRay(searchStartPosition, 3.14f);

// and if you want the angle to be between two positions you can do
var otherPosition = new Vector2(200, 200);
var rayBetweenPositions = QTreeRay.BetweenVectors(searchStartPosition, otherPosition);

// ray cast all in specific range
var distanceResults = qtree.RayCast(ray).Where(result => Vector2.Distance(ray.Start, result.Hit) < YOUR_MAX_DISTANCE);

// get first collision from start point
var firstHit = qtree.RayCast(ray).OrderBy(result => Vector2.Distance(ray.Start, result.Hit)).FirstOrDefault()?.Object;

// get everything in collision with the ray
var all = qtree.RayCast(ray).ToList();

Not monogame

// create a ray with a start point and direction
var searchStartPosition = new Point2D(100, 100);
var direction = new PointF2D(.5f, .5f);
var ray = new Ray(searchStartPostion, direction);

// if you want to use an angle in radians instead you can do
var rayFromRadians = new Ray(searchStartPosition, 3.14f);

// and if you want the angle to be between two positions you can do
var otherPosition = new Point2D(200, 200);
var rayBetweenPositions = Ray.BetweenVectors(searchStartPosition, otherPosition);

// ray cast all in specific range
var distanceResults = qtree.RayCast(ray).Where(result => Vector2.Distance(ray.Start, result.Hit) < YOUR_MAX_DISTANCE);

// get first collision from start point
var firstHit = qtree.RayCast(ray).OrderBy(result => Vector2.Distance(ray.Start, result.Hit)).FirstOrDefault()?.Object;

// get everything in collision with the ray
var all = qtree.RayCast(ray).ToList();

Benchmarks

Adding a point

Benchmark is located here

Finding a point

Benchmark is located here

Ray cast

Benchmark is located here

Difference from previous version

Add point
Find point
Ray cast

Find point speed has gone down significantly from the previous version. Add point seems to be a bit faster, and ray cast has gotten slower. Not sure why that is since it is so dependent on the find function.