Jump to content
• Advertisement

Public Group

# Confused about QuadTrees

This topic is 2283 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

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
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]public class FSEQuadTree { public static FSECoordHandling coordHndlingObj; static boolean lastChild = false; static int maxX, maxY; static int objCount = 0; public int nodeID; public int width; public int posX, posY; public FSEQuadTree NE, SE, SO, NO; //This is the constructor of the root node. //It gets the size of the surface its supposed to //represent. Ie, gets an 8 for an 8x8 surface. public FSEQuadTree ( int dimXY) { //Calculate distance from the centre of the //node to its sides. For the root node this is simple //its half the size of the quadtree's surface. int tmpHalfDist = dimXY/2; //These are the maximum coordinates of //the quadtree. FSEQuadTree.maxX = dimXY; FSEQuadTree.maxY = dimXY; //Node ID number. this.nodeID = objCount; //Node counter. FSEQuadTree.objCount++; //Storing the coord of the node. In the case of the //root node, its the same as its width. //For a 8x8 surface, the root node's center is going //to be X=4, Y=4 and its width = 4. this.posX = tmpHalfDist; this.posY = tmpHalfDist; this.width = tmpHalfDist; //Now here I calculate the coords of the 4 //quadrants that compose the root node. //Some names are in Spanish. //Value of X for eastern sub quadrants. int tmpCentroXEste = this.posX+(this.width)/2; //Value of X for the western sub quadrants. int tmpCentroXOeste = this.posX-(this.width)/2; //Value of Y for the northern sub quadrants. int tmpCentroYNorte = this.posY+(this.width)/2; //Value of Y for the southern sub quadrants. int tmpCentroYSur = this.posY-(this.width)/2; //The 4 child quadrants are made, passing their coords to the //child node constructor in the next order: //Northeast, Southeast, Southwest, Northwest. this.NE = new FSEQuadTree( tmpCentroXEste, tmpCentroYNorte, this.width ); this.SE = new FSEQuadTree( tmpCentroXEste, tmpCentroYSur, this.width ); this.SO = new FSEQuadTree( tmpCentroXOeste, tmpCentroYSur, this.width ); this.NO = new FSEQuadTree( tmpCentroXOeste, tmpCentroYNorte, this.width ); } //This is the child node constructor. It differs a little from //the root node constructor. private FSEQuadTree ( int dimX, int dimY, int fWidth ) { this.nodeID = objCount; FSEQuadTree.objCount++; //Assign the central coords . this.posX = dimX; this.posY = dimY; //The width of the child node is the half of its father. this.width = (fWidth/2); //Now, I evaluate if the node is a last level node or not. //Last level nodes have width 0. The "leaves" of the tree. if ( ((this.width)/2) > 0 ) { //If it isnt a last level node, calculate the coords //normally and pass them to the constructor. int tmpCentroXEste = this.posX+(this.width)/2; int tmpCentroXOeste = this.posX-(this.width)/2; int tmpCentroYNorte = this.posY+(this.width)/2; int tmpCentroYSur = this.posY-(this.width)/2; this.NE = new FSEQuadTree( tmpCentroXEste, tmpCentroYNorte, this.width ); this.SE = new FSEQuadTree( tmpCentroXEste, tmpCentroYSur, this.width ); this.SO = new FSEQuadTree( tmpCentroXOeste, tmpCentroYSur, this.width ); this.NO = new FSEQuadTree( tmpCentroXOeste, tmpCentroYNorte, this.width ); } else { //If it is a last level node, pass the positions to another constructor. this.NE = new FSEQuadTree( this.posX+1, this.posY+1 ); this.SE = new FSEQuadTree( this.posX+1, this.posY-1 ); this.SO = new FSEQuadTree( this.posX-1, this.posY-1 ); this.NO = new FSEQuadTree( this.posX-1, this.posY+1 ); } } //This is the constructor of the leaves of the tree. private FSEQuadTree ( int dimX, int dimY ) { this.nodeID = objCount; FSEQuadTree.objCount++; this.posX = dimX; this.posY = dimY; //Last level nodes are dots with width 0. this.width = 0; //No further nodes are needed. this.NE = null; this.SE = null; this.SO = null; this.NO = null; } } [/spoiler]

#### Share this post

##### Share on other sites
Advertisement
Welcome to GameDev

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

#### Share this post

##### Share on other sites
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.

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5
• Advertisement

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633755
• Total Posts
3013706
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!