Jump to content
• Advertisement

# [Tutorial] Instant-Insertion Quadtrees

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

Advertisement
Bookmarked. Thanks for sharing!

#### Share this post

##### Share on other sites

That's pretty damn slick - gotta love the bit-hacks.

#### Share this post

##### Share on other sites

Interesting stuff! I just made a simple quadtree program last week to refresh myself on the C++ language.

I may try making this quadtree as a challenge.

#### Share this post

##### Share on other sites
Great tutorial!

Wit this technique, are my world coordinates forced to be from 0 - 256? And objects will only be spatially sorted at a resolution of (1/256)? Edited by web383

#### Share this post

##### Share on other sites

Great tutorial!

Wit this technique, are my world coordinates forced to be from 0 - 256? And objects will only be spatially sorted at a resolution of (1/256)?

That would make it very limited, wouldn't it? It's 256 in his example since it's easier to show how it works in 8 bits. You can use 16 or 32 bit types if you want, for a much larger area.

#### Share this post

##### Share on other sites

Wit this technique, are my world coordinates forced to be from 0 - 256?

No, you just need to apply a suitable conversion factor.

And objects will only be spatially sorted at a resolution of (1/256)?

Yes. That should be plenty to significantly speed up collision detection, or any other naive O(N^2) process.

You can use 16 or 32 bit types if you want, for a much larger area.

You will run out of memory - it's not feasible to preallocate enough storage. If you really need a quad-tree with depth greater than 8, then you need a sparse representation thereof.

#### Share this post

##### Share on other sites

You can use 16 or 32 bit types if you want, for a much larger area.

You will run out of memory - it's not feasible to preallocate enough storage. If you really need a quad-tree with depth greater than 8, then you need a sparse representation thereof.

Oh right, I mixed up the world coordinates for depth representations. I forgot for a moment that the 8-bit value represents the tree levels, not coordinates.

Converting the coordinates as you said makes more sense.

#### Share this post

##### Share on other sites
But couldnt you just use a part of lets say a 16 bit into to get lets say a 10 level tree?

#### Share this post

##### Share on other sites
The world size can be any value.  In the code, m_fInvRadius is used to make the conversion from world units to internal units here:
		// Now to the range from [0..255].
a2Shifted.m_vMin.x *= m_fInvRadius;
a2Shifted.m_vMin.y *= m_fInvRadius;
a2Shifted.m_vMax.x *= m_fInvRadius;
a2Shifted.m_vMax.y *= m_fInvRadius;
You can use 16-bit values and some adjustments to the internal range to get 10 levels, but that would be 349,525 nodes and 18,175,300 megabytes of memory on 32-bit machines.

8 levels is usually enough. If your world is 10,000 meters square (10 kilometers), the smallest squares are 78.125 meters in size, which is very reasonable resolution. Remember that the smaller your nodes are the more frequently moving objects have to be re-inserted, so there is a trade-off with deeper trees.

L. Spiro

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5
• Advertisement

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633724
• Total Posts
3013556
×

## Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!