Height map generation in F# using midpoint displacement

Here is a simple program to generate some height maps. The maps can be generated to png files or txt files (as a serialized array).

Here’s the main program:

module TerrainGen

open System.Drawing

open HeightMap  
open MidpointDisplacement
open TestFramework
open Tests

let heightMapToTxt (heightMap:HeightMap) (filename:string) =
    let out = Array.init (heightMap.Size * heightMap.Size) (fun e -> heightMap.Map.[e].ToString())
    System.IO.File.WriteAllLines(filename, out)

let heightMapToPng (heightMap:HeightMap) (filename:string) =
    let png = new Bitmap(heightMap.Size, heightMap.Size)
    for x in [0..heightMap.Size-1] do
        for y in [0..heightMap.Size-1] do
            let red, green, blue = convertFloatToRgb (heightMap.Get x y) 
            png.SetPixel(x, y, Color.FromArgb(255, red, green, blue))
    
    png.Save(filename, Imaging.ImageFormat.Png) |> ignore

[<EntryPoint>]
let main argv =
    consoleTestRunner testsToRun
    let map = newHeightMap 8
    generate map 0.3 0.5
    heightMapToPng map "out.png"
    heightMapToTxt map "out.txt"  
0 

It uses two other modules. HeightMap which contains the height map type and the functions to work with this type. MidpointDisplacement which contains the algorithm proper.

module HeightMap

// contains the height map types and common functions that can be re-used for 
// different generation algorithms

type HeightMap = {Size:int; Map:float array} with     
    member this.Get x y =
        this.Map.[x * this.Size + y]      
        
    member this.Set x y value =
        this.Map.[x * this.Size + y] <- value

// returns a square matrix of size 2^n + 1
let newHeightMap n : HeightMap =
    let size = ( pown 2 n ) + 1
    {Size = size; Map = Array.zeroCreate (size * size)}  

// normalize a single value to constrain it's value between 0.0 and 1.0
let normalizeValue v =
    match v with
    | v when v < 0.0 -> 0.0
    | v when v > 1.0 -> 1.0
    | _ -> v

// converts a float point ranging from 0.0 to 1.0 to a rgb value
// 0.0 represents black and 1.0 white. The conversion is in greyscale 
let convertFloatToRgb (pct:float) : int * int * int =
    let greyscale = int (255.0 * pct)
    (greyscale, greyscale, greyscale)
    
// returns the average between two values    
let inline avg (a:^n) (b:^n) : ^n =
    (a + b) / (LanguagePrimitives.GenericOne + LanguagePrimitives.GenericOne)
    
// returns a floating number which is generated using bounds as a control of the range of possible values
let randomize (rnd:System.Random) (bound:float) : float =   
(rnd.NextDouble() * 2.0 - 1.0) * bound
module MidpointDisplacement

open HeightMap

// set the four corners to random values
let initCorners (hm:HeightMap) (rnd) =
    let rnd = System.Random()    
    let size = hm.Size   
    
    hm.Set 0 0 (rnd.NextDouble())
    hm.Set 0 (size - 1) (rnd.NextDouble())
    hm.Set (size - 1) 0 (rnd.NextDouble())
    hm.Set (size - 1) (size - 1) (rnd.NextDouble())
    
// set the middle values between each corner (c1 c2 c3 c4)
// variation is a function that is applied on each pixel to modify it's value
let middle (hm:HeightMap) (x1, y1) (x2, y2) (x3, y3) (x4, y4) (variation) =   
    // set left middle
    if hm.Get x1 (avg y1 y3) = 0.0 then 
        hm.Set x1 (avg y1 y3) (avg (hm.Get x1 y1) (hm.Get x3 y3) |> variation)      
    
    // set upper middle
    if hm.Get (avg x1 x2) y1 = 0.0 then
        hm.Set (avg x1 x2) y1 (avg (hm.Get x1 y1) (hm.Get x2 y2) |> variation)
    
    // set right middle
    if hm.Get x2 (avg y2 y4) = 0.0 then 
        hm.Set x2 (avg y2 y4) (avg (hm.Get x2 y2) (hm.Get x4 y4) |> variation)
    
    // set lower middle
    if hm.Get (avg x3 x4) y3 = 0.0 then
        hm.Set (avg x3 x4) y3 (avg (hm.Get x3 y3) (hm.Get x4 y4) |> variation)           

// set the center value of the current matrix to the average of all middle values + variation function
let center (hm:HeightMap) (x1, y1) (x2, y2) (x3, y3) (x4, y4) (variation) =
    // average height of left and right middle points
    let avgHorizontal = avg (hm.Get x1 (avg y1 y3)) (hm.Get x2 (avg y2 y4))
    let avgVertical = avg (hm.Get (avg x1 x2) y1) (hm.Get (avg x3 x4) y3)
           
    // set center value
    hm.Set (avg x1 x4) (avg y1 y4) (avg avgHorizontal avgVertical |> variation) 

