Around The World, Part 27: Planting trees : Frozen FractalFrozen FractalGamesProjectsBlogAboutContactMenu×
Lose context
Restore context◂ Back to latest posts▾ Previous: Around The World, Part 26: BiomesAround The World, Part 27: Planting treesFri, 28 Nov 2025 by Thomas ten Cate · Comments
 Game Development, Around the WorldIn 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.InputsRecall 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?PlacementFirst 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 placementA 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 1species “blue” has a large radius and a relative probability of 0.5Of 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 samplingSo 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 methodsMaybe 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 difficultyThis 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 issuesThere 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!PerformanceAt 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!◂ Back to latest posts▾ Previous: Around The World, Part 26: BiomesJavascript needs to be activated to view comments.Copyright © 2025, Frozen Fractal. All rights reserved.VAT nr. NL002153043B85KvK nr. 68703848

This document details the implementation of a procedural tree generation system within the “Around the World” game project, focusing on achieving a realistic and visually appealing forest environment while managing performance constraints. The core of the system revolves around a grid-based approach, combining several techniques to handle biome diversity, species variation, and spatial constraints.

The primary challenge addressed is creating a believable forest landscape, starting with the determination of appropriate vegetation types based on biome data. Thomas ten Cate utilizes a "plant functional type" system to categorize vegetation, ensuring distinct-looking species within each type. The creation of low-polygon tree models and other plants, primarily using Blender, utilizes a deliberately low polygon count to maximize the number of trees that can be rendered without relying on impostors, a technique that can significantly impact performance. The tallest tree, the "tonka bean," has only 44 triangles, demonstrating a conscious effort to minimize visual complexity.

The system employs several key layers of detail. Firstly, a coarse biome map (1x1 km resolution) is refined using domain warping to create more natural biome boundaries, mirroring the previous implementation in “Around the World, Part 26.” Secondly, relative spawn probabilities are established for each species within its biome, allowing for variations in canopy density and emergent trees, as exemplified by the “tonka bean” in tropical rainforests. Furthermore, a single layer of simplex noise introduces a threshold value, dictating the maximum tree coverage within each biome, simulating natural factors like soil quality and grazing.

To manage spatial overlaps, the system initially considered a grid-based placement strategy. Each grid cell, ideally a hexagon but simplified to squares for practicality, is associated with a plant, determined by a hash of the cell’s global coordinates. This approach allows for deterministic placement, contributing to both realism and reproducible results. However, the developer quickly recognized potential issues with this method, particularly how overlaps between plants from adjacent chunks would be handled.

The rejection sampling technique is employed as a primary method for resolving overlaps. By randomly selecting a point within a chunk and assigning a plant species, the system tries to avoid conflicts. However, this method highlights the inherent tension between achieving perfect density and managing performance. The developer identified a critical flaw: the ordering of hash values can dramatically impact placement, leading to cascading pruning of species and ultimately, an unbalanced distribution. The example image illustrates this point clearly, showing how the removal of one plant can trigger the removal of others, based on their hash values.

Recognizing the complexity of the problem, the developer temporarily simplifies the approach, accepting overlapping plants to avoid the intricate issues of hash-based sorting and chunk-boundary management. This decision acknowledges that achieving perfect density at this stage is not a primary concern, prioritizing performance and visual consistency. A grid spacing is established, allowing for a greater density of plants and the potential for overlap.

Several additional refinements are implemented to improve results and address specific issues. The developer incorporates gradient calculations to prevent plants from spawning on overly steep terrain, configurable per species, and adds a “port town” mechanic. Within the port towns, plants are prohibited from spawning within an inner radius, with a smooth transition to full coverage outside. This clever mechanic adds points of interest to the environment and visually represents the impact of human interference.

Despite these efforts, the system's performance ultimately proves insufficient for the game's target framerate, particularly on denser environments. The number of rendered trees and the overdraw (the amount of pixel that needs to be redrawn) are identified as key bottlenecks. In a densely forested archipelago, framerates drop from 132fps to 75fps, and on vast maps the rates plummet to 45fps. This necessitated a planned shift toward implementing impostors, a technique that uses simplified representations of objects to reduce the rendering load.

In conclusion, the “Around the World, Part 27” document details a surprisingly thorough approach to procedural forest generation. The system combines multiple techniques – from biome mapping and species variation to grid placement and spatial constraints – to achieve a complex and visually appealing environment. While initially focused on achieving a high level of detail, the developer ultimately prioritized performance and acknowledged the need for further optimization, especially the inclusion of impostors.