Log in
In the previous post, I determined what kind of vegetation should grow where in my procedurally generated world. Now it’s time to actually plant those plants!
As I mentioned last week, I figured out a list of tree species that belong to each “plant functional type” in the BIOME1 system. I made sure to get a set of distinctive-looking trees, so now it was time to fire up Blender, dust off my modelling skills (such as they are) and create some low-poly tree models and an assortment of other plants:
Most of the game takes place at sea, so you won’t often see these models up close. By keeping the polygon count very low, I’m hoping I can render a large enough number of trees without having to resort to impostors. The tallest tree in the back (tonka bean) has only 44 triangles. The simplest plants are just distorted octahedra, with only 8 triangles.
The grasses are generated with Blender’s geometry nodes and are actually way too detailed, with up to 500 triangles each, but I’m not sure I’ll be keeping them anyway. If I do, a handful of intersecting textured planes would be a better implementation.
Inputs
Recall that we have a fairly coarse map of biomes, and that each biome corresponds to a set of plant functional types, each of which contains some plant species. So that indirectly gives us an occurrence map for each species, containing 1.0 where the plant can occur and 0.0 where it can’t.
However, that map only has a resolution of 1×1 km. We don’t want our forest boundaries to be big straight-edged squares, so we’ll have to add some detail to this. In the previous post, I used domain warping to distort the boundaries, because I didn’t want to blend between biome terrain colours. Let’s apply the same trick here, using the same domain warp, so that the plants nicely follow the biome boundaries.
On top of that, I want some artistic control over how often each species appears. For example, in tropical rainforest, most of the visible trees are part of the canopy, but the canopy is occasionally pierced by even taller, so-called “emergent” trees, like the tonka bean we saw above. These should be rarer than the other species, so I’ll give each species a base “occurrence rate”, to be evaluated relative to the other ones in its biome.
And on top of that, not every square meter of land should be covered by trees, even in biomes where they can grow. In nature, factors like soil quality and grazing animals keep areas of land open. This differs by biome: tropical rainforest should have near 100% coverage, but colder or dryer biomes will have less. I’ll mimic that using a single layer of simplex noise, and give each biome a threshold value between 0 and 1. Plants can only grow where the value of the noise is below the threshold.
In the end, this gives me two functions, which can be evaluated at any point in the world:
- Coverage amount: what is the probability of a plant growing here?
- Relative species frequency: if there is a plant here, how likely is it to be of a particular species?
Placement
First off, we don’t want plants to overlap. Maybe in a dense forest, the trees will intersect a little bit, but never by too much. So I’ll assign each species a radius, and declare that the discs defined by these radii must never overlap. This also gives some artistic control; for example, by setting a large radius, we could create a “loner” tree species that doesn’t grow near others.
However, remember that the terrain is generated in chunks (of 1×1 kilometer, like the biome map, but this is a coincidence). When placing plants in one chunk, we cannot refer to trees in the neighbouring chunks, because those might not have been generated yet. If we force generation of neighbouring chunks, we run into a chicken-and-egg problem, because they’ll require their neighbours, and so on. And yet, we have to prevent trees from overlapping.
A simple approach is rejection sampling: pick a uniformly random point inside the chunk, choose a plant species for it, and if there is room for that plant, spawn it there. But then, how would we prevent overlaps with plants from other chunks? We could avoid placing plants near chunk edges, keeping their entire disc inside their own chunk, but then we’d get weird straight paths along chunk edges where no plants grow.
Grid placement
A more suitable approach would be to place plants in a grid (ideally a hex grid, but squares are a bit simpler to work with). Each grid cell contains the center of at most one plant, whose species and position within the cell are computed deterministically from the hash of the cell’s global coordinates. Here sketched on single chunk containing a 3×3 grid for two species:
- species “green” has a small radius and a relative probability of 1
- species “blue” has a large radius and a relative probability of 0.5
Of course, plants will end up overlapping, so we’ll have to prune them. To do that, my first thought was to hash the coordinates of their cells, and keep only the plant with the largest hash. We can then “predict” where plants will spawn in the neighbouring chunks, and deal with overlaps that way. With some fictional two-digit hashes, it could look like this:
However, this has an ordering dependency: suppose plant A overlaps with B, and B overlaps with C. The hashes are ordered as A > B > C. If we handle the overlap A-B first, then B is pruned and C can continue to exist. But if we handle the overlap B-C first, then C is pruned. I didn’t notice this problem until drawing the above image! For instance, the plant with hash 02 could only continue to exist because 43 and 46 were pruned first, since they in turn were dominated by 93 and 88 respectively.
We could impose some fixed ordering for handling overlaps, such as left-to-right, top-to-bottom, but it’s not clear how that would work across chunk boundaries. There might be an entire chain of overlaps running across a chunk, meaning information could “travel” across many chunks, most of which we haven’t generated yet. This would make placement depend, at least a little bit, on chunk creation order – something I’d rather avoid.
On top of that, there is another fundamental problem with this approach: it creates a bias towards smaller plants. Imagine we use a grid of 1×1 meter squares, a shrub has a radius of 1 meter, and a tree has a radius of 10 meters. A potential tree will then overlap with many shrubs, and the probability that it’ll “win” over all of them is near zero. We could try adjusting the relative probabilities to compensate, but I’m not sure how that should work when more than two species are in play.
Rather, since we already applied the relative spawn probabilities of each species, from now on each candidate should have an equal probability of spawning. And… I have no idea how to achieve that.
Rejection sampling
So maybe I should use rejection sampling after all? Pick a random point inside the chunk, pick a species for it, and if there are no overlaps, spawn a plant of that species there. But this runs into the exact same problem! Even if the tree and the shrub are configured with equal probabilities, the tree has a larger radius, and therefore a smaller probability of actually fitting in between the already spawned plants.
Maybe we should spawn larger plants first? But this won’t work either: if two species have equal probability and nearly equal radius, the slightly larger one will dominate.
Maybe we should adjust the spawn probability by radius, or by surface area, to make larger plants more likely to spawn? This should fix the balancing issue – and in fact it should even work with the grid-based approach – but now a large tree with a small probability will create a great many candidates, most of which will be rejected. With rejection sampling, this would kill performance, and with the grid placement, it would occupy most grid cells with plants that will never spawn, and thus not achieve maximum density.
Maybe we could select a plant species first, according to its relative probability, and find a suitable place for it second? Then we could keep searching until it fits somewhere. However, what do we do if we can’t fit it in anymore? To keep the relative frequencies of all plants, we’d have to abort the loop, otherwise we’ll just keep spawning only smaller and smaller plants to fill the gaps, upsetting the balance. But if we do abort the loop, it might mean we haven’t achieved maximum density: a single failed attempt to fit in a large tree would mean that the entire chunk would not be as densely covered as it could be. Another issue is that we can’t select a plant species without knowing the biome, and the biome depends on the location within the chunk.
Iterative methods
Maybe we could iteratively improve our plant placement to converge to the desired balance, while also keeping density. Let’s call this “acceptance sampling”: pick a point, pick a species based on that point’s biome, unconditionally place that plant there, then prune everything it overlaps with. Repeat until satisfied.
However, this has the same problem of imbalance: though large plants now have the right probability of spawning, they instead have a disproportionately large probability of being pruned. We could increase their spawn probability to compensate, but then they’d often spawn only to be pruned shortly afterwards, leaving a gap in coverage. And that’s not even considering how this would work across chunk boundaries.
Turning down the difficulty
This is a much harder problem than I thought at first. I don’t think it’s fundamentally impossible to solve; if you have any ideas, let me know! But I have to avoid wasting even more time on it, so for now, I’m adjusting my requirements: overlapping plants are okay and I’m not going to keep that from happening.
To ensure somewhat even coverage, I’ll still use the grid approach. Now the grid spacing becomes all-important, since it directly determines how many plants will be placed and how much overlap there will be. I’ll have to find some compromise so that large trees don’t overlap too much, while the distance between small plants doesn’t get too large either.
This nicely avoids any problems at chunk boundaries as well, since we don’t need to account for overlaps with plants from neighbouring chunks.
With all that, I’m getting decent results. Here are some patchy coniferous forests interspaced with shrublands:
And a tropical rainforest:
Remaining issues
There are a few more issues to resolve. First, it looks weird if plants grow on sheer cliff faces:
To fix this, I just computed the gradient of the local terrain, and reject the plant if it tries to spawn on a location that’s too steep for that species. This is configurable per species, so that smaller shrubs can still spawn on steep slopes, where big trees couldn’t grow. This helps:
Here’s another issue that needs to be solved:
The white houses represent a port town, and of course it shouldn’t be overgrown like that. We could prevent plants spawning wherever buildings have already spawned, but we can do better: typically, humans will cut down trees for firewood, so there should be some clearing around the port itself.
Thus, my solution is to assign each port an inner and outer radius. Within the inner radius, no plants can spawn at all; the probability is 0. Between the inner and the outer radius, the plant spawn probability smoothly increases towards 1. This is multiplied with the base spawn probability for plants, which is already a noisy function, so we shouldn’t get a hard-edged perfectly circular clearing around the port.
Let’s see how that looks:
Much better!
Performance
At the start, I wrote:
By keeping the polygon count very low, I’m hoping I can render a large enough number of trees without having to resort to impostors.
How is that working out? Not great, unfortunately. On this densely forested archipelago, the trees bring the framerate down from 132 fps to 75 fps:
It gets worse on flat continents, which have even more trees and also more overdraw, even though most of the trees are hidden behind other trees. The framerate goes down to 45 fps on those.
These numbers would be fine if I were testing on a low-end machine and wasn’t planning to add more stuff, but at this stage of development I should be aiming for about 150-200 fps to keep this game playable on potato hardware as well. So it’s clear that I will need to implement impostors after all. But that’s for some other day!
