›

Random River Generation

bigbadwoflbigbadwofl
edited in General
Not sure where to post this so please excuse if this is the wrong forum. I wrote a little tutorial on generating random-things-that-are-sort-of-straight-but-not-too-straight-or-it-would-look-corny today (don't worry the actual post has a much more succinct name).

Originally I thought of using cubic splines with random distances between vertices but this way seemed much cooler (if a bit overkilley).

You can read it here.

Comments

  • hermantullekenhermantulleken
    edited
    Very cool application of both Perlin noise and A* :)

    It may be a bit overkilly for rivers, but the algorithm (with a tiny modification) is at the heart of two very useful texture manipulation algorithms: seam carving (a seam is simply the best "river" on on the derivative of an image from top to bottom) and image quilting (where the quilt-seam is simply the best "river" on the difference of the two images where they overlap, offset by one pixel in the one image). Quilting, especially, is useful for generating seamlessly tillable textures. You should try it out.

    A* and it's siblings (each field of study give their one names) is probably one of the most useful algorithms.

    (The tiny modification is just to leave the source and target open to be calculated, instead of specified).

    What version of Perlin noise did you use? I notice some straight sections in the river, which implies seams in the noise, which may either be a feature of the algorithm (which can usually be fixed very easily), or a bug [Edit: these stupid smileys must really go away now; they hinder communication. What I meant was * skeptical smiley*.]
  • bigbadwoflbigbadwofl
    I'm not sure which version I 'used'. It's based on my JavaScript port of the C++ version I wrote a few years ago. The straight sections are actually likely due to how I implemented my A* (some cheating involved to make it faster for the web). but it could also be due to a little hack I used for my Perlin implementation to cater for an annoying little nuance of how JavaScript stores numbers (bitwise that is).

    Thanks for checking it out! The topics you mentioned seem extremely interesting and I'll definitely be reading about it soon.
  • creative630creative630
    edited
    Not strictly the same/appropriate for rivers but for interest sake, there is also another algorithm which came to mind along the same lines as Image Quilting using graphcuts. It finds the path that cuts minimally between two overlapping images to give the best blend between them.
  • DeepFreezDeepFreez
    Here is a bit of a modification to your approach.

    Instead of pre-generating the whole random field (most of which will not be used) just call your perlin/simplex/other noise function when needed to calculate your cost function. One of the nice features of A* is that it effectively caches the expensive calculations, and only does the ones it needs.

    I have not coded this out, just so you know :p

    An interesting application of this approach that I want to try in one of my projects is to create roads on an existing height map. Here is how I see it happening:
    - Pick points A and B
    - Get the average height between them (m)
    - As noise map, use abs(noise(x,y) - m). This gives the average contour on the map a weight of 0.

Sign In or Register to comment.