Procedurally Generating Islands

My first shot at generating an island didn’t go well. Here’s what it looked like:

I was happy with it, nonetheless, but over the next 24 hours I would go on to learn a whole host of new techniques that would turn my poor excuse for an island into something that actually looked like an island. This post will follow my journey from nothing to something.

My first island used a very simple technique:

1. Fill a 2D array with a radial gradient
2. Apply perlin noise to the gradient
3. Paint the square based on the value in the cell of the array

This is how we got here.

To fill the 2D array I had kind of figured out my own little algorithm but I was really going about it the wrong way, we’ll see the right way later, but my mistakes turned into lessons and we’ll have to look at the mistake first to learn the lesson later.

My method was to draw concentric circles around the center of the grid. So to start I needed to find out how one finds a point on a circle, it turns out it’s quite simple:

x = centerX + radius * Math.cos(angle);
y = centerY + radius * Math.sin(angle);

Where centerX and Y are the center coordinates of the circle.

We then loop this to fill in each point of the circle. So, logically, with 360 degrees in a circle, we want to loop 360 times, with the angle starting at 0 and increasing by 1 each time.

while(angle < 360) {
    x = centerX + radius * Math.cos(angle);
    y = centerY + radius * Math.sin(angle);
    angle++;
}

This will draw 360 points that will join up into a circle. The next step is to figure out how to draw a slightly smaller circle. Simple answer: reduce the radius.

radius = 200;
maxRadius = 200;
while(radius > 0) {
    while(angle < 360) {
    x = centerX + radius * Math.cos(angle);
    y = centerY + radius * Math.sin(angle);
        array[x][y] = maxRadius - radius;
        angle++;
    }
    angle = 0;
    radius--;
}

This will now draw circles, slowly decreasing inside, towards the center of the array.

The only issue with this algorithm, is that it leaves gaps. When I use the points that I’ve calculated on I get a gradient that looks like this:

We can see the gaps in here, and when we draw our island it’s going to end up leaving gaps.

So when I did draw the island using these values, I was left with lots of little gaps, I then decided that to fix these gaps I would just make the squares that I drew bigger and they’d merge together, but all I got was the original image I tried a few other things like playing with the noise algorithm, thinking maybe that had something to do with it and reducing the increment of my angle based on how large the outer circle was, but didn’t have much luck with either. So, I took to the internet and I found a very helpful person, and they taught me the following things.

The first step was to figure out how to generate a gradient without gaps. I was informed that by going pixel by pixel over the array and calculating the distance to the middle, I would get a nice smooth radial gradient without gaps. I had already tried this approach before and I had only received a weird, square shape, that’s not what I wanted, but I then read that I had been calculating the manhattan distance to the center with this algorithm:

xDistance = Math.abs(centerX - x);
yDistance = Math.abs(centerY - y);
distance = xDistance + yDistance;

What I actually needed was the euclidean distance to the center. I was having flashbacks to high school, I had to use Pythagoras, for an actual real life application. I couldn’t believe it.

xDistance = Math.pow(Math.abs(centerX - x), 2);
yDistance = Math.pow(Math.abs(centerY - y), 2);
distance = Math.sqrt(xDistance + yDistance);

This produced a beautifully smooth radial gradient, I was so happy. I had actually spent a good few hours trying to implement a radial gradient and the maths just broke my head for some reason. I just needed to sit down and break the problem down, explain what I was doing to someone and then figure out a track from there.

My nice smooth gradient felt like a huge win, even if it looks like nothing, I was so happy with it.

Now it was time to go back to what we were doing before, we wanted to apply the noise and then draw an island.

First I applied the noise and got this:

Then I culled the edges, basically only drawing cells with values over a certain threshold:

And then finally I added a bit of colour, using the values in the array to decide which colour should be drawn

I finally had something that almost resembled an island. It wasn’t quite there but we were getting somewhere finally.

The next few hours were spent playing with my noise algorithm, figuring out how the hell to make it less sharp, and make my island actually look like one contiguous landmass.

All I could do was make the edges more or less noisy. I still just had a flat set of circles, it didn’t look much like an island at all. Back to playing with noise.

I finally stumbled on something, this was all a bit of a blur, I was using a perlin noise library and I eventually figured out that if I combined two levels of noise I could make something like this.

It was at this point that someone who had seen my code pointed out that it looked like I was getting my noise pixels incorrectly. Since the noise was in a 1D array and my map was a 2D array, I had to translate that, and I was doing it wrong.

terrain[x][y] -= noise[x * 800 + y]

I was referencing the noise horizontally rather than vertically.

I needed to access it like this:

terrain[x][y] -= noise[y * 600 + x]

It was a simple fix, although I didn’t actually implement it as I was far more concerned with something else. Even if I did manage to place it, my island was going to look like a circle still. I needed to distort it somehow.

