Arborithm

Overview

This project provides an a-frame component that procedurally generates trees. Key features include:

• Phenotypic diversity when generating individual trees
• Basic genetic marker simulation when selecting tree traits
• High performance using Web Workers

This package is intended to be used alongside Terrainosaurus to enhance the appearance of each dimension. It's part of Pocket Dimension. Since they're meant to work together, using Arborithm is as simple as passing it the same seed that Terrainosaurus used and the vertices that it generated. Arborithm will register a component that, when added to the scene, will place a bunch of trees inside of itself.

Those are some nice buzzwords you've got there, be a shame if someone explained them

"Phenotypic diversity" is just a fancy person's way of saying that the trees generated by Arborithm can look very different from each other. Trees can vary according to things like trunk height, width, slope, branch number, branch segments, leaf shape, leaf size, and the colors of each component.

Some traits are more likely to appear alongside others - this is where the "basic genetic marker simulation" comes from. While it's technically possible for any trait to appear with any other trait, some traits are more likely to be paired up with others. For example, short trunks and low branch numbers are likely to be associated with tall pyramids for leaves. This gives you a pine tree.

Web Workers are Web Workers. Google them. TL;DR: They let you run some background JS in another thread, and let you send data back and forth using postMessage. Super useful for intensive computations.

Installation

Matthew will do this later. He's lazy and will just use NPM link for now. Sue me.

Usage

Terrainosaurus emits an event named terrainInitialized when the terrain is, you guessed it, initialized. The event will look like

{
  event: {
    detail: {
      terrainClient
    }
  }
}

The terrainClient was used to create the terrain geometry. It has an array with the position of every vertex in the terrain. It also has the seed used to generate everything. This is all the data that arborithm needs from Terrainosaurus. A simple implementation of Terrainosaurus+Arborithm might look something like this:

const terrainosaurus = document.querySelector("[terrainsosaurus-terrain]")
terrainosaurus.addEventListener("terrainInitialized", ({ detail: { terrainClient } }) => {
  // Arborithm also accepts parameters for stuff like tree colors, but we'll ignore that in this example
  const treeGenParams = getTreeGenParams()
  const arborithmClient = new Arborithm({
    vertices: terrainClient.vertices,
    seed: terrainClient.seed,
    ...treeGenParams
  })

  // I read somewhere that it's preferable to use only primitives in a-frame state data.
  // To adhere to this, the component receives a reference to an instance of the Arborithm class, not the instance itself.
  const arborithmEl = document.createElement("a-entity")
  arborithmEl.setAttribute("arborithm", { id: arborithmClient.id })
  
  // We're not appending directly to a-scene.
  // For context, see the Terrainosaurus docs.
  // Basically, the terrain moves up and down so the player stays anchored to the ground.
  // The trees should be appended to the wrapper entity that moves up and down so they stay on the ground too.
  document.querySelector("#scene-content-wrapper").appendChild(arborithmEl)
})

Algorithm

There are two basic procedural generation steps: tree placement and individual tree generation. They are fairly independent, but there are some hidden intersections between the two - certain tree phenotypes are associated with higher or lower tree density.

The trees

From a modeling perspective, trees consist of:

• a trunk (an <a-cone>)
• zero or more branches (<a-torus> elements that have an arc of 90 degrees)
• leaves at the top of the trunk and each branch.

Branches are positioned at a randomized height along the trunk and rotated a randomized amount. The rotation is only slightly randomized; they are evenly distributed and then a small amount of jitter is applied. Each branch has a randomized number of line segments. The more segments it has, the more smoothly curved it is. A branch with zero segments is a straight line.

The trunk is given a randomized height, top and bottom radii, and color. Leaves and branches are also given a single random color.

The randomization process is where the genetic simulation comes in. Some of these traits are continuous numbers, like the height. Others are quantized, like the color. The trait selection process is as follows:

• The quantized traits can be placed in arrays.
• Functions can be defined for each continuous trait.
  • For this example, let's say the height function is f(x) = 1.5 + x
  • Let's say the trunk width function is f(x) = 1.4 - x
• A normalized pseudorandom number is generated. For each array of traits, this number can be scaled to the length of the array and rounded to select a trait.
• The pseudorandom number is passed to the output function for each of the continuous traits. Note that given the functions we've defined in this example, there is an inverse relationship between trunk height and width. Similarly, the quantized traits are all related based on the trait orders we've defined.
• Phenotypes should be correlated, but there should be some variation. To accomplish this, a random number from -1 to 1 is generated for each trait.
  • For the quantized traits, this is used to shift the array index. The random number can be denormalized, and the denormalization factor can be used to control how strict the correlation is between this trait and the others in its index.
  • For the continuous traits, the number is added directly to the trait value, regardless of the output function.

Result: Trees have observably correlated traits (e.g., blue leaves appear more on tall trees), but there are exceptions.

Some terminology: A "species" of tree is defined by the initial random number, before the individual random shifts are applied.

Placing the trees

This is as simple as iterating over every 24th vertex in the array of vertices and deciding whether to put a tree there, and which species of tree. We use only every 24th vertex to simplify dealing with some weird vertex duplication stuff, as well as making sure trees aren't too close together.

At the beginning of the placement process, generate a number of species that should be present in the biome. Generate a set of random numbers to represent each species of tree. Generate a base tree placement likelihood. Some dimensions will be more likely to have trees than others.

Deciding whether to place a tree is done by adding up some thresholds, generating a random number, and checking if it's above the threshold. Each species will have its own threshold. Take the two species with the lowest thresholds and generate a hybrid tree using those numbers. The hybridization process is basically selecting some traits from one species and some traits from the other. For simplicity, the hybrids cannot reproduce. When selecting traits, each trait will prefer either the lower number or the higher number. This will be my very loosely accurate implementation of dominant and recessive traits.

The thresholds are based on the species preferred altitude, slope, and density. Each threshold will have a weight - some trees really won't care about the altitude, for example. The density is use to make trees grow in patterns - track how many trees have been placed nearby and check how close we are to the desired density.