[dartoscoder]

I have been working on this quadtree for a while and its pretty much done except for a few functions and I wanted to know what all of you think of it. When I get those last functions added I will update the code below

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

namespace QtreeTest
{
    public class QTreeNode
    {
        QTreeNode[] childNodes = new QTreeNode[4];
        public List<Sprite> sprites = new List<Sprite>();
        int quad = -1;
        int generation = 0;
        public QTreeNode parent = null;

        public Rectangle areaRect;

        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.parent = parent;
            this.quad = quad;
        }

        void update()
        {
            if(sprites.Capacity == 2)
            {
                detectCollision();
            }
            else if(sprites.Capacity > 2 && generation <= 4)
            {
                while (sprites.Capacity > 2)
                {
                    for (int i = 0; i < 3; i++)
                    {
                        switch (i)
                        {
                            case 0:

                                childNodes[i] = new QTreeNode(0, 0, this.areaRect.Width / 2, this.areaRect.Height / 2, this, this.generation + 1, 1);
                                
                                foreach (Sprite s in sprites)
                                {
                                    if(s.collisionRect.Intersects(childNodes[i].areaRect))
                                    {
                                        this.sprites.Add(s);
                                        this.sprites.Remove(s);
                                    }
                                }

                                break;
                            case 1:

                                childNodes[i] = new QTreeNode(this.areaRect.Width / 2, 0, this.areaRect.Width, this.areaRect.Height / 2, this, this.generation + 1, 2);

                                foreach (Sprite s in sprites)
                                {
                                    if (s.collisionRect.Intersects(childNodes[i].areaRect))
                                    {
                                        this.sprites.Add(s);
                                        this.sprites.Remove(s);
                                    }
                                }

                                break;
                            case 2:

                                childNodes[i] = new QTreeNode(this.areaRect.Width / 2, this.areaRect.Height / 2, this.areaRect.Width, this.areaRect.Height, this, this.generation + 1, 3);

                                foreach (Sprite s in sprites)
                                {
                                    if (s.collisionRect.Intersects(childNodes[i].areaRect))
                                    {
                                        this.sprites.Add(s);
                                        this.sprites.Remove(s);
                                    }
                                }

                                break;
                            case 3:

                                childNodes[i] = new QTreeNode(0, this.areaRect.Height / 2, this.areaRect.Width, this.areaRect.Height, this, this.generation + 1, 4);

                                foreach (Sprite s in sprites)
                                {
                                    if (s.collisionRect.Intersects(childNodes[i].areaRect))
                                    {
                                        this.sprites.Add(s);
                                        this.sprites.Remove(s);
                                    }
                                }

                                break;
                        }
                    }
                }
            }
            else if (generation > 4)
            {
                detectCollision();
            }
        }

        public void nodeSpriteCheck(Sprite s)
        {
            if (s.collisionRect.Intersects(this.areaRect))
            {
                for (int i = 0; i < s.interGrid.Length - 1; i++)
                {
                    if (s.interGrid[i] == null)
                    {
                        s.interGrid[i] = this;
                        break;
                    }
                }
                childNodes[1].nodeSpriteCheck(s);
                childNodes[2].nodeSpriteCheck(s);
                childNodes[3].nodeSpriteCheck(s);
                childNodes[4].nodeSpriteCheck(s);
            }
        }

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

        public bool hasChild()
        {
            if (childNodes[0] != null)
            {
                return true;
            }

            return false;
        }

        public bool detectCollision()
        {
            if (sprites[0] == null || sprites[1] == null)
            {
                return false;
            }
            else if (sprites[0].collisionRect.Intersects(sprites[1].collisionRect))
            {
                sprites[0].react(sprites[1]);
                sprites[1].react(sprites[0]);
                return true;
            }
            else
            {
                Exception ex = new Exception("QTree Error: Collission Detect failed");
                throw ex;
            }
        }
    }
}

If any of you have any comments/tips/anything to say I would be glad to hear from you.

[Skydiver]

Off topic:
When did quad-tree's start being called qtree's ? So are oct-trees now call otrees? And will binary trees be called btrees and who cares if there are B-trees and B+ trees already?

Shouldn't this question in the XNA or Game Development section?

On topic:
I think you should at least try running and testing your code before asking for code review. I think that you will discover that you are still a ways off from "pretty much done except for a few functions".

Public variables should follow Pascal casing. (See lines 12, 15, 17)

You should wrap your public variables in properties. This is to future proof yourself should you decide to change a variable name or implementation.

Public methods should follow Pascal casing.

A List<>'s Capacity is different from a List<>'s Count. I think you are checking the wrong property, but I could be wrong since some of the intent of your code is not clear.

Your for loop on line 36 doesn't do the full range of i.

See lines 44-51. Does this actually work at runtime without exceptions?

You have practically duplicated code across each of your case statements on lines 44-99. Moving the duplicate code into a function will help make the code more readable.

Your update() function seems to only detect collisions if the sprite list capacity is 2, or you are in generation 4. What about the other cases?