I continued playing with different layers of noise, and eventually I got this:

That was cool, but I still had a few issues with it:

1. It was still a circle
2. It still had weird horizontal lines
3. Someone pointed out that it looked really flat

So, since it looked flat I needed to do something about it. The very nice person on the internet who was guiding me this entire time explained that I could implement some shading, so that was the next step.

At this point, I was using a library called PIXI to do my drawing, it took hex values for colour, which was all very well and good, until shading came into the equation. I spent a good few hours struggling with shading, trying to convert between string, ints and hex values and calculate differences between them. It was horrendous, but I finally got somewhere.

I managed to implement a basic shading algorithm, if the cell closer to the light source is ‘higher’ up, then the current cell needed to be shaded, and would simply be slightly darker than the normal shade for it’s height.

I had also changed my noise algorithm further at this point, so we had a different shape of island.

I then went on to multiply the shade, so the lower it was, the darker it got.

This looked cool, but the lighting on the bright side of the hills looked really flat, so I went a step further and attempted to shade both sides of the hills.

This really didn’t look that good at all, it almost looked like plastic. I needed to take a different approach, and dealing with hex values wasn’t helping. It had been suggested to me earlier that I ditch the library and just draw with raw JS, and that’s exactly what I did.

The next few hours was turmoil, why wouldn’t it just work, I didn’t understand what was going on, my code was broken, it just wouldn’t draw and I didn’t even get the slightest hint at an error from my dev console.

for(var x = 0; x < 800; x++) {
    for(var y = 0; y < 600; y++) {
        var colour = getColour(terrain[x][y]);
        imageData[(y * 800 + x) * 4] = colour.r;
        imageData[(y * 800 + x) * 4 + 1] = colour.g;
        imageData[(y * 800 + x) * 4 + 2] = colour.b;
        imageData[(y * 800 + x) * 4 + 3] = colour.a;
    }
}
context.putImageData(imageData, 0, 0);

I had virtually copied the code right from the Mozilla docs, but my canvas was not drawing, and I didn’t have any errors. I thought I had lost my island. I was so sad, then, suddenly, I noticed something.

I had a line printing into my JS console in Chrome. I had just told my drawing script to print my imageData object. It hit me like a speeding truck:

ImageData object, with data as one of it’s members. I needed to access the damn data array, not the object, the simplest change to my code and hours of frustration were suddenly solved:

for(var x = 0; x < 800; x++) {
    for(var y = 0; y < 600; y++) {
        var colour = getColour(terrain[x][y]);
        imageData.data[(y * 800 + x) * 4] = colour.r;
        imageData.data[(y * 800 + x) * 4 + 1] = colour.g;
        imageData.data[(y * 800 + x) * 4 + 2] = colour.b;
        imageData.data[(y * 800 + x) * 4 + 3] = colour.a;
    }
}
context.putImageData(imageData, 0, 0);

I finally had values that could be measured on a scale of 0-255 for my colours, and it drew a whole lot faster than before. I was waiting up to 30 seconds for PIXI to draw my islands before, now I was waiting 10 at most.

Time to add shading:

for(var x = 0; x < 800; x++) {
    for(var y = 0; y < 600; y++) {
            hillshade = terrain[x][y] - terrain[x - 1][y];
            hillshade = 1 + hillshade * 10000;
        }
        var colour = getColour(terrain[x][y]);
        imageData.data[(y * 800 + x) * 4] = colour.r + hillshade;
        imageData.data[(y * 800 + x) * 4 + 1] = colour.g + hillshade;
        imageData.data[(y * 800 + x) * 4 + 2] = colour.b + hillshade;
        imageData.data[(y * 800 + x) * 4 + 3] = colour.a;
    }
}
context.putImageData(imageData, 0, 0);

My other issue was that it still had those weird horizontal lines on it, they were nasty, I needed to fix it. Time to re-think. I ended up finding a new library using a different noise algorithm. I moved over to something called OpenSimplex noise that I had read was quite good and that I should be using over Perlin, so I moved over to that.

Finally, I managed to draw something, with shading, that didn’t have horizontal lines and actually looked like it might be an island.

The only thing left annoying me was that the damn thing still looked like a circle.

After fiddling around for a bit I finally figured out that I could change my initial radial gradient into a differently shaped gradient by changing the distance calculations. Instead of figuring out the squared distance of each point I calculated the distance of each point by 2, minus a random number in the range 0 and 2.

That gave me this:

It was an actual island looking thing, and it randomly generated, and it looked awesome. We have reached the end of the journey, I’m going to take this knowledge forward and build out things on top of these islands, and I’m really looking forward to learning more about procedural generation.

This has been a wonderful adventure, and the difference between what I had 24 hours ago and what I have now is astounding.