How We Procedurally Generated Disney Melee Mania’s Vegetation
As a technical artist, I’m most excited about finding new ways to improve our art workflow using math and code. In Disney Melee Mania, each of our holo-arenas are lined with trees, rocks, bushes, and flowers around the perimeters — and thanks to the power of algorithms, they were all generated by our artists in Unity with only a few clicks. Follow along to learn how we achieved this with our vegetation tool!
Before I delve into the details, here’s how we formulated our game plan for this task. In tool development, it’s important that we first establish the context: what features we need, how it will be used, and so on.
The Game Plan
Here’s what we had to keep in mind when building this tool:
- Our vegetation had to reside within railings, which are spline-based objects made using the Curvy Splines package purchased from the Unity Asset Store.
- Vegetation was to be used solely for decorative purposes, remaining largely around the arenas’ perimeters, and would not affect gameplay.
This meant that the vegetation tool had to tackle two main problems:
- How could we generate points within an irregular spline shape?
- How could we randomly distribute those points in a visually appealing way?
Additionally, since our vegetation was not gameplay-critical, I had to be careful not to over-engineer the solution as well.
Now that you have the context of what problems we faced, let’s jump into their solutions!
Staying Within the Rails
First, I had to generate points within our spline railings. Curvy Splines did not provide an out-of-the-box solution for such a specific problem, so where could I begin?
As a start, I found that you could access each spline’s bounding box, allowing me to generate points within the spline’s vicinity.
Note that I started with generating points in a uniform grid, since I didn’t want to worry about random placement just yet. I just had to figure out how to discard all those pesky points lying outside the spline curve.
What else was there to work with? I found the following functions within Curvy Splines:
- 1: Given any point in the world, get the nearest point that lies on the spline
- 2: Given any point on the spline, get its tangent vector
This was pivotal. With access to these two pieces of data, I could derive much more. Enter: vector math!
Using the given functions, I got the following two vectors:
- a: the vector from the nearest spline point N to our point P
- b: the tangent vector at point N
This was actually all I needed. There’s a vector math operation called the cross product. By crossing vectors a and b, I got the resulting vector c, which would point up or down depending on whether a pointed inwards into the spline — in other words, whether P lied inside the spline.
There was another step. To detect whether c pointed up or down, I used another vector math operation called the dot product, which tells us how similar two vectors’ directions are. When dotting c with an up vector (Vector3.Up), a result greater than zero means that P lies inside the spline.
And that’s it! With what amounted to 5 lines of code, here’s the result: uniformly-distributed grids of points that lay exclusively within our rails, no matter what the spline shape was.
Turning Up the Noise
Next: random distribution!
Randomly distributed points are also known as noise. The easiest way of generating noise is to simply pick coordinates using a random number generator, for as many points as you need — sort of like blindly throwing darts at a dartboard. This is what’s known as white noise.
Unfortunately, white noise was a bad option for us. Indiscriminate dart-throwing results in haphazard spreads of clustered and sparse areas, as seen above. Given that our vegetation is meant to blend into the player’s peripheral vision, we couldn’t have any clusters of trees that would distract from the main arena.
We needed a more evenly-spaced distribution of points, albeit still random enough to look organic. Turns out, what we were looking for was blue noise, which is just white noise generated with one more rule: each new point must be some minimum distance from all existing points.
This made things way easier. I continued to pick random coordinates, but then I would compare its position with all other points inside the spline, discarding it if any one point was too close. If the point was distant enough from all the others, then I would add it into the spline area.
To be clear, this was not an efficient algorithm. For a list of N points, each point had to be compared with up to N other points, so our total calculations were in the order of N². To generate 10 trees, it would take 100 calculations, and for 1000 trees, we’d go up to a million! This is why there exists all sorts of optimisations for the Naive Dart Throwing algorithm I just described (yes, that’s the actual name).
But let’s recall the context: our vegetation is not tied to gameplay. It doesn’t need to be generated at runtime. Even if it took entire minutes to generate everything, it would be done offline after all, and having our artists wait a couple minutes would already be far better than having them spend hours placing trees and rocks one at a time. Moreover, I’d already seen in the previous task how many trees it took to fill our railings (even if they were uniformly distributed), and it was much less than 1000.
So, while I had the option of digging deeper into the rabbit hole of optimised blue noise algorithms (Hierarchical Dart Throwing, Scalloped Sector, …), I went ahead and ran our naive generation script first. Guess what?
The whole forest appeared in a blink! Randomly scattered, evenly spaced — and that held true across all of our different railings. The tool did its job quickly enough for our needs, and so was perfectly usable, no further bells and whistles needed.
This task is a great example of avoiding premature optimisation: to not over-engineer a solution at the start until you’ve tested it across your use cases.
To wrap up…
There’s much more to the tool, of course — the user interface, the setup of different adjustable fields like random rotation and object count, and so on. But with these two challenges in particular, I genuinely experienced how the right algorithms can do powerful work for artists. I thoroughly enjoyed this little adventure, and I hope I managed to share some of its wonder with you too!
If you found this article helpful, drop me some claps or give the Mighty Bear Games publication a follow!
How We Procedurally Generated Disney Melee Mania’s Vegetation was originally published in Mighty Bear Games on Medium, where people are continuing the conversation by highlighting and responding to this story.
