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]
