Jump to content
  • Advertisement
Sign in to follow this  
Derakon

Quadtrees and Gray Codes

This topic is 5013 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've been working on implementing quadtrees for my 2D game engine, and it was brought to my attention that there's a serious inefficiency where a sprite crosses a "large" boundary between quads. For example, at the highest level, the entire world is split into four quads; if a sprite moves from one of those four to the other, then there's a lot of maintenance required to figure out which quads you need to check. It occurs to me that this problem is in large part because of the binary nature of quadtrees. The common solution to this kind of problem in other areas is to use a Gray Code (that is, an encoding where any two adjacent values differ by only one bit), and I was wondering how this might apply to quadtrees. This is a rather theoretical detour in my game development, though; if someone's already done such a thing (or shown it to be impractical), then I'd like to know. Otherwise, I may want to look into this further and maybe see about publishing a paper. :)

Share this post


Link to post
Share on other sites
Advertisement
hi,

This is quite a common problem, and there are various different approaches to resolving it.

I think when you talk of 'Gray code' the term you're looking for is 'loose' For example 'loose octrees', although clearly its not restricted to octrees. The term 'loose' simply means to have each node's physical boundaries overlap its neighbours, allowing you to put an object that straddles two or more quadtree nodes into a single one.

An alternative is to move the object/sprite up/down the tree. That is if it straddles two nodes, don't bother entering it into either of them, instead place it in their parents node.

Overall I don't think any one approach is better than any other, it usually comes down to your requirements, and game specifics.

Share this post


Link to post
Share on other sites
That's not exactly what I meant. I'm aware of the overlapping boundaries solution; I'm thinking of other potential ways to solve the problem.

Basically, the goal here is to ensure that quads that are close in space are always close in the data structure as well. Otherwise, a sprite crossing a normally-innocuous boundary incurs a large cost as significantly more sprites must be checked (even, I think, with overlapping boundaries). Simply pushing a sprite higher up in the tree works for most cases, but again, if the sprite crosses a large boundary, then suddenly it's at the top of the tree and is checking far more sprites than is necessary.

Gray codes are a way of encoding numbers such that the difference between any two numerically adjacent numbers is only one bit. For example:


binary:
000 = 0
001 = 1 (one bit changed)
010 = 2 (two bits changed)
011 = 3 (one bit changed)
100 = 4 (three bits changed)

Gray code:
000 = 0
001 = 1 (one bit changed)
011 = 2 (one bit changed)
010 = 3 (one bit changed)
110 = 4 (one bit changed)


Since you can think of a flipped bit in a number as representing a different branch in a tree, what this ultimately means is that in a binary tree, the path from the root to any two adjacent leaves may be vastly different (e.g. left-right-right-right vs. right-left-left-left). A Gray code, in contrast, ensures that adjacent nodes in the tree will always have very similar paths from root to leaf. If I can figure out a good way to represent the leaves using Gray codes, then I should have a fairly efficient representation of a quad tree.

The biggest problem (beyond the difficulty in implementation) is that it no longer really makes sense to have sprites exist anywhere except at leaf level. That is, there's really not much point in "pushing up" a sprite so that it covers more area. At least, not that I can tell right now.

Share this post


Link to post
Share on other sites
Ahh, sorry I mis-read your original post.

I remember some discussions (in Maths and physics forum I think) about directly accessing neighbour nodes in a quadtree, but that doesn't sound quite like what you purpose?

I'm not really sure how what you propose helps you though, what benifit there is in having similar paths from root to leaf. As to me all 4 children already have the same path from the root and easily obtainable from the parent node. So its not like you start searching from the root again just becuase you've crossed a boundary.

Anyway sorry I couldn't help, will be interesting to see if anyone can adress the 'gray code' aspect with regard to use in a quadtree.

Share this post


Link to post
Share on other sites
Quote:
Original post by noisecrime
Ahh, sorry I mis-read your original post.

I remember some discussions (in Maths and physics forum I think) about directly accessing neighbour nodes in a quadtree, but that doesn't sound quite like what you purpose?

That is roughly what I'm after here. The basic problem is that each node in the quadtree has 9 neighbors. Pushing it up one level gives it access to three of them (the three in its quad), and pushing it further up may give it access to more neighbors, but in the extreme case you have to push the sprite up to the very top of the tree, where it has access to every single node. This occurs when at least one of the neighbors is in a different top-level quad than the others.

Quote:

I'm not really sure how what you propose helps you though, what benifit there is in having similar paths from root to leaf. As to me all 4 children already have the same path from the root and easily obtainable from the parent node. So its not like you start searching from the root again just becuase you've crossed a boundary.

I think I've been having some problems visualizing what it is I'm talking about here. Gray codes can be tricky that way; they're not really intuitive at any but the conceptual level. But basically, what it comes down to is that in a Gray code quadtree, when you push a sprite further up the tree, you should always get access to relevant neighbors. I think.

At this point, I'm beginning to suspect that the Gray code idea, while feasible, may be more trouble than it's worth. I'm going to talk it over with a professor tomorrow, though.

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!