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.

A better algorithm to generate random names

In October I published a post about an Algorithm to generate random names. If you came here looking for a way to generate random names, I suggest you go read that post, skim over the source code and then later come back here for the much better version.

The program worked in two parts, a script to generate probability tables and a class called RandomNameGenerator. The script was quickly thrown together. I wanted to save time since this was a small part of a larger project.

When it came time, months later, to add more features and correct some bugs I quickly regretted my decision to “quickly throw together” a script to generate the probability tables. The whole thing was hard to understand and extend. The version I was working with was more involved than what I had originally posted, and using a simple script wasn’t cutting it any more. I had fallen into the proverbial “working fast but taking much more time in the end” trap.

So I started the whole thing over using test-first BDD, OO principles and applying care to my work. In not much more time than it took me to write the first version I had a working second version with the features I wanted and I got rid of the bugs that were bugging (pun intended) me.

I put the whole thing on GitHub so you can go there for the source code and to get a working copy.

I have included some sample data to use to generate names. It’s under the /media directory and it uses names from Greek mythology (all taken from Wikipedia).

There is a small program called fix_sample.rb that will try to convert a sample file to the desired format. The sample is expected to be in following format:

firstName secondName thirdName

Which is a space-delimited plain text file that starts and ends with a space.

The tests are found in the /spec directory.

A sample program, random_name_generator_test.rb provides a sample usage of the program for those who want to know how to call it.

Since this test program is very small I’ll reproduce it here in it’s entirety:

require_relative 'random_name_generator'

generator = RandomNameGenerator.new("media/greek_myth_sample")

puts "Generating 40 names"
40.times {puts generator.generate}

This test program will generate 40 random names and output them to the console, that’s all there is to it.

Here is a sample output:

Ados
Heria
Zeusa
Lestia
Caemis
Catosesos
Hersa
Amede
Meliasa
Kraera
Celespa
Anyssa
Demine
Agra
Uros
Dikia
Arcos
Hemesiste

Take care.

Creating a random 2d game world map

Creating a random 2d game world map

I wanted to create a program that generates a random 2d world map. Like one you would find in old rpg video games. This got me to investigate the wonderful world of procedural content generation.

The word random is used here to mean that the map will be created using a certain amount of randomness so as to get a different map every time we generate one.

Using totally random data would just create a bunch of noise. I generated a map using totally random data to show you what I mean.

Random world generated using pure random numbers

I looked into how to create random 2d worlds. My research on Google led me to pseudo-random number generation and Perlin noise. I quickly realized this wasn’t the path I wanted to investigate.

I wanted to share with you the solution I adopted. It’s easy to code and powerful. I ended up generating a heightmap. These are primarily used to create 3d worlds, but when you think about it, it’s even easier to use them for a 2d world by applying some sort of filter on the height values of the map to convert them to 2d tiles. Here is some code that uses an already generated heightmap, of exactly the same kind you would use for 3d graphics, and turns it in a 2d world map.

require '../map'
require '../tile'
require './height_map'

class WorldMap < Map	
	def initialize(width, height, height_map)
		super(width, height)		
				
		(0...width).each do |x|
			(0...height).each do |y|
                # If the tile is on the edge of the map I select a water tile whatever the results. This is because I absolutely wanted to create an island. If this is not your goal you can forgo this.
				if edge_of_map?(x, y)
					terrain = :water
				elsif height_map[x + y * width] == 0
					terrain = :water
				elsif height_map[x + y * width] >= 70
					terrain = :mountain
				elsif height_map[x + y * width] >= 1 && height_map[x + y * width] <= 2
					terrain = :sand
				elsif height_map[x + y * width] >= 30 && height_map[x + y * width] <= 60
					terrain = :forest
				else
					terrain = :grass
				end
				
				@tiles[x + y * width] = Tile.new(terrain, x, y)
			end
		end
	end			
end

This will allow us to generate something like this:

World created using a heightmap

Bear in mind that these are preliminary results. I still have much work to do on the height map generator to get the kind of results I am looking for.

Generating a heightmap is actually pretty simple. You can look up my two previous posts on the subject for more information.

Generating heightmaps using particle deposition
Using Gaussian blurring on heightmaps

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

Algorithm to generate random names

I recently wanted to create an algorithm that could generate random fantasy names. The goal was to have the algorithm produce a new random name each time it was called.

Returning a random “normal” name is pretty easy (ie: John, Robert, Stacy). You just take a big list of names (like from the US census) and draw one out at random.

If you rather want to create some made-up name, like one you could find in a fantasy novel, video game or sci-fi movie and you want it to be random, then you need to use an algorithm.

Here is a sample of random male fantasy names generated with the technique I will describe:

Ealst
Fara
Riond
Cuserion
Staran
Melenorno
Ennamit
Inele
Carau
Anbolod
Andockeff
Belagu
Fresp
Aronduste
Kemal
Fanda
Gaurio
Dersta

Overview

