• Create Account

#ActualTheChubu

Posted 15 September 2012 - 07:47 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
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

#3TheChubu

Posted 15 September 2012 - 07:43 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
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

#2TheChubu

Posted 15 September 2012 - 07:41 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
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

#1TheChubu

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
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

PARTNERS