Quad Tree not working

I made my first attempt at a functional Quad Tree data structure. I’m planning on adding collission detection later.

The problem is, I’m not even at that part and it’s already stack overflowing like crazy. I tried patching as many leaks as I can, but it still loses its mind as soon as I spawn a mild number of objects. Can anyone spot where it goes wrong?

using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Content;

public class TreeList
{
//This is a tree class for a list of gameobjects, which when updated recursively sorts the objects into lists based on locations. The basic idea is
//that when the amount of objects in its own list gets too large, it sorts the objects in new TreeLists. This goes on until the amount of objects 
//per list is reduced appropriately. It's an attempt at a basic implementation of a Quad Tree structure
#region Fields
private int max;
protected Rectangle boundaries;
protected TreeList parent;
protected IList<GameObject> objects;
protected IList<TreeList> children;
#endregion

#region Constructor
//Constructor, which takes new boundaries, the maximum amount of objects and the parent TreeList as parameters
public TreeList(Rectangle boundaries, int max, TreeList parent = null)
{
    this.max = max;
    this.boundaries = boundaries;
    this.parent = parent;
    children = new List<TreeList>();
    objects = new List<GameObject>();
}
#endregion

#region Methods
//A method for adding new objects to the list. It then immediatly checks if the amount of objects exceeds the maximum.
//If the treelist contains children, it tries to add it to them.
public void NewObject(GameObject obj)
{
    if (children.Count == 0)
    {
        objects.Add(obj);
        obj.Parent = this;
        if (objects.Count > max)
        {
            SplitQuad();
        }
    }
    else
    {
        foreach (TreeList treeList in children)
        {
            if (treeList.Boundaries.Contains(new Point((int)obj.Position.X, (int)obj.Position.Z)))
            {
                treeList.NewObject(obj);
                return;
            }
        }
        objects.Add(obj);
    }
}
//A method for finding every object in this list and all of its children. It's recursive, so each child will also
//return the objects in their children's lists.
public List<GameObject> ObjectsAll()
{
    if(children.Count == 0)
    {
        return objects as List<GameObject>;
    }
    else
    {
        List<GameObject> tempObjects = new List<GameObject>();
        foreach(GameObject obj in objects)
        {
            tempObjects.Add(obj);
        }
        foreach(TreeList child in children)
        {
            foreach(GameObject obj in child.ObjectsAll())
            {
                tempObjects.Add(obj);
            }
        }
        return tempObjects;
    }
}

//A method for removing objects. Caution is advised with implementing this, since unsafe use in a loop or different class
//can royally screw up everything;
public void RemoveObject(GameObject obj)
{
    if(objects.Contains(obj)) objects.Remove(obj);
    else
    {
        foreach(TreeList child in children)
        {
            child.RemoveObject(obj);
        }
    }
}

//This is the method which splits the tree once the objects list grows too big.
public void SplitQuad()
{
    //Here we create four new TreeLists, each with 1/4th of the original boundaries rectangle. We try to make sure they
    //don't overlap, but this probably needs some finetuning.
    children.Add(new TreeList(new Rectangle(boundaries.Location, boundaries.Center - boundaries.Location), max, this));
    children.Add(new TreeList(new Rectangle(boundaries.Right - (boundaries.Width / 2), boundaries.Top, boundaries.Width / 2, boundaries.Height / 2), max, this));
    children.Add(new TreeList(new Rectangle(boundaries.Left, boundaries.Bottom + (boundaries.Height / 2), boundaries.Width / 2, boundaries.Height / 2), max, this));
    children.Add(new TreeList(new Rectangle(boundaries.Center, boundaries.Size), max, this));

    //This part sorts the objects of the parent in each of the children. If the objects overlap boundaries,
    //they instead get added to the parent list of objects. Again, this method probably needs finetuning to
    //check for each object if they're contained within the boundaries or overlap the borders.
    List<GameObject> temp = new List<GameObject>();
    foreach (GameObject obj in objects)
    {
        bool added = false;
        foreach (TreeList child in children)
        {
            if (!added && child.Boundaries.Contains(new Point((int)obj.Position.X, (int)obj.Position.Z)))
            {
                child.NewObject(obj);
                obj.Parent = child;
                added = true;
            }
        }
        if (!added) temp.Add(obj);
    }
    objects = temp;
}

public void Update(GameTime gameTime)
{
    List<GameObject> markedForRemoval = new List<GameObject>();

    foreach(GameObject obj in objects)
    {
        obj.Update(gameTime);
        if (obj.Parent != this)
        {
            markedForRemoval.Add(obj);
        }
    }

    foreach(GameObject obj in markedForRemoval)
    {
        RemoveObject(obj);
        Root().NewObject(obj);
    }
    markedForRemoval.Clear();

    foreach(TreeList child in children)
    {
        child.Update(gameTime);
    }
}

//Property for the boundaries rectangle, which we will later need for each object to find its own TreeList to check collission with.
public Rectangle Boundaries
{
    get { return boundaries; }
}

public TreeList Parent
{
    get { return parent; }
}

public TreeList Root()
{
    if (parent == null) return this;
    else return Parent.Root();
}

//Property for the list of objects contained in this branch. We will later use this for each object to check collission with peer objects
public List<GameObject> Objects
{
    get { return objects as List<GameObject>; }
}

public List<TreeList> Children
{
    get { return children as List<TreeList>; }
}
#endregion

}

