Anyone want to review my QTree?

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 3476 Views - Last Post: 06 August 2012 - 11:11 AM Rate Topic: -----

#16 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3631
  • View blog
  • Posts: 11,327
  • Joined: 05-May 12

Re: Anyone want to review my QTree?

Posted 04 August 2012 - 11:36 AM

You know that your code doesn't even compile, right? createChildren() takes one parameter, yet you call it without passing a parameter.
Was This Post Helpful? 0
  • +
  • -

#17 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3631
  • View blog
  • Posts: 11,327
  • Joined: 05-May 12

Re: Anyone want to review my QTree?

Posted 04 August 2012 - 11:42 AM

What are you trying to do with your nodeSpriteCheck()? It looks like all your nodes will have references to all the sprites in the world, which I think is not the intent of a quad tree. A node should only contain the sprites in its area.
Was This Post Helpful? 0
  • +
  • -

#18 dartoscoder  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 313
  • Joined: 15-May 09

Re: Anyone want to review my QTree?

Posted 06 August 2012 - 09:24 AM

Besides the properties I think I got the whole thing working. All the tests say it is running fine so.. Here is my code

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;
        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 (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;
                    }
                }
            }
        }

        private bool detectCollision()
        {
            if (sprites[0] == null || sprites[1] == null || !sprites[0].moved || !sprites[1].moved)
            {
                return false;
            }
            else if (Globals.isCollide(sprites[0], sprites[1]))
            {
                sprites[0].react(sprites[1]);
                sprites[1].react(sprites[0]);
                return true;
            }
            else if (!Globals.isCollide(sprites[0], sprites[1]))
            {
                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();
                }
            }
        }

    }
}



Thank you all so much.

View PostSkydiver, on 04 August 2012 - 12:36 PM, said:

You know that your code doesn't even compile, right? createChildren() takes one parameter, yet you call it without passing a parameter.

Yeah I posted the wrong code and tried to fix it in the post text editor and made that mistake.

This post has been edited by dartoscoder: 06 August 2012 - 09:25 AM

Was This Post Helpful? 0
  • +
  • -

#19 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3631
  • View blog
  • Posts: 11,327
  • Joined: 05-May 12

Re: Anyone want to review my QTree?

Posted 06 August 2012 - 10:43 AM

Same comment as my post #17. You are adding all the global sprites into all your nodes with your nodeSpriteCheck(). I doubt this is what you want to do with a quad-tree since the point is for only each node to only have the sprites within its area. Yes, you trim away the extra sprites when you pop back up to the update() context, but you'll put them right back in again on the next update() call.
Was This Post Helpful? 0
  • +
  • -

#20 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5884
  • View blog
  • Posts: 12,768
  • Joined: 16-October 07

Re: Anyone want to review my QTree?

Posted 06 August 2012 - 11:11 AM

You know, when you create a child, only three values should fundamentally change:
private QTreeNode CreateChild(int x, int y, int quad) {
	return new QTreeNode(x, y, this.areaRect.Width / 2, this.areaRect.Height / 2, this, this.generation + 1, quad);
}



That is, the dimensions for all four children should be the same. Maybe differing by one either way, depending on your slice.

Perhaps I'm missing something... You could also put the sprite push down logic in that CreateChild.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2