let rec displace (hm) (x1, y1) (x4, y4) (rnd) (spread) (spreadReduction) =
    let ulCorner = (x1, y1) 
    let urCorner = (x4, y1)
    let llCorner = (x1, y4)
    let lrCorner = (x4, y4)
    
    let variation = (fun x -> x + (randomize rnd spread)) >> normalizeValue
    let adjustedSpread = spread * spreadReduction
    
    // the lambda passed in as a parameter is temporary until a define a better function
    middle hm ulCorner urCorner llCorner lrCorner variation 
    center hm ulCorner urCorner llCorner lrCorner variation
    
    if x4 - x1 >= 2 then
        let xAvg = avg x1 x4
        let yAvg = avg y1 y4
        displace hm (x1, y1) (xAvg, yAvg) rnd adjustedSpread spreadReduction
        displace hm (xAvg, y1) (x4, yAvg) rnd adjustedSpread spreadReduction
        displace hm (x1, yAvg) (xAvg, y4) rnd adjustedSpread spreadReduction
        displace hm (xAvg, yAvg) (x4, y4) rnd adjustedSpread spreadReduction
    
let generate hm startingSpread spreadReduction =
    let rnd = System.Random()
    let size = hm.Size - 1    
    
    initCorners hm rnd
displace hm (0, 0) (size, size) rnd startingSpread spreadReduction

The algorithm is pretty similar to diamond-square, in fact I have seen some people call it so, but it’s subtly different (in how to various sub-sections are divided) from the canon example, which is why I’m referring to it as midpoint displacement rather than diamond-square.

I’m pretty happy with the output of the results. It’s better than any map I have done before. Here is an example :

out

The code would need some optimization has it’s running out of memory fairly quick when generating larger maps.

You can find it as part of a larger repo on GitHub, that I have sadly abandoned.

Randomly generating a 2d RPG world

Randomly generating a 2d RPG world

This is a compilation of all my posts about using procedural content generation to create a random 2d RPG world.

The first step is to create a heightmap. This randomly generated bitmap will serve as the basis of the world map. Then we can convert this heightmap to our world map. Finally we can generate some random names for our map (world name, city names, etc.)

Filtered Twice
Height map

Create the heightmap

Generating heightmaps using particle deposition

Using Gaussian blurring on heightmaps

caves1
A remote mountain cave.

Create the 2d world map

Creating a random 2d game world map

Creating a random 2d game world map, Part 2: Adding rivers and lakes

Creating a random 2d game world map, Part 3: Cities, caves and snow

I had used an open source implementation of the A* algorithm to add roads between cities. Sadly, I have never written about it. But here is a link to the relevant code:

Adding roads to our world map

cities1
A city next to a river.

Generating random names

Algorithm to generate random names

A better algorithm to generate random names

snow1
A snowy island.

Finally here is a link to a Github repository where I had implemented these algorithms:

Gameproject Repo

Creating a random 2d game world map, Part 3: Cities, caves and snow

I have been continuing my 2d game world generator (part 1, part2) and I wanted to show you my progress so far.

This time I added small stuff that was simple to implement and didn’t require any special programming.

World name

A world name tag.
Heloist

I now name my worlds. To do so I use the code described in this post. Right now, I show my world name in the upper left corner in white letters.

Snow

A snowy island.
A snowy island.

Nothing fancy here, the top ~7% of the map is covered with snow, with the last row having a 50% chance to be covered in snow.

I ignore mountain and water tiles and just replace the other types of tiles with a snow tile. As for forest tiles, I replace them with a snowy forest tile.

Caves

A remote mountain cave.
A remote mountain cave.

To implement caves I select a random number of tiles which fit the following criterion:

  • must be a mountain tile
  • must be on the edge of a non-mountain region
  • must not be next to another cave
  • must have at least 2 mountain neighbor tiles in a radius of 2 tiles
  • must have at least 2 non-mountain, non-water neighbor tiles in a radius of 2 tiles

Cities

A city next to a river.
A city next to a river.

For cities I use the same technique as for caves, picking out random tiles that fit some criterion.

The criterion are pretty much the same, but I also add the criteria that a city must be within 2 tiles of a water tile. Real world cities are usually built near fresh or sea water so this adds a touch of realism.

Results

Here are the results from a randomly generated world, the world of Norgele.

A world map with snow, cities and caves.
A world map with snow, cities and caves.

Future improvements

As for future improvements, the next step would be to add some roads to connect the different cities together. For this I have been thinking about using A* with each type of terrain having a different weight for how difficult such a terrain would be to cross.

Creating a random 2d game world map, Part 2: Adding rivers and lakes

Creating a random 2d game world map, Part 2: Adding rivers and lakes

