Maze Generation Algorithms - Recursive Backtrack

11 May, 2017

I have recently been playing around with the idea of generating mazes. This is mostly due to the tower defence game I am working on and generating mazes is a very interesting topic. I have decided to start by implementing the Recursive Backtracker algorithm as it seemed both easy to implement and I like the mazes produced by it. By far the best resource I found while learning about mazes was a blog by Jamis Buck and his book “Mazes for Programmers”.

 

You can see my implementation of the Recursive Backtracker algorithm below.

Maze Seed:


Regenerate

The code is all on my Github

Procedurally generating a solar system

27 April, 2017

Procedural generation has always been of interest to me, and solar systems are cool. So I decided to explore procedural generation by procedurally generating a solar system! Below is a solar system that has been generated based on a pseudo random seed. Below is an example of a generates Solar System. Refresh the page for a new randomly generated Solar System! click Here for a full screen version that is not scaled down and looks nicer!

 

To procedurally generate anything we first need a seed to base our generation on. We will seed the random number generation to our seed. Once we have a seed the rest of the generation will be based on this. This means that the same seed will always generate the exact same solar system, so if there is a solar system that is particularly nice the seed can be saved to re-generate the exact same solar system at any given time. I have written this in HTML5 using the phaser framework and thus my code to generate and set a random seed is as follows:

Math.seed = Math.floor(Math.random() * (89898989898989898989 - 29898989898989898989 + 1)) + 29898989898989898989;

Where Math.seed is the value that we will use as our unique seed.

Math.randomSeed = function(max, min) {
    max = max || 1;
    min = min || 0;
    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;
    return min + rnd * (max - min);
}

Math.randomSeed is the random function that we will use to generate pseudo random numbers based on the seed generated and stored in Math.seed. Of particular note is:

Math.seed = (Math.seed * 9301 + 49297) % 233280;

This is a general math equation to generate pseudo random numbers, more info on this is available at: http://stackoverflow.com/questions/33716998/why-does-seed-9301-49297-233280-233280-0-generate-a-random-number

Once the seed is generate we can begin to generate our solar system. Our solar system consists of 4 elements: The sun, Planets, Moons and Stars. Each of these are generated based on the seed. Some things like the planets are affected by the sun that is generated. Due to this we must generate the solar system in the following order:
Stars – only affected by the seed
Sun – only affected by the seed
Planets – Affected by the heat of the sun and distance from sun. More on this later
Moons – Affected by the distance from the planet and the climate of the planet
We will look at how each element is generated.

 

Generating the stars

The stars are probably the easiest to generate as the stars are based on per-defined images. There are 9 possible images that will be used for the stars, they are all similar with a slightly different layout:

undefined

The image to be used is chosen at random based on the seed:

  this.type = parseInt(Math.randomSeed(1,10));
  this.sprite = game.add.sprite(960, 960, 'stars'+ this.type);

Once one of the 9 images is chosen we set a random rotation for it in 90 degree intervals.

  this.sprite.anchor.setTo(0.5,0.5);
  var rotation = parseInt(Math.randomSeed(1,5));
  this.sprite.angle = rotation*90;

In doing this we get a total of 36 different possibilities for the layout of the stars as each of the 9 images have 4 different possible rotations.

 

Generating the Sun

The Sun is the core of the solar system and will have an effect of every planet and moon that is generated. To generate the Sun the first thing we need to do is define all the properties that a sun has. For this project I decided a sun was determined by its Type, Size, Heat and Sprite. In this case Type is an arbitrary value to add some extra variation. Size is pseudo random and Heat is based on both the Type and Size of the sun. These 3 values are set using our random function defined earlier.

	this.type = parseInt(Math.randomSeed(1,6));
	this.size = parseInt(Math.randomSeed(1,9));
	this.heat = (this.size*this.type*5)+30;

The last thing we need to do is set a sprite for the sun. The sun much like the stars have a pre-defined set of images that can be used:

undefined

However the sprite that is chosen to represent the sun is based on the sun type and as a result also corresponds to the heat of the sun:

this.sprite = game.add.sprite(10, 10, 'sun'+this.type);

 

Generating the planets

Much like the sun to generate planets we must first determine all the properties that make up a planet. I decided each planet should have a Size, Distance, Water Level, Speed, Temperature, Climate, Name and Sprite. Each value is determined based on the Seed and also often the Sun that has been generated.

The Size, Distance and Water Level are based only on the Seed:

	this.size = parseInt(Math.randomSeed(1,4));
	this.distance = parseInt(Math.randomSeed(3,9));
	this.waterLevel = parseInt(Math.randomSeed(1,10));

The Speed is based on both the Seed and Distance:

	this.speed = (parseInt(Math.randomSeed(10,25)))-this.distance;

The planets temperature is base on the Seed, Heat of the Sun and Distance from the sun:

	this.temp = this.sunHeat – (this.distance*8);

The climate is based on both the Water Level and Temperature of the planet. I wrote a separate function to work out the climate of the planets based on these values.

planetClass.prototype.getClimate = function(water, temp){
	var climate;
	if(water < 4){
		if(temp < 1){climate = "plains"}
		else if(temp < 41){climate = "desert"}
		else{climate = "fire"}
	}else if(water < 7){
		if(temp < 1){climate = "earth"}
		else if(temp < 41){climate = "earth"}
		else{climate = "tropic"}
	}else{
		if(temp < 1){climate = "ice"}
		else if(temp < 41){climate = "tropic"}
		else{climate = "gas"}
	}
	return climate;
}

Each planet should have a name to make is more unique. Each name is based on the Seed and a pre-defined list of names that are available. Depending on the Seed a random name is chosen and a random number added to the name.

planetNames = ["Zeus","Hera","Poseidon","Demeter","Ares","Athena","Apollo","Artemis","Hephaestus","Aphrodite",
"Hermes","Dionysus","Hades","Hypnos","Nike","Janus","Nemesis","Iris","Hecate","Tyche"] this.name = parseInt(Math.randomSeed(0,20)); this.name = planetNames[this.name] + parseInt(Math.randomSeed(0,200));

The last thing to do is set an appropriate sprite for the planets. Again this is chosen from a pre-defined selection of planet sprites.

undefined

The sprite that is chosen for the planet is a direct result of the climate of the planet:

this.sprite = game.add.sprite(10, 10, this.climate);

 

Generating the Moons

Again the generate the moons we need to define the properties that a moon has. I decided each moon needed a Size, Speed of Orbit, Type, Distance and Water Level.

The Size, Speed of Orbit and Type are directly related to the Seed:

	this.moonSize = parseInt(Math.randomSeed(1, 4));
	this.speed = parseInt(Math.randomSeed(5, 10));
	this.type = parseInt(Math.randomSeed(1,4));

The distance is based on the distance of the moon from the sun.
The Water Level is based on the Water Level of the planet

The Sprite for the moons is chosen from the same selection of sprites as the planets they are however scaled down. The sprite chosen for the moons directly corresponds to the Type of moon:

	switch(this.type){
		case 1: this.sprite = game.add.sprite(10, 10, 'desert'); break;
		case 2: this.sprite = game.add.sprite(10, 10, 'fire'); break;
		case 3: this.sprite = game.add.sprite(10, 10, 'plains'); break;
	}

 

Adding an AI to battle for control of the Solar System Generated

 For a little bit of extra fun I created a basic AI that will battle for control over the generated Solar system. This becomes Red vs Green where each AI is assigned a starting planet. Each planet is given a “ship production rate” to generate ships. The AI will send ships from planets it owns to try capture planets it does not own in an attempt to control the entire Solar System.

 


The full source for this project is available on my Github at:

https://github.com/NathanKewley/Procedural_Space

 

 

Home