Stringing random letters together would give you something like: “dkwidfjwz”, which isn’t very convincing.

The proper technique consist of parsing a text file to create probability tables. These indicate the probability of a letter following another letter. Something that says the letter A has 50% chance of being followed by E and 50% of being followed by F.

While you could take existing letter probability from the English language, it is very important that make your own probability tables created from your own sample data. Otherwise you won’t get good names from your output. This is because standard probability tables are made using common names rather than proper names.

Building your probability tables

This simple script was rapidly thrown up together and won’t win me any awards for coding style but it will show you how to generate a two letter pair probability table.

# simple scripting to generate probability tables from a file

# PARAMETERS
# this script takes two parameters, the first is the input file 
# and the second is the output file

require "yaml"

input_file = ARGV[0]
output_file = ARGV[1]

# treat all letters as well as spaces
chars = ('a'..'z').to_a.push(' ')

last_char_read = " "
frequencies = Hash.new(0.0)

# parse the file to read letter pair frequencies
File.open(input_file) do |file|
	while char = file.getc
		if ('a'..'z').to_a.include?(char.downcase)
			if chars.include?(last_char_read.downcase)
				frequencies[last_char_read.downcase + char.downcase] += 1
			end
		end
		
		last_char_read = char
	end
end

# get the total count of each single letter
letter_total_count = Hash.new(0.0)
frequencies.each {|key, value| letter_total_count[key[0]] += value}  
letter_total_count[frequencies.keys.last[1]] += 1

# the final hash will contain our, ahem, final result
final = Hash.new(0.0)
frequencies.sort.each {|key, value| final[key] = (value / letter_total_count[key[0]])  }  

# make a running total 
chars.each do |first_letter|
	running_total = 0.0

	('a'..'z').each do |second_letter| 
		if final.key? first_letter + second_letter
			original_value = final[first_letter + second_letter] 
			final[first_letter + second_letter] += running_total
			running_total += original_value
		end
	end
end 

# output to file for later use
File.open(output_file, "w") {|file| file.puts YAML::dump(final)}

Here is a partial sample of what is being generated in the output file:

ba: 0.21774193548387097
be: 0.5403225806451613
bi: 0.5887096774193548
bl: 0.6129032258064515
bo: 0.814516129032258
br: 0.9274193548387096
bu: 0.9919354838709677
by: 1.0

As we will see in the Improvements section, this basic script can be improved upon to get better results.

Generating the random name

To generate a random file from such a file you basically generate a random number from 0.0 to 1.0 and get the corresponding letter.

Here is how you could generate a random name:

require "yaml"

class RandomNameGenerator
	def initialize	
		@random_number_generator = Random.new 
		@probability_tables = YAML.load_file('your_data_file_name_here')
	end
	
	def generate
		name = get_next_letter(' ')
		
		@random_number_generator.rand(4...10).times do			
			next_letter = get_next_letter(name[name.length - 1])
			
			while next_letter == name[name.length - 1] && next_letter == name[name.length - 2]
				next_letter = get_next_letter(name[name.length - 1])
			end
			
			name += next_letter	
		end

		return name
	end

private
	def get_next_letter(current_letter)	
		random_number = @random_number_generator.rand(0.0..1.0)
		
		@probability_tables.select {|k, v| k[0] == current_letter && 
		 	  															 v >= random_number}.first[0][1]
	end 
end

If you are using Ruby 1.9.2 or above, use the new Random class and reuse an instantiated object rather than creating a new for each “roll”. This way your results will be much more random. (Detailed explanation here)

Sample data

To get better results it is important to have good sample data. I can’t stress that enough. You need to give some thought about what to put in the file you will parse.

Consider the following points:

  • The source of your data: If you create your sample data using names from Lord of the Rings, expect to get names similar to those in Lord of the Rings. Your data should have a single or a very limited number of themes.
  • Sample size: A good sample size is important to get variability.
  • Sample representativeness: Your data sample should be representative. Your data should include rare letter combinations, but these should be infrequent. Think about how frequently you want certain letter combinations to come up and reflect this in your sample data.
  • Many samples: Be sure to use different samples for men, woman, places or different themes.

Improvements

My current program is more complex than what I have shown you here but I have a feeling this post is already far too long. I should really keep my post shorter if I want people to read them. For brevity I didn’t go in all the gory details but hopefully what you have here will get started on the correct path.

Here’s what to do next:

  • Generate both two letters pairs and three letters triplets in your probability tables.
  • Favor using triplets in your random generator but have pairs as a fallback when needed.
  • Instead of using a random value for name length, use a normal, Cauchy or Gaussian distribution to get name length. You could also build an average name length from your sample data.
  • Prevent long repetition of a single letter in output results (ie: Maeeeel). This is much less of a problem if you are using triplets.

Hope you have fun with all of this!

UPDATE: I have created a better version of this algorithm. You can find it here on GitHub and I also made another post, A better algorithm to generate random names that contains explanations. This post still contains useful complementary information that should be read first.