Sign in to follow this  

Quadtree node finding question

This topic is 4693 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

I need an algorithm to find the 8 (max) neighboring nodes of a quadtree node. 8 max because some nodes will have fewer neighbors if they are on the edge of the tree. Nodes are given an ID in the order that they are placed in the tree. In a tree with 64 leaves (4 levels) the top left node would be 1-1-1-1 and the bottom right node would be 1-4-4-4 Likewise, bottom left would be 1-3-3-3 and top right would be 1-2-2-2. Is there an easy way to find all neighbors given the ID of any arbitrary node. Also, the algorithm would have to scale to 5,6 +... level trees. I can come up with a way to map all ids into an array that makes it easy to look up, but the problem is I'd have to code different logic for every size tree I make. It would be nice to have an all-inclusive algo for this. I can post a screenshot of a 64 leaf tree, when I get home, that shows the exact order of node creation; if it would help. Can't do it now though... (at work on break)... Thanks, Webby

Share this post


Link to post
Share on other sites
Assuming your nodes are layed out like

1 2
3 4

Subtract 1 from the node value and you get

0 1
2 3

Which is a 2-bit number where the lower bit refers to the X coordinate and the higher bit refers to the Y coordinate.

EXAMPLE
Original: 1-4-3-2-3-1
Original Minus One: 0-3-2-1-2-0
X Coordinate: 0-1-0-1-0-0
Y Coordinate: 0-1-1-0-1-0

The X and Y coordinates can be simply thought of as binary numbers now. Subtracting 1 moves one square left (or up). Adding one moves one square down (or right).

Your 8 surrounding squares are:

(X-1, Y-1), (X, Y-1), (X+1, Y-1)
(X-1, Y ), CENTER , (X+1, Y )
(X-1, Y+1), (X, Y+1), (X+1, Y+1)



Then, after you have added or subtracted 1 from X and/or Y, simply reverse the process and you have your new node.

CONTINUE EXAMPLE: (lower left)

X Coordinate: 0-1-0-1-0-0
Y Coordinate: 0-1-1-0-1-0
X Coordinate - 1: 0-1-0-0-1-1 (Going left means subtract 1 from X)
Y Coordinate + 1: 0-1-1-0-1-1 (Going down means add 1 to Y).
Recombination: 0-3-2-0-3-3.
(This is simply using the corresponding X value as the lower bit of each bit-pair and the Y value as the upper bit)

Add 1 to Recombinaton: 1-4-3-1-4-4

So 1-4-3-1-4-4 is lower-left of 1-4-3-2-3-1







If you need to do this very often, and real fast, you may want to try this method when you are up to the optimising stage:

1) Pack multiple node-directions together in single words so that each direction takes up only 2 bits. (Use directions 0 to 3).

2) Shuffle (I can give you an algorithm if you are interested, but I'll have to find my one 1st) the bits so that the X coordinates are on the low bits of the word and the Y coordinates are on the high bits.

3) Separate the X and Y coordinates into two separate ints.

4) Calculate X-1, X+1, Y-1 and Y+1.

5) Unshuffle these values (I can give you another algorithm here).

6) To get the directions to a square bitwise-OR the unshuffled X value and the unshuffled Y value, then unpack the direction.





NOTE:

If your coordinate system looks like
1 2
4 3
(Increasing or decreasing clockwise) than you can use this formula, or something similar, to get the X value on the lower bit and the Y value on the higher bit:


Hope this helps.

minusOne = (value - 1) ^ ((value - 1) >> 1).

Share this post


Link to post
Share on other sites
Thanks Kyrlloan.
The grid is indeed laid out like
1 2
3 4

Can't wait to implement this and see how it works out. It should be fast enough as is since I'll only be doing it like once a minute or thereabouts.

Cheers!
Webby

Share this post


Link to post
Share on other sites
That works quite well. But another monkey wrench. Is it difficult to from quad tree to an octtree with this?

Took me a while to wrap my head around what was going on in the 2d plane.

Thanks,
Webby

Share this post


Link to post
Share on other sites

This topic is 4693 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this