A while back I published a post about how to go about creating random 2d game world maps. I was looking to create something that could be used for a game similar to those old Might and Magic games.

In my first post, I posted an image of a generated map that went like this:

World created using a heightmap

Since then, I improved my maps and I also added some rivers and lakes.

To create rivers and lakes, I created a river filter. Since my height maps were already accepting filters for my Gaussian Blur filters I used the same underlying mechanic.

Here’s my filter method on my heightmap:

# Return a new height map, created by using the filter parameter on the current height map
def filter(filter)
	filtered_height_map = HeightMap.new
	filtered_height_map.load(filter.filter(@data), @size_x)
	return filtered_height_map
end

This returns a new heightmap which has been filtered by the parameter.

River filter

rivers_and_lakes1

To create the river filter, I create a new height map which I call a rain map. This is a normal height map, but instead of interpreting the values as the height of the terrain, we simply interpret them as the quantity of water that fell over an area. The rain map is of the same size as my height map, which means I can superimpose the two to find out where rain has fallen on my generated world.

In the river filter I use a rain level threshold. Wherever it has rained sufficiently to go over that threshold value, I will use that spot to start a river/lake.

If you are using the height maps parameters from my post on generating heightmaps here are the configuration values I am using for a 80×80 rain map.

  # 80 x 80
  RainMap_medium_world = Proc.new do |height_map|
    height_map.number_of_drop_points = 30
    height_map.min_particles = 400
    height_map.max_particles = 800
    height_map.number_of_passes = 4
    height_map.particle_stability_radius = 1
  end

There is no need for the particles to cover the whole map as we are only interested in knowing the places where it has rained a lot. We can thus save time by using configuration values to generate a few heavy spots of rain (lighter spots of rain wouldn’t have crossed the rain level threshold anyway and would have been ignored).

This is a sample 80×80 rain map:

rain_map

Note that I use a single pass of Gaussian filter blurring on my rain maps.

To get similar results on larger maps calculate the difference in total pixels of the larger height map and modify the number_of_drop_points, min_particles and max_particles by that factor.

Starting points for rivers

rivers_and_lakes2

In my implementation of the river filter, I decided to only start rivers in mountains where a sufficient rain threshold had been achieved. This way all my rivers are coming down from mountains.

The first step is to find the different river starting points. It is best to leave out some spaces between each starting point to make sure we do not cover too much of the map with our rivers.

# superimpose rain map with array (normal height map) to choose river locations
    (0...@size).each do |y|
      # @size is used since we assume the array is square 2d matrix
      (0...@size).each do |x|
        if filtered_rain_map.data[x + y * @size] >= 80 && filtered_array[x + y * @size] >= 68 &&
            river_starting_points.none? {|p| (p[0] > x - 4 && p[0] < x + 3) &&
                                             (p[1] > y - 4 && p[1] < y + 3)}
          river_starting_points.push([x, y])
        end
      end
    end

In this last code sample my river threshold is at 80 and I added the additional condition that my height map height should be at 68. For reference, when creating a world, I consider height values of 70 and up as mountains. After some experimentation, I ended using a slightly lower value (68). Not only does it allows for rivers to start next to mountains but the overall result is more pleasing.

Creating river paths

Now that we have our starting points we can create river paths. We need to store those river paths inside arrays. Once we have all our river paths in memory we can dig the rivers afterwards. If we dig our rivers as we go, it will be difficult not to keep going back into spots we have already dug.

The system to create river paths uses a “find lowest neighbor” method to find out where the river should be flowing next.

When finding our lowest neighbor we must skip our current location, of course, and the pixels in diagonal. Because diagonal rivers look really unnatural when converted into 2d tiles.

The following picture illustrates with check marks which pixels must looked at to find the lowest neighbor.

findLowestNeighbor diagram

By always choosing the lowest neighbor we end up following a path as such:

River path illustration

Of course a more realistic river filter would fill up all adjacent pixels up to a certain level with water. In this last picture, with a more realistic system, the pixel with a value of 55 would get filled before the one with a value of 65. While this would make for a more realistic simulation of rain accumulation, we do not need to go this far unless we actually wish too.

You will still get broad rivers and lakes with the former approach when you have groups of even pixels next to each other.

rivers_and_lakes3

You stop your river path when you reach a body of water.

Digging the rivers

Once all your river paths have been generated independently, you can dig rivers by replacing the pixels on the river paths with 0 (or what ever value you use to signify water).

Results

Here is a full world map which uses the technique described above to create rivers and lakes:

World created using a heightmap and rain map

Furthermore, the existing rain map could be used for other purposes, like creating biomes. A lower altitude area that didn’t get any precipitations could become a desert, while another which got a lot of precipitations over a large flat expanse could be turned into a swamp.

That’s all for now. Keep tuned for other posts on creating a random 2d world in the future.

UPDATE: I published a part 3 to this article: Cities, caves and snow.