Voxel heightmap, dla

I've been mucking about a bit with the voxel stuff some more, trying some terrain generation. I first cooked up something from memory but it wasn't correct, tried perlin noise but wasn't really happy with it and then I came across this post about terrain generation using Diffusion Limited Aggregation (DLA) to generate mountain ranges.

Partial solution.

And the final result of the basic DLA. This version is cyclic.

The basic algorithm is very simple:

  Node[] nodes;  // grid of nodes
  int[] map;     // grid of points
  randomly seed Ns locations in nodes
  total = Ns;
  // until all locations are visited
  while total < width*height
    x = random(width);
    y = random(height);
    if (nodes[x,y] != null)
       continue;
    fi
    // randomly walk until something is hit
    while !hit
      // save location we came from
      lx = x;
      ly = y;
      // walk to next location
      (x,y) = randomly move by 1 cell in a compass direction
      if (cyclic)
        x = x & (width-1);
        y = y & (height-1);
      else if (out of range)
        break;
      fi
      // check for attachment point
      n = nodes[x,y]
      if (n != null)
        hit = true;
        total += 1;
        n = new node(n, lx, ly);
        nodes[lx,ly] = n;
        n.visit(map);
      fi
    wend
  wend

Where:
Node {
  Node parent;
  int x, y;

  void visit(int[] map) {
    map[x,y] += 1;
    if (parent != null)
      parent.visit(map);
  }
}

I'm then showing log(map).

It certainly has some nice 'erosion' like shapes, and can also make some nice lightning. I also experimented with something based on physical erosion but that didn't really pan out.

This algorithm grows the seed points like a crystal and because the search space is quite big is rather slow to get going on larger images. Although it really races to the end (the first image above was about 15 seconds in, the second was 2 seconds later). I tried a few variations to speed this up:

Using random line segments

This is much much faster but the result has fewer "fiddly bits" and is more strung out.

Randomly choosing an existing node from which to grow a new point

This is faster at the start but slows down as it starts to randomly choose nodes which have no where to go. It also produces a more regular shape more akin to mould growth; which is not really very mountainous.

It might be possible to play with how it chooses the growth points with this one, both to speed it up and tune the shapes it generates. I've experimented a little bit but didn't have much luck so far.

Unfortnately the pixel-scale of everything is a bit too detailed so I need a way to scale it up without losing the intricacies. I haven't tried the accumulation of multiple blur radii from the link above yet. That should be able to upscale at the same time too.

But yeah, right now it just isn't grabbing me enough to really get into it - but then again nothing is atm. Blah.