What happens to nodeSpriteCheck() if there are no child nodes?

Why are your arrays in nodeSpriteCheck() indexed from 1 rather than 0? Woudn't a for or foreach loop make more sense?

Your detectCollision() only detects collisions for two sprites, yet you hold a list of sprites.

Your detectCollision() should only detect collisions. You are making it double duty and also react to the collisions.

[dartoscoder]

Response to off topic:
This is the first tree-like anything I have ever made. Being self taught I need to come up with my own naming conventions and that is what I used. I have nothing against naming it a QuadTreeNode but I used QTreeNode *shrug*.

No I don't think this belongs in XNA development because trees are not specific to XNA.

Response to on topic:
Oh wow.. I missed a lot of stuff huh?
Thanks for pointing this stuff out. I am working on it now but like I said, my first tree.

Thanks for the input I'll update it when I address those issues.

As I am pretty new to C# (Have been programming in it for 3 months) I am not sure what you mean my "wrapping it in a property". Is that just giving it get and set methods? How would that make it easier for me to change variable names?

This post has been edited by dartoscoder: 03 August 2012 - 12:02 PM

[Skydiver]

Yes, a property has get/set accessors. It lets you do something like this:

class Obama {
    int noTaxIncreases = 0;

    public int TaxIncreases {
        get { return noTaxIncreases; }
    }
};

To this:

class Obama {
    int someTaxIncreases = 15;

    public int TaxIncreases {
        get { return someTaxIncreases; }
    }
};

[Curtis Rutland]

not just for name changes. It makes most refactoring easier. If you ever need to do something other than just returning a value (or setting it) it makes all the difference.

Just a contrived example, but let's say you use a public int field. Then, later, you realize that there's one specific value that your field should never be set to. So, you can either go find all the places you used that field and change it, or you could use a property:

const int BAD_VALUE = -1024;

private int _MyValue;

public int MyValue{

  get {
    return _MyValue;
  }

  set {
    if(value == BAD_VALUE) 
      throw new Exception ("Bad value");
    _MyValue = value;
  }
} 

[Skydiver]

And then when it's time to convert:

public List<Sprite> sprites = new List<Sprite>();

You'll run into different philosophies. Some believe this is perfectly fine:

public List<Sprite> Sprites
{
    get;
    set;
}

I tend to go along the path of:

public IEnumerable<Sprite> Sprites
{
    get
    {
        return new List<Sprite>(_sprites);
    }

    protected set
    {
        _sprites = value;
    }
}

And you'll probably see and hear everything in between. It'll depend on what your performance goals are and what your contracts are with the code that calls your class.

[baavgai]

I'm confused. You talk about QTree, but all I see is a class QTreeNode. There are also public things that shouldn't be, so it's even hard to guess how you want to use it. Do you have an example of how you use this? Just some test code?

Also, pet peeve:

public bool hasChild()
{
	if (childNodes[0] != null)
	{
		 return true;
	}
	return false;
}

Don't evaluate a condition an then return the result by proxy. Just go straight to it:

public bool hasChild() { return (childNodes[0] != null); }

[dartoscoder]

Skydiver, on 03 August 2012 - 03:43 PM, said:

I tend to go along the path of:

public IEnumerable<Sprite> Sprites
{
    get
    {
        return new List<Sprite>(_sprites);
    }

    protected set
    {
        _sprites = value;
    }
}

And you'll probably see and hear everything in between. It'll depend on what your performance goals are and what your contracts are with the code that calls your class.

What is the benefit of doing it this way? It looks like it would take more processor time to make a new list every time I need to access it.

[AdamSpeight2008]

Immutability / Read-Only view.
As List<T> is a reference type

[dartoscoder]

I don't really understand what you mean by immutability.

Aside from encasing the variables in propertys I have made some good changes.

It seems to work in testing now. But for some reason it said that childNodes[3] is never initialized. Probably something wront with the for loop. I'll fix it but here is the code right now

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];
        public List<Sprite> sprites = new List<Sprite>();
        int quad = -1;
        int generation = 0;
        public QTreeNode parent = null;
        public Rectangle areaRect;

        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.parent = parent;
            this.quad = quad;
        }

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

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

            foreach (Sprite s in sprites)
            {
                if(s.collisionRect.Intersects(childNodes[i].areaRect))
                {
                    childNodes[i].sprites.Add(s);
                    toDestroy.Add(s);
                }
            }

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

        public void update()
        {
            QTreeManager.reloadAllNodes();
            if(sprites.Count == 2)
            {
                detectCollision();
            }
            else if(sprites.Count > 2 && generation <= 4)
            {
                while (sprites.Count > 2)
                {
                    for (int i = 0; i < 4; ++i)
                    {
                        switch (i)
                        {
                            case 0:

                                createChild(i);

                                break;
                            case 1:
                                createChild(i);

                                break;
                            case 2:
                                createChild(i);

                                break;
                            case 3:
                                createChild(i);

                                break;
                        }
                    }
                }
            }
            else if (generation > 4)
            {
                detectCollision();
            }
        }

        public void nodeSpriteCheck(Sprite s)
        {
            if (s.collisionRect.Intersects(this.areaRect))
            {
                for (int i = 0; i < 3; ++i)
                {
                    if (s.interGrid[i] == null)
                    {
                        s.interGrid[i] = this;

                        if (!this.sprites.Contains(s))
                        {
                            this.sprites.Add(s);
                        }
                        
                        break;
                    }
                }

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

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

        public bool hasChild()
        {
            return childNodes[0] != null;
        }

        public bool detectCollision()
        {
            if (sprites[0] == null || sprites[1] == null)
            {
                return false;
            }
            else if (sprites[0].collisionRect.Intersects(sprites[1].collisionRect))
            {
                sprites[0].react(sprites[1]);
                sprites[1].react(sprites[0]);
                return true;
            }
            else if (!sprites[0].collisionRect.Intersects(sprites[1].collisionRect))
            {
                return false;
            }
            else
            {
                Exception ex = new Exception("QTree Error: Collission Detect failed");
                throw ex;
            }
        }
    }
}

