Jump to content
  • Advertisement
Sign in to follow this  
WebsiteWill

Quadtree node finding question

This topic is 4908 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!