[dartoscoder]

It was early in the summer of 2012 when I started working on my first Quad Tree. I spend 3 months researching and building it only to find that the way I was building it was too slow to work. It is filled with strange hacky methods of getting things to work.
So here I post it for your ridicule (or criticism)... enjoy.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace MassDestructionTop
{
    public class QTreeNode
    {
        QTreeNode[] childNodes = new QTreeNode[4];
        private List<Sprite> sprites = new List<Sprite>();
        private int quad = -1;
        private int generation = 0;
        private QTreeNode parent = null;
        private bool cleanUp = false;
        private Rectangle areaRect;
        private const int maxGen = 4;
        private bool hasChild
        {
            get { return childNodes[0] != null; }
        }

        public QTreeNode(int x, int y, int w, int h, QTreeNode parent = null, int generation = 0, int quad = -1)
        {
            areaRect = new Rectangle(x, y, w, h);

            this.generation = generation;
            this.parent = parent;
            this.quad = quad;
        }

        private void createChildren()
        {
            childNodes[0] = new QTreeNode(0, 0, this.areaRect.Width / 2, this.areaRect.Height / 2, this, this.generation + 1, 1);
            childNodes[1] = new QTreeNode(this.areaRect.Width / 2, 0, this.areaRect.Width, this.areaRect.Height / 2, this, this.generation + 1, 2);
            childNodes[2] = new QTreeNode(this.areaRect.Width / 2, this.areaRect.Height / 2, this.areaRect.Width, this.areaRect.Height, this, this.generation + 1, 3);
            childNodes[3] = new QTreeNode(0, this.areaRect.Height / 2, this.areaRect.Width, this.areaRect.Height, this, this.generation + 1, 4);

            List<Sprite> toDestroy = new List<Sprite>();

            for (int i = 0; i < 3; ++i)
            {
                foreach (Sprite s in sprites)
                {
                    if (Globals.isCollide(s.collisionRect, this.areaRect))
                    {
                        childNodes[i].sprites.Add(s);
                        if (!toDestroy.Contains(s))
                        {
                            toDestroy.Add(s);
                        }
                    }
                }
            }

            foreach (Sprite s in toDestroy)
            {
                this.sprites.Remove(s);
            }
        }

        public void update()
        {
            nodeSpriteCheck();
            if(sprites.Count <= 2)
            {
                detectCollision();
            }
            else if(sprites.Count > 2 && generation < maxGen)
            {
                createChildren();
            }
            else if (generation > maxGen)
            {
                detectCollision();
            }

            if (cleanUp)
            {
                deleteEmptyChildren();
            }

            if (generation > maxGen)
            {
                throw new Exception("Generation Too high");
            }

            updateChildren();

        }

        private void nodeSpriteCheck()
        {
            foreach (Sprite s in Globals.globalAllSprites)
            {
                if (hasChild)
                {
                    childNodes[0].childNodeSpriteCheck(s);
                    childNodes[1].childNodeSpriteCheck(s);
                    childNodes[2].childNodeSpriteCheck(s);
                    childNodes[3].childNodeSpriteCheck(s);
                }
                else if (!this.sprites.Contains(s) && Globals.isCollide(this.areaRect, s.collisionRect))
                {
                    this.sprites.Add(s);
                }
                else if(this.sprites.Contains(s) && !Globals.isCollide(this.areaRect, s.collisionRect))
                {
                    this.sprites.Remove(s);
                }
                else if (this.sprites.Count == 0)
                {
                    parent.cleanUp = true;
                }
            }
            
        }

        private void childNodeSpriteCheck(Sprite s)
        {

            if (childNodes[0] != null)
            {
                childNodes[0].nodeSpriteCheck();
                childNodes[1].nodeSpriteCheck();
                childNodes[2].nodeSpriteCheck();
                childNodes[3].nodeSpriteCheck();
            }
        }

        private void deleteEmptyChildren()
        {
            if (hasChild)
            {
                if (childNodes[0].sprites.Count <= 1 && childNodes[1].sprites.Count <= 1 && childNodes[2].sprites.Count <= 1 && childNodes[3].sprites.Count <= 1)
                {
                    for (int i = 0; i < 4; ++i)
                    {
                        childNodes[i] = null;
                    }
                }
            }
        }

        private bool detectCollision()
        {
            if (sprites.Count >= 2)
            {
                if (sprites[0] == null || sprites[1] == null || !sprites[0].moved || !sprites[1].moved)
                {
                    return false;
                }
                else if (Globals.isCollide(sprites[0].collisionRect, sprites[1].collisionRect))
                {
                    sprites[0].react(sprites[1]);
                    sprites[1].react(sprites[0]);
                    return true;
                }
                else if (!Globals.isCollide(sprites[0].collisionRect, sprites[1].collisionRect))
                {
                    return false;
                }
                else
                {
                    Exception ex = new Exception("QTree Error: Collission Detect failed");
                    throw ex;
                }
            }

            return false;
        }

        private void updateChildren()
        {
            foreach(QTreeNode child in childNodes)
            {
                if (child != null)
                {
                    child.update();
                }
            }
        }

    }
}

[sas1ni69]

3 months? Seems a bit long, no?