3 Replies - 684 Views - Last Post: 20 December 2012 - 11:30 PM Rate Topic: -----

#1 GryphonClaws  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 09-December 12

QuadTree's for Collision Detection

Posted 20 December 2012 - 03:28 PM

Hello D.I.C.

I'm here today to ask for a little guidance from those of you who have written a quadtree that was used for collision detection. As I was looking at my design today I realized that I need to change it up even more to get the functionality I desire, but I got to wondering what is a good way to tackle this problem. I'm not looking for code, just opinion here.

My idea is that I want two classes, QuadTree, and QuadTreeNode. The QuadTree class will handle all the creation of QuadTreeNodes and updating objects, checking collisions, and deciding which nodes need to be updated or not. QuadTreeNode should only keep track of what objects are currently inside of said node, and if the node has children or a parent. I wanted to make the tree divide a node when the maximum object limit is hit, but I got to wondering, lets say I divide a node into four, but objects are only in three of the new nodes. Should I delete that empty node, or leave it alone? I assumed that If I leave it, then the parent node would need to keep track of that single object since all the other objects should be moved to the children nodes, but I would like to hear from people more experienced than I. This is my first time attempting something so complex and any helpful tips/opinions are appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: QuadTree's for Collision Detection

#2 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: QuadTree's for Collision Detection

Posted 20 December 2012 - 07:06 PM

Firstly, QuadTreeNode should be a structure or some other abstract data type that represents a node. Your QuadTree class is the object that will manipulate the data representing your partitioned space.

Functionality like collision detection is not what defines quadtree structure, so should not be part of the QuadTree class.

Regarding deleted nodes on your quadtree, maybe you should mark them as 'occupied' or not so that the references remain for the overall partitioned space.
Was This Post Helpful? 1
  • +
  • -

#3 GryphonClaws  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 09-December 12

Re: QuadTree's for Collision Detection

Posted 20 December 2012 - 10:38 PM

Well the quadtree doesn't actually do the collision checks, I'm just using it to control how often checks are done. I guess I don't really need QuadTreeNode to be a class, as you pointed out. Thanks for the response, I can see that I at least had the right idea.
Was This Post Helpful? 0
  • +
  • -

#4 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: QuadTree's for Collision Detection

Posted 20 December 2012 - 11:30 PM

Awesome.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1