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
}