Jump to content

  • Log In with Google      Sign In   
  • Create Account

Confused about QuadTrees


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 TheChubu   Crossbones+   -  Reputation: 4761

Like
0Likes
Like

Posted 15 September 2012 - 07:40 PM

Hi! I'm new in this forum. Been lurkin' for a while, hoped to register later after I've learnt more but alas it wasn't mean to happen Posted Image
I'm doing a OOP course in uni, which teaches OOP with Java. For the final software work we need to make a small board game that uses squared slots.

So I, complicated person as I am, tried to make a Quad Tree to represent the board and the chips in it. Not that I would need it per se, I could just make an 8x8 matrix that stores chip objects and call it a day BUT I'd like to learn quad and oct trees because they are used a lot in 2D and 3D graphics (as far as I know) and they are interesting structures.

Now so far I made a self replicating... thing, and I'm confused about what I should do.
I store the area of each node of the quad tree by storing the centre of each square c=(X,Y) with a width value w=int, essentially, storing quadrants. The quadtree starts with a total size, and then it subdivides itself in 4 smaller quadrants and so on until the width of the quadrants is 0, so it becomes a point. Those were the nodes which would store the data, chips in this case. So say I want to store a chip in the top rightmost corner of an 8x8 board. It's position would be X=8, Y=8 (if we take the lower leftmost corner as (0,0) position to simplify the math).

Root node: center=(4,4) width=4. Stores only its childs.
1st level northeast node c=(6,6) w=2 Stores only its childs.
2nd level northeast node c=(7,7) w=1 Stores only its childs.
3rd level northeast node c(8,8) w=0. This is the point, the node that stores the chip.

To visualize things I made a class to draw crosses on the centres of each node, with double the width of the quadrant. Ie, the first cross would be centered at 4,4, with 8 width on both directions, dividing the entire surface by 4, drawing crosses on each centre and so on. 3rd level nodes are dots (obfuscated by my cross drawing) of width 0. This looks fine, I have the 8x8 square grid I need, its the image 1, image 2 illustrates the tree structure, only drawing the southeastern nodes.

Now, this is all good until I want to store something that it isn't located on one of the last level child nodes but on any other level. Say that I want to store something that is located at the same height as the center of the root node. (2,4) for example. Then my quadtree falls off.
First, several 3rd level nodes (at this level its a point of width 0) would have that particular position according to my code.
Second, there are positions that do not have a node at all!

I made the thing also draw a circle of comparable width in each node (image 3) Biggest circle is the root node, smaller circles are the child nodes. Now, while I'm not confused about what I'm seeing, I'm confused about what I should see. I *think* i should be seeing a circle in the center of each square since those are the positions I want to store (I guess), and i could make it so BUT my math would be off. I'd be drawing centers at half steps, ie, (4.5,4.5) or (7.5,7.5). Which sounds strange for some reason so I think I'm doing something wrong.

For now the good thing is that I can make it draw pretty patterns by increasing its dimention as you can see on the fourth image:P

Here is the Java source for my QuadTree class:
Spoiler

Attached Thumbnails

  • 3_4_IMG.jpg

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator


Sponsor:

#2 Mizu   Members   -  Reputation: 1076

Like
2Likes
Like

Posted 15 September 2012 - 09:03 PM

Welcome to GameDev Posted Image

Now, I might not be too helpful since I'm very tired, and I hope someone else comes by and give you more detailed help, but I can say this: you don't subdivide a quadtree until the size of your nodes reach 0. A quadtree node could be seen as a bounding box that is able to store the objects you want the quadtree to store. There are many different implementations of quadtrees but usually, in a simple implementation you stop subdividing when you reach a set minimum node size (above 0).

If you subdivide each node into four children of equal size there should be no point inside the root node that doesn't have a node, and the only difference between the leaf nodes and the rest of the nodes is that the leaf has no children (again, I'm talking about the most basic implementation here...)

If you place an object in such a way that it is inside more than one leaf node, then you usually either split the object between the nodes or place it at a higher level. When inserting an object in the tree, you supply the position of the object, and the tree find out which leaf node contains that position (by going down through each level of the tree and checking the position against the bounds of each node) and insert the object there.

I *think* i should be seeing a circle in the center of each square since those are the positions I want to store (I guess), and i could make it so BUT my math would be off. I'd be drawing centers at half steps, ie, (4.5,4.5) or (7.5,7.5). Which sounds strange for some reason so I think I'm doing something wrong.

If your smallest node size is 1 and you store the middle position of the node, then you're right, you should see a circle in the center of each square, and that would mean you'd get positions like (0.5; 0.5) and (7.5 7.5). Right now the positions of those smallest circles seems strange to me (there's not even an equal number of circles as there is squares. This should be the case if each square equals one node)

Hope that helps at least a little Posted Image

#3 TheChubu   Crossbones+   -  Reputation: 4761

Like
0Likes
Like

Posted 16 September 2012 - 09:53 PM

Of course! If I'm storing the centres of the quadrants and the distance from the sides, im not storing the actual width of the node but half the width of the node. So if I want an 1x1 quadrant (smallest quadrant I want to store), the width will be 0.5 and its centre will be placed at a half step too. The leaf nodes are both badly placed and have the wrong width value in my current implementation. Thanks!

Now I have two solutions to that:
1. Convert all positions to floats so I can handle the values I need, plus change a lil bit the leaf node constructor.
2. Change the node representation, storing instead of the centres, say, the top left corner position of each node and the real width of the node (so an 1x1 node would have 1 as the real width).

I'm going with the first one since I planned to use floats eventually, I just used ints to simplify the math at first (besides I like the centered coords).

The thing is that ideally I wanted only the leaf nodes to store information. I hadn't thought about splitting the position of the object among the leaf nodes. But I guess that the most "elegant" solution is just using the father node to store the object instead. There I have an issue since I hadn't expected to store more than one object on a single node (father nodes and the root node can comprise several positions that the leaf nodes can't).

I guess I'll have to use a linked list of objects in each node or something like that, though I'd like to evade that since I wanted a simpler approach... Maybe calculating all the positions a node could have and make an array of objects of that size? ie, root node of an 8x8 size can have all positions that go along (4,Y) and (X,4), a max of 16 objects. Its child nodes would have a max of 8 objects each, and so on until I reach the leaf nodes that only store a single object.

But now that I think of it, my math is off. Root node could store in the X axis (0,4) (1,4) (2,4) (3,4) (4,4) (5,4) (6,4) (7,4) and (8,4). 9 positions per axis. 18 in total. If I limit its range from 0 to 7, it would store 8, but the centre would be off by 0.5 (ie, 4 its not the centre between 0 and 7, 3,5 is). GAH! I'll code the float fix tomorrow, see if I can get a proper tree generated, and then i'll think how to store things in it...

Thanks for your response again and more feedback is appreciated.

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS