Article 8

Procedural Generation

Generate terrain with diamond-square, grow trees via space colonisation, trace rivers, and distribute flora with Poisson disc sampling.

⏱ 60 min procedural terrain L-systems space colonisation Poisson disc noise

Procedural generation systems combine deterministic algorithms with controlled randomness to produce environments, structures, and organisms that feel natural while remaining fully parameterised. This article builds a layered procedural landscape: heightmap, tree placement, and river tracing.

Simplex Noise vs Perlin Noise

Processing’s noise() function uses Ken Perlin’s improved Perlin noise (2002), which uses gradient interpolation over a permutation table. Simplex noise (also by Perlin, 2001) is computationally cheaper in higher dimensions and lacks the axis-aligned artefacts visible in Perlin noise at certain scales.

Processing does not include simplex noise natively. A common approach is to import a Java simplex implementation or use octave-stacked Perlin noise to approximate simplex quality:

float fbm(float x, float y, int octaves, float lacunarity, float gain) {
  float value    = 0;
  float amplitude = 0.5;
  float frequency = 1.0;
  for (int i = 0; i < octaves; i++) {
    value    += amplitude * (noise(x * frequency, y * frequency) - 0.5) * 2;
    amplitude *= gain;
    frequency *= lacunarity;
  }
  return value;
}

Use lacunarity = 2.0, gain = 0.5 for standard fractal Brownian motion. Lower gain values (0.4) produce smoother, more plateau-like terrain.

Diamond-Square Terrain Algorithm

Diamond-square is a midpoint displacement algorithm that generates heightmaps on a (2^n + 1) × (2^n + 1) grid. It alternates between diamond and square steps, halving the displacement range each iteration.

final int  SIZE   = 257;  // 2^8 + 1
float[][]  hmap   = new float[SIZE][SIZE];
float      rough  = 0.7;  // 0 = flat, 1 = jagged

void diamondSquare(int step) {
  int half = step / 2;
  if (half < 1) return;

  // Diamond step
  for (int y = half; y < SIZE - 1; y += step) {
    for (int x = half; x < SIZE - 1; x += step) {
      float avg = (hmap[x-half][y-half] + hmap[x+half][y-half]
                 + hmap[x-half][y+half] + hmap[x+half][y+half]) / 4.0;
      hmap[x][y] = avg + random(-rough, rough);
    }
  }

  // Square step
  for (int y = 0; y < SIZE; y += half) {
    for (int x = (y + half) % step; x < SIZE; x += step) {
      int count = 0;
      float sum = 0;
      if (x - half >= 0)    { sum += hmap[x-half][y]; count++; }
      if (x + half < SIZE)  { sum += hmap[x+half][y]; count++; }
      if (y - half >= 0)    { sum += hmap[x][y-half]; count++; }
      if (y + half < SIZE)  { sum += hmap[x][y+half]; count++; }
      hmap[x][y] = sum / count + random(-rough, rough);
    }
  }

  rough *= 0.5;  // halve displacement range
  diamondSquare(half);
}

void generateTerrain() {
  // Seed corners
  hmap[0][0]           = random(-1, 1);
  hmap[SIZE-1][0]      = random(-1, 1);
  hmap[0][SIZE-1]      = random(-1, 1);
  hmap[SIZE-1][SIZE-1] = random(-1, 1);
  rough = 0.7;
  diamondSquare(SIZE - 1);
}

Poisson Disc Sampling for Natural Point Distribution

Poisson disc sampling generates points with a guaranteed minimum distance between them, producing distributions that look like naturally scattered objects (trees, rocks, flowers) rather than uniform grids or pure noise.

import java.util.ArrayList;

ArrayList<PVector> poissonSample(float minDist, int maxAttempts) {
  float cellSize = minDist / sqrt(2);
  int   cols     = ceil(width  / cellSize);
  int   rows     = ceil(height / cellSize);
  int[] grid     = new int[cols * rows];
  java.util.Arrays.fill(grid, -1);

  ArrayList<PVector> points  = new ArrayList<PVector>();
  ArrayList<PVector> active  = new ArrayList<PVector>();

  PVector first = new PVector(width / 2, height / 2);
  points.add(first);
  active.add(first);
  int gx = (int)(first.x / cellSize);
  int gy = (int)(first.y / cellSize);
  grid[gy * cols + gx] = 0;

  while (!active.isEmpty()) {
    int idx = (int)random(active.size());
    PVector pt = active.get(idx);
    boolean found = false;

    for (int attempt = 0; attempt < maxAttempts; attempt++) {
      float angle = random(TWO_PI);
      float dist  = random(minDist, minDist * 2);
      PVector candidate = new PVector(
        pt.x + cos(angle) * dist,
        pt.y + sin(angle) * dist);

      if (candidate.x < 0 || candidate.x >= width ||
          candidate.y < 0 || candidate.y >= height) continue;

      int cx = (int)(candidate.x / cellSize);
      int cy = (int)(candidate.y / cellSize);
      boolean ok = true;

      for (int dx = -2; dx <= 2 && ok; dx++) {
        for (int dy = -2; dy <= 2 && ok; dy++) {
          int nx = cx + dx, ny = cy + dy;
          if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) continue;
          int ni = grid[ny * cols + nx];
          if (ni != -1 && PVector.dist(candidate, points.get(ni)) < minDist)
            ok = false;
        }
      }

      if (ok) {
        grid[cy * cols + cx] = points.size();
        points.add(candidate);
        active.add(candidate);
        found = true;
        break;
      }
    }

    if (!found) active.remove(idx);
  }
  return points;
}

Space Colonisation for Tree Branching

The space colonisation algorithm (Runions et al., 2007) grows a skeleton by iteratively attracting branches toward attractor points. It naturally produces tree and river network shapes.

ArrayList<PVector> attractors = new ArrayList<PVector>();
ArrayList<Branch>  branches   = new ArrayList<Branch>();
float INFLUENCE_RADIUS = 120;
float KILL_RADIUS      = 15;
float SEGMENT_LENGTH   = 8;

void colonise() {
  // Find branches within influence of any attractor
  boolean grew = false;
  boolean[] attracted = new boolean[branches.size()];
  PVector[] dirs      = new PVector[branches.size()];
  for (int i = 0; i < branches.size(); i++) dirs[i] = new PVector(0,0);

  for (int ai = attractors.size() - 1; ai >= 0; ai--) {
    PVector attr  = attractors.get(ai);
    Branch  close = null;
    float   minD  = INFLUENCE_RADIUS;

    for (int bi = 0; bi < branches.size(); bi++) {
      float d = PVector.dist(attr, branches.get(bi).pos);
      if (d < KILL_RADIUS) { attractors.remove(ai); close = null; break; }
      if (d < minD)        { minD = d; close = branches.get(bi); }
    }

    if (close != null) {
      int bi = branches.indexOf(close);
      PVector dir = PVector.sub(attr, close.pos).normalize();
      dirs[bi].add(dir);
      attracted[bi] = true;
    }
  }

  for (int bi = 0; bi < branches.size(); bi++) {
    if (!attracted[bi]) continue;
    dirs[bi].normalize();
    PVector newPos = PVector.add(branches.get(bi).pos,
      PVector.mult(dirs[bi], SEGMENT_LENGTH));
    branches.add(new Branch(newPos, bi));
    grew = true;
  }

  if (!grew && !attractors.isEmpty()) {
    // Grow toward nearest attractor from tip of any branch
  }
}

class Branch {
  PVector pos;
  int     parent;
  Branch(PVector p, int parent) { this.pos = p.copy(); this.parent = parent; }

  void draw() {
    if (parent < 0) return;
    stroke(80, 50, 20);
    strokeWeight(1);
    PVector parentPos = branches.get(parent).pos;
    line(parentPos.x, parentPos.y, pos.x, pos.y);
  }
}

Full Example: Procedural Landscape

This sketch generates a heightmap, derives water from low-elevation cells, places trees via Poisson disc sampling weighted by elevation, and traces rivers from high points downhill.

final int  HM   = 257;
float[][]  h    = new float[HM][HM];
ArrayList<PVector> trees;
ArrayList<ArrayList<PVector>> rivers = new ArrayList<ArrayList<PVector>>();

void setup() {
  size(1024, 1024, P2D);
  noLoop();
  generateTerrain();
  normaliseHeightmap();
  placeTrees();
  traceRivers(6);
}

void draw() {
  drawHeightmap();
  drawWater();
  drawTrees();
  drawRivers();
  save("landscape.png");
}

void generateTerrain() {
  h[0][0] = h[HM-1][0] = h[0][HM-1] = h[HM-1][HM-1] = 0.5;
  float r = 0.65;
  diamondSquare(HM - 1, r);
}

void diamondSquare(int step, float r) {
  int half = step / 2;
  if (half < 1) return;
  for (int y = half; y < HM-1; y += step)
    for (int x = half; x < HM-1; x += step)
      h[x][y] = ((h[x-half][y-half]+h[x+half][y-half]+h[x-half][y+half]+h[x+half][y+half])/4)
                + random(-r, r);
  for (int y = 0; y < HM; y += half)
    for (int x = (y+half)%step; x < HM; x += step) {
      int cnt = 0; float s = 0;
      if (x-half>=0)  { s+=h[x-half][y]; cnt++; }
      if (x+half<HM) { s+=h[x+half][y]; cnt++; }
      if (y-half>=0)  { s+=h[x][y-half]; cnt++; }
      if (y+half<HM) { s+=h[x][y+half]; cnt++; }
      h[x][y] = s/cnt + random(-r, r);
    }
  diamondSquare(half, r * 0.5);
}