Fixed it. I am stupid with for loop logic.

This post has been edited by dartoscoder: 03 August 2012 - 09:41 PM

[Curtis Rutland]

Immutability means it can't change. Which isn't a perfect description, because something truly immutable couldn't change at all. If you wrap a private field in a property without a public setter, external code can't change the field. Internal code can. Which is, in a lot of cases, a desired result. You wouldn't want some other code using your tree class to reinitialize a list, right? So, if you just have a getter and no (or a private) setter, only your code in the class can reassign the list.

And yes, properties do have minor overhead. It's not worth worrying about it, considering the other benefits it provides. Read up on it. It's a pretty standard practice in the world of object oriented programming. In Java, they use getter and setter methods. C# obfuscates it a bit more, but in the IL it's the same thing. A property is basically one or two methods, get and/or set.

[Skydiver]

Lines 58-80 can now be collapsed into 2 lines:

for(int i = 0; i < 4; i++)
    createChild(i);

Unfortunately all the children are sharing the same rectangle... the top left rectangle.

You can play some tricks with the & operator to determine whether to offset right, bottom, or bottom right.

This post has been edited by Skydiver: 03 August 2012 - 11:12 PM

[Skydiver]

Line 122 still indexes an array out of bounds.

On Line 163, you should through your own custom exception, or pick of the other pre-made ones. This is because in the future, if you want to catch your exceptions, you won't be stuck writing:

catch(Exception e) { ... }

which will catch all exceptions including stack overflows, out of memory condition, etc, which you probably don't want to catch.

This post has been edited by Skydiver: 03 August 2012 - 11:21 PM

[baavgai]

You know, createChild only creates a child for the top left quad? Also, you forgot generation in the constructor, so it will always be 0.

I look at deleteEmptyChildren and I see you digging deep:

childNodes[1].sprites.Count == 0 && childNodes[2].sprites.Count...

It seems that such a test wants a method. Or two.

public bool IsEmpty { get { return sprites.Count == 0; } }

private void deleteChildren() {
	for (int i = 0; i < childNodes.Length; i++) {
		childNodes[i] = null;
	}
}
private void deleteEmptyChildren() {
	if (hasChild()) {
		foreach(QTreeNode node in childNodes) {
			if (node.IsEmpty) { return; }
		}
		deleteChildren();
	}
}

It's unclear why you'd want to do this at all, though. Reasonably, you wouldn't create a child if there were no eligible sprites to put in it? This would automatically prune your tree, with significant savings.

Your quad tree could use a List for nodes, having only the children that contain sprites. Conversely, you could just create the entire structure and never delete.

[dartoscoder]

baavgai, on 04 August 2012 - 05:23 AM, said:

You know, createChild only creates a child for the top left quad?

In the first code I put in it generated all the quads. When I moved all the code to a separate function I forgot to make the other quads. And I forgot about generation, thanks.

Here is the new code. Still didn't put properties in there yet. I want to make sure it works 100% first.

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 Rectangle areaRect;

        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(int i)
        {
            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>();

            foreach (Sprite s in sprites)
            {
                if(s.collisionRect.Intersects(childNodes[i].areaRect))
                {
                    childNodes[i].sprites.Add(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 < 4)
            {
                createChildren();
            }
            else if (generation > 4)
            {
                detectCollision();
            }

            updateChildren();

        }

        private void nodeSpriteCheck()
        {
            foreach (Sprite s in Globals.globalAllSprites)
            {

                if (!this.sprites.Contains(s))
                {
                    this.sprites.Add(s);
                }

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

        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 == 0 && childNodes[1].sprites.Count == 0 && childNodes[2].sprites.Count == 0 && childNodes[3].sprites.Count == 0)
                {
                    for (int i = 0; i < 4; ++i)
                    {
                        childNodes[i] = null;
                    }
                }
            }
        }

        public bool hasChild()
        {
            return childNodes[0] != null;
        }

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

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

    }
}

This post has been edited by dartoscoder: 04 August 2012 - 11:16 AM