# Calculate Number of Nodes in a quad tree

This topic is 4970 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Okay I can figure out the number of leaves, for a 257x257 heightmap. (256 / iLeafWidth) * (256 / iLeafWidth) Now I have a way of calculating the number of nodes which I believe is flawed, it only produces the right number when iLeafWidth is 4. Then again I cannot proove this, since I do not know how to sit down on paper and find out exactly how many nodes I will have total...

##### Share on other sites
Consider that the depth of your root is 0, and there is only one root so x0 = 1.

If you have xn nodes at depth n, then you will have xn+1 = 4 xn nodes at depth n+1.

This ends up being: xn = 4n for any n.

That is, unless the nodes at depth n are leaves, at which point they have no children. Let L be the depth of leaves. Then the number of nodes you have is:

X = Σ0..L 4n = (4L+1 - 1) / 3

In any case, L = log4 leafCount, so:

X = (4 * leafCount - 1) / 3

##### Share on other sites
Genious explanation!
After I posted this I did solve the problem in my function but it still has inaccurate moments due to the some dividing which takes place.

I em going to impliment what you have posted.

Thanks.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

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

• Total Topics
634092
• Total Posts
3015448
×