void normaliseHeightmap() {
  float mn=9999, mx=-9999;
  for (float[] row : h) for (float v : row) { mn=min(mn,v); mx=max(mx,v); }
  for (int x=0;x<HM;x++) for (int y=0;y<HM;y++) h[x][y]=(h[x][y]-mn)/(mx-mn);
}

void drawHeightmap() {
  loadPixels();
  for (int x=0;x<HM-1;x++) for (int y=0;y<HM-1;y++) {
    float v = h[x][y];
    color c;
    if      (v < 0.35) c = lerpColor(#1a3a6b, #2a5fa5, v/0.35);
    else if (v < 0.42) c = lerpColor(#d4b483, #c9a96e, (v-0.35)/0.07);
    else if (v < 0.70) c = lerpColor(#4a7c4e, #2d5a32, (v-0.42)/0.28);
    else if (v < 0.85) c = lerpColor(#8c8c8c, #707070, (v-0.70)/0.15);
    else               c = lerpColor(#e8e8e8, #ffffff, (v-0.85)/0.15);
    int px = (int)map(x, 0, HM, 0, width);
    int py = (int)map(y, 0, HM, 0, height);
    pixels[py * width + px] = c;
  }
  updatePixels();
}

void drawWater() {
  noStroke(); fill(30, 80, 180, 80);
  for (int x=0;x<HM;x++) for (int y=0;y<HM;y++) {
    if (h[x][y] < 0.36) {
      float px = map(x,0,HM,0,width), py = map(y,0,HM,0,height);
      float cw = (float)width/HM, ch = (float)height/HM;
      rect(px, py, cw, ch);
    }
  }
}

void placeTrees() {
  trees = poissonSample(18, 30);
  // Filter out water and high-altitude
  for (int i = trees.size()-1; i >= 0; i--) {
    PVector p = trees.get(i);
    int gx = (int)map(p.x, 0, width, 0, HM);
    int gy = (int)map(p.y, 0, height, 0, HM);
    gx = constrain(gx, 0, HM-1); gy = constrain(gy, 0, HM-1);
    float elev = h[gx][gy];
    if (elev < 0.43 || elev > 0.72) trees.remove(i);
  }
}

void drawTrees() {
  stroke(20, 80, 20, 140); strokeWeight(1.5); noFill();
  for (PVector t : trees) {
    int gx = constrain((int)map(t.x,0,width,0,HM), 0, HM-1);
    int gy = constrain((int)map(t.y,0,height,0,HM), 0, HM-1);
    float sz = map(h[gx][gy], 0.43, 0.72, 3, 8);
    ellipse(t.x, t.y, sz, sz);
    line(t.x, t.y, t.x, t.y + sz * 1.2);
  }
}

void traceRivers(int count) {
  for (int i=0; i<count; i++) {
    // Start from a random high-elevation point
    int sx, sy; int tries=0;
    do { sx=int(random(HM)); sy=int(random(HM)); tries++; }
    while (h[sx][sy] < 0.75 && tries < 500);
    ArrayList<PVector> river = new ArrayList<PVector>();
    int cx=sx, cy=sy;
    for (int step=0; step<300; step++) {
      river.add(new PVector(map(cx,0,HM,0,width), map(cy,0,HM,0,height)));
      if (h[cx][cy] < 0.36) break;
      // Find steepest descent neighbour
      int nx=cx, ny=cy; float lowest=h[cx][cy];
      for (int dx=-1;dx<=1;dx++) for (int dy=-1;dy<=1;dy++) {
        int tx=cx+dx, ty=cy+dy;
        if (tx<0||tx>=HM||ty<0||ty>=HM) continue;
        if (h[tx][ty] < lowest) { lowest=h[tx][ty]; nx=tx; ny=ty; }
      }
      if (nx==cx && ny==cy) break;
      cx=nx; cy=ny;
    }
    rivers.add(river);
  }
}

void drawRivers() {
  stroke(40, 120, 200, 200); strokeWeight(1.5); noFill();
  for (ArrayList<PVector> river : rivers) {
    beginShape();
    for (PVector p : river) curveVertex(p.x, p.y);
    endShape();
  }
}

// (Poisson disc sampling as defined earlier in the article)

Run the sketch and it saves landscape.png directly to the sketch folder — a complete procedural world ready for further layering.