This should be easy to debug to find the issue. It would be useful if you said were the overflow is happening.

Without looking at the code in depth, I’ll go ahead and recommend implementing (or finding) a grid-based spatial partitioning method rather than a quad tree. Especially in 2D a grid-based solution will in most cases perform equally well or better than a quad tree. It’s also a lot harder to get things wrong in the implementation and more intuitive than a quad tree because it’s not a recursive data structure.

Thanks for the response! The overflow seems to be coming from different methods in there every time. Sometimes at the constructor(?), sometimes from QuadSplit(), etc.

A grid sounds like an idea, except I’m working in 3D.

Can’t you see a stack trace? That should reveal the issue.

Then your quadtree should be in 3d, but you’re using Rectangles.

In SplitQuad(), I believe the last two splits here are incorrect. Here is a diagram of how I believe they are being split.

It helps when visualizing it to use properties consistently. Here you are using a mix Location, Size, Right, Center, Top, Bottom and Left. And use temporary local variables to make the intent clearer.

int w = boundaries.Width / 2;
int h = boundaries.Height / 2;
int top = boundaries.Top;
int left = boundaries.Left;
children.Add(new TreeList(new Rectangle(top, left, w, h), max, this));
children.Add(new TreeList(new Rectangle(top, left + w, w, h), max, this));
children.Add(new TreeList(new Rectangle(top + h, left, w, h), max, this));
children.Add(new TreeList(new Rectangle(top + h, left + w, w, h), max, this));

Also, have RemoveObject() return true if it removed the object. Otherwise, if the first quad contained the object, you are still calling RemoveObject() on the other three child quads, which will walk down their entire tree when you already know the object is not there.

1 Like

A quadtree is for 2D. An octree is for 3D. As @Jjagg mentioned, you’re using Rectangles and you’re only splitting each cell into four.

Spacial grids can be used in 3d as well.

You can block up 3d space just like 2d space were the 2d space has a width height grid that is a array of buckets the 1d array or list representation of them is as follows.

You can immediately find a objects positions correlating bucket space element index’s in 2d by
x = objectsPosition.X / bucketSize.X;
y = objectsPosition.Y / bucketSize.Y;

The index to the array is found from spacial positions by
arrayIndex = y * width + x;

The maximum x y buckets are
arrayLength = width * height;

registering multiple objects with different id’s or references allows each bucket to have a list of objects per bucket which can actually build you a collision checking table. So that if there are no possible collisions the entire structure need not even be checked at all.

With 3d you have depth so

You can immediately find a objects positions correlating bucket space element indexs by
x = objectsPosition.X / bucketSize.X;
y = objectsPosition.Y / bucketSize.Y;
z = objectsPosition.Z / bucketSize.Z;

the index is defined by
arrayIndex = z * (width * height) + y * width + x;

The maximum buckets are defined by
arrayLength = width * height * depth;

I suppose if we had super computers maybe in hundred years you could see how you could simply expand this to 4 dimensions e.g. time and attempt to predict collisions before they occured using some parallel processing lol.

The trick with spacial grids is there size, it makes the difference to everything about how you structure it. As well just changing it changes the efficiency. For 2d i like them i dunno about 3d i never really did it in 3d, but its the same principle. Just saying it can apply to 3d easily.

Good catch!

Or even better, use its position to find the right tree.

Absolutely. No need for the slow Contains() when you can derive the correct branch from the position.

Maybe take a look here: https://github.com/UnterrainerInformatik/collisiongrid
The explanation should be ok and you can even use it for 3D if you take 2 of the grids like the people here have already explained… Input is welcome. cu

Thanks for all the advice everyone! It seems to be working better now that I fixed SplitQuad(), with KonajuGames’ tip. No stack overflows, even if I spam thousands of objects(bullets in this case) in a span of seconds.

I’ll also look into using an array for a spatial grid! Good idea willmotil, thank you. Is that a form of spatial hashing?

I will take the tips about efficiency into account too. Thanks everyone!

I forgot to mention: @Jjagg, I didn’t know what a stack trace was haha! I found out that SplitQuad() was responsible for all of the stack overflows, which is consistent with what KonajuGames told me. Thank you!

Is that a form of spatial hashing?

Yes.

The primary benefit is they are simple.

They do however shine exceptionally for worlds with a lot of static non moving objects. Like those are no cost to query against once inserted.

The insertion deletion time for moving objects is what is expensive with them. Which is why the spacial size of each bucket effects performance.

Now that i think about it i suppose each bucket could hold its own quad or octree which with large buckets might speed it up even more.