Procedural Tree Generator - Game(?) A Week #6

Hello, welcome to this weeks post about my game a week challenge, where this week I decided not to make a game. Basically I wanted something easy and fairly quick to do this week, so I decided on making an idea I've had floating in my head for a while: a procedural tree generator.

Statistics

One thing I didn't realise would be a problem coming into this project was statistics, specifically sampling probability distribution functions (pdf), a fancy term for a graph representing the probably of returning certain values. This section is a bit maths heavy, and an understanding of calculus will help :). Basically, I needed the ability to vary some variables, and I needed to be able to input a value between 0 and 1, and return a value between -1 and 1. This input value (between 0 and 1) needs to control the distribution, where 0 means no variance. and 1 means a uniform variance (a random number between -1 and 1). I was thinking about how to do this with normal distributions and the likes, but after a bit I decided to go with a much simpler method, create my own super simple pdf: two lines.

As you can see, the input value, P, controls the slope of the lines, and the y position of a line at a given point represents the probability of returning that x-value. When P = 0 there is a certain chance of returning 0, and when P = 1, every x-value has an equal probability, so it is a uniform distribution (equal chance of any number being picked). And, when P = 0.5 the number with the highest probability of being picked is 0, becoming increasingly unlikely of picking a number as the graph goes out to the extremities ( 1 or -1).

Now, how do you pick a number out of this distribution? Well, simple, find the cumulative distribution function (cdf), invert the function, normalise the function, pick an x-value between 0 and 1, find the y-value at that point, and there's the return value, simple. Breaking this down step by step: the cdf is a function which is basically just the area for each x-value of the pdf (original function) added together, if you're familiar with calculus you'll know this as the integral of the pdf. For a linear function, the integral is a parabola, so for this particular pdf, the cdf is just two parabolas (since the pdf is made of two lines). Inverting a parabola is fairly easy, original: y = x^2, inverted: y = (plus or minus) sqrt(x). Now this just leaves normalising the function, or making sure that every point in it is between 0 and 1. Unfortunately, the left parabola likes to dip below the x-axis, and the right parabola likes to go above 1, however this is actually a really easy fix: find the maximum of the right parabola, and this value is also the minimum of the left parabola since they're mirrored, so just add the max value to each side, and divide by two times the max value, and voila it's normalised. Then, you pick a random x-value between 0 and 1, and find the corresponding y-value of the inverted function by just plugging it into the function equation.

There are some trick that I pulled to make it faster that I won't go into too much detail on, since they're specific to my case, but here's a conclusion of the final process: 1. Define your probability distribution function (pdf) 2. find the cumulative distribution function (cdf) 3. invert the cdf 4. normalise the cdf 5. pick an x-value between 0 and 1, and then use the inverted cdf to find the y-value, and there's your return value. That's the best way I can explain it, but it's definitely not the best way to have it explained, in the end I'm just a weirdo that loves maths, so I doubt I can do it justice, and if you want to read more: https://en.wikipedia.org/wiki/Inverse_transform_sampling

GDExtension

I found pretty quickly that I had very bad performance, so I decided to rewrite the tree generator in C++, for a performance boost. I've had a bit of a past with C++, so I thought it should be easy enough to get into it. It wasn't. Although that's because I also had to set up an entire C++ environment, downloading a compiler, VSCode, setting it all up, downloading git, the Godot build tool and so on. I'm not much of a computer guy, so in the end it took me from 9 to 5 just to SET IT UP. And until 8 to actually get the code running. All I can say is that the set up process isn't the worst part, and that it's quite the learning experience. The worst part is actually Godot, not because the engine sucks, but because the complete lack of C++ documentation, not like I can complain much though I probably just didn't look hard enough. And to be fair, what you need to know is there, and what I wanted to know wasn't really but kinda was. But whatever, back to the main point, I got it working, and lo and behold... Two times faster. Two times? Seriously? Well, turns out I never quite spent the time to figure out why the generation was slow, so I ended up targeting the wrong problem. Lesson learnt, ask why is it slow before spending a day fixing the wrong pipe. If you're curious to know what the actual problem is, it's deleting all the children, or more simply just removing the old tree. When you run the generator right after opening it you'll notice that the first generation is super quick, and the second generation may crash the application, try it with higher settings to see the full effect.

Future

I didn't have much time this week, and I really wanted to add more features to this generator, so for the first time it's likely that I'll actually come back and redo it, especially with optimisations. But for future plans:

Image exporter, add a box that you can drag around and set a resolution, and a button that allows you to take a picture of the tree and save it as an image.

Graph over distance / height, basically allows variables to change over the distance grow to a point, or the height of a point, allowing for trees that grow super tall, and then explode into an umbrella canopy, or maybe a tree with different coloured leaves depending on the height, so on, so forth.

Redoing the algorithm, after going outside and touching some grass I've realised that my trees don't look like real trees (at least where I live they don't look like the generated trees), and I've notice a couple of things I could change to make them better, as well as some other general improvements

More variables, and the ability to edit colours, I wanted to do the colour one in the first place, but I just didn't get enough time and realised that I wouldn't actually be able to finish the project if I tried to allow colour changing. It's crazy how close I was to not having anything done.

Web export, yeah it just didn't work, I need to build my GDExtension for web, but for some reason I couldn't install Emscripten (a necessary component in building C/C++ for web (WASM)), something about not having python even though I downloaded python a few days ago. Dunno, didn't have enough time so I just gave up and decided to export for windows only since I knew I could build for windows.

That's it for this week, hope you learnt something and definitely didn't skip over the exciting maths section and me rambling about GDExtension troubles. I hope to do more of this in the future, cause I love procedural generation, it's just unfortunate that 3D scares me still, it's just too hard to do a 3D project in a week. P.S. I wrote this post in less than an hour so expect spelling mistakes and errors.