Friday 31 January 2014

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.

1 comment:

Bill Tavis said...

Awesome post! The way you colored the pixels was the key to the puzzle... I was looking for just this type of thing... I also looked at the accumulated blurs article, and after trying it myself I realized it is doing the same thing as a 1/f filter in the Fourier domain... So instead of waiting and waiting for several large blurs to accumulate you can just take your beautiful aggregate and apply this filter and you will nearly instantly have a landscape out of it with the exponent controlling the roughness. see http://paulbourke.net/fractals/noise/ for more. Instead of starting with white noise though, you start with the DLA just as you displayed it here, and it works! And the fact that you used cyclic boundaries works perfectly with the FFT!