Thursday, 19 November 2015

Seeded Map Generation

Seeded Map Generation

Been messing around with various hobby projects. The latest one, a Seeded Map Generator, I'm overjoyed to have implemented. There are a whole wealth of ideas I want to try out with this :D
One sentence summary: I can use this code to produce nice looking random maps of varying levels of detail with each map produced being connected to a fixed seed value, if you know the seed you can recreate the entire map!

A quick explanation of the techniques involved and an interactive demo are below the fold...

Pseudorandom Number Generation

Computers are deterministic devices, giving the same output for the same input every time. This means that to create random numbers akin to a dice roll or coin flip they need a source of randomness. A commonly used source is the internal clock time in milliseconds or smaller intervals. It changes so quickly that it  is essentially random. This is then inputted into an algorithm which returns a series of random numbers.

The default JavaScript Math.random() function does something like this but unfortunately doesn't let you set the initial value, the seed. If you could, then you could input the same initial seed and Math.random() would return the exact sequence of numbers every time it is reset.

This would be great functionality for creating maps as only the seed value needs to be stored in memory.  I experimented with creating my own function based on the multiply with carry method (I will most likely replace this with a more robust algorithm once I learn more about the subject). Wikipedia as usual will be my first point of research.

Perlin Noise

A random map produced by giving each square a random height would not look very good. It would end up looking like a mess of static. What is really needed is some way to have smoothly undulating hills and valleys where each square is a slightly different height to its neighbours. There are various algorithms that can produce this effect, one of the most popular is Perlin Noise .

It results in pleasant cloud-like patterns and is often seen in procedural textures or heightmaps in games (for example Minecraft). Now I am not completely certain how it operates but the algorithm allows you to compute a height at position x and it will be similar to the heights at position x-1 and x+1. The algorithm can be generalised to n dimensions so can create 3D shapes or have a shape smoothly transition over time.

A single instance of Perlin Noise on its own does not result in particularly interesting terrain, all the hills will be of similar width. By summing together multiple noise functions at different amplitudes and frequencies you can end up with fantastic fractal patterns which do a reasonable job of mimicking the patterns seen in real world terrain heightmaps.

Interactive Demo

Below is a random map generator where the seed value can be set or randomised. The map is produced with 8 instances of Perlin Noise each with half the amplitude and twice the frequency of the one before. Do have a play around with it and let me know what you think :D
Map Seed:

HTML5 canvas goes here

No comments:

Post a Comment