Procedural Generation in the Real World

Welcome back! So last time we tried to make procedural planets. We sort of achieved that but they didn't look that great. Our method may not have been the best but we also described others and there are real examples of people doing that, so let's take a look.

I think one of the most impressive examples of procedural content generation to date is No Man's Sky. I mentioned this game briefly in my last post but today I want to talk more about. No Man's Sky is impressive for a number of reasons. It achieved what we tried to do and generates procedural planets but it does so much more. No Man's Sky generated an entire procedural universe. A universe far bigger than any one person can ever explore. Each planet is unique and live demonstrations often surprise even the developers of the game because they find new generated content so frequently.

Source

The above video is one of the developers showing off the game and talking about it. I highly recommend you watch it as it is very impressive what these people have made. Every planet has its own ecosystem. Plants, animals, biomes, all unique to each planet and all generated randomly. This game is an incredible feat of procedural content and I am personally extremely excited for the game to be released and to explore it.

The other example I mentioned in the last post was Space Engine. Space Engine generates the entire universe starting with out solar system. It uses realistic physics when creating these planets so many of them, or similar versions of them, can be found in the real world.

Video games aren't the only place procedural generation is used either. It is also popular in film and one of the best examples of this is Peter Jackson's The Lord of the Rings movies.

Source

Above is a shot from the film of a massive Orc army. Each of these soldiers was based on a basic orc model. From there a computer made changes to each's appearance and placed them in after filming. This allowed Peter Jackson to create a massive army where no two soldiers are the same.

Procedural content generation has come a long way. We saw in an early post that it started with dungeons in rogue-like games, and today, it has progressed to the ability to generate an entire universe and create armies. As technology progresses more and more, so will the procedural content generation methods, and it will be interesting to see what we can create.

Procedural Planets

We've come a long way. Starting with a simple dungeon all the way up to the noise functions. Having made it this far is an accomplishment. It's time to move onto bigger and better things though. All of our past posts have been dealing with 2-dimensional content. Today we are going to start 3D, specifically 3D planets ( A.K.A. normal planets ). Procedural planets are a pretty popular topic currently. There are many video games like No Man's Sky ( We are going to talk in more detail about this game in the next post ), and the impressively realistic Space Engine among many others that generate these procedural planets. So let's first talk a little bit about some ways it's done first.

As you have previously seen, there are many ways to accomplish a task with procedural content generation, this is no exception. One way to generate procedural is to actually start with a cube and use a noise function like Perlin or Worley and adjust the points on the cube based on those height values. From there the cube is then projected to a sphere and you have a planet with terrain!

This is not how we are going to do ours though. We are going to do something completely different in fact. While doing some research I stumbled upon one persons interesting idea on procedural planets. It was relatively simple to implement however he had not done it. So I decided to implement it for this post and see how good the generated planets look.

The basic idea is as follows. You first generate a plane with a random rotation around the x, y, and z-axis. You then get every vertex on your planets surface and dot product it with the planes normal vector. If the dot product is greater than zero you move the point in a small amount, if the dot product is less than zero you move it out a small out, and if that dot product is zero, you leave it alone. This is done over a number of iterations with a random plane each time and it will generate peaks and valleys due to the random moving in and out of points. Pretty clever, so let's implement it.


As you can see, there's quite a bit of new stuff here that we have never seen before. That is because this is part of a bigger project. There's a considerable amount of code that is rendering the planet, moving the camera, and things like that. We're not gonna talk about that cause that's a different blog. We're interested in the code above.

As you can see we first make a normal vector that is the planes normal. This is random and each value is between -1 and 1. We create a scale value and determine how many iterations we want to do. We loop through the iterations and loop through each vertice with each iteration doing the dot product each time and moving the points by a scale value. So, let's run it and see how it turns out.

First, this is what our "planet" looks like before we did anything to it. I applied a random texture I had readily available. At this point it's a perfect sphere so all is good.

Next, I ran it over 1 iteration just to test if this idea would even work at all. It did! It created a weirdly shaped planet by moving the bottom inwards and the top out. Great! Let's run it over a larger number of iterations.

Hmm... Interesting. This was run over 100 iterations. You can clearly see the planet was misshaped and now has a series of peaks and valleys. If you look at pictures of earth from space though you can't see the difference in elevation, it looks perfectly round and this doesn't! That is because this is on a small scale. In order to achieve that effect I would have to make the scale factor incredibly small and the planet incredibly large with a staggering number of vertices and I don't have the time for that.

Because of this, I would say the "planet" looks more like an asteroid. So perhaps our method needs to be slightly different. Maybe we will try a new method in the future. But for now, we have a starting place. We rendered some planets and we made them not perfectly spherical.

As usual, thanks for reading. Hopefully we get a better result next time. If you want to see the full source code go here. I have added all necessary code in the Prodedural_Planets folder so you can run it if you want. The code in this post is located in mesh.cpp.

Worley Noise

Previously we discussed two different noise algorithms, Diamond-Square and Perlin noise. Both of these noise algorithms produce similar results and can be used for a variety of things but there are certain places they aren't great. So today we are going to talk about one last noise algorithm that is versatile and produces results very unlike the previous two algorithms. That algorithm is Worley Noise. Also referred to as Cell Noise or Voronoi noise, this algorithm is very useful in generating or simulating stone, water, and cells. So lets get started in talking about this!

Worley noise is one of the more complicated noise function we've covered. Not only that, it is also the slowest of them. It however is more customizable than the other ones. We will see examples of this at the end. First, lets take a look at our constructor.



Here we can see where everything is set up. We have a variable called permutations that is set with unique values from 0 to 255. These numbers are then swapped around to make them in a random order. These are used to determine the location of the "cells" in the final image. In the constructor we call the fill_map method which can be seen below.


The idea of the fill map method is simple. It iterates through each pixel and determines the color it should be. Along with that it also saves the maximum and minimum values that are seen. These can be used for scaling if necessary. In the fill_map method we see smoothed_noise is called so lets look at that.


The smoothed_noise method is where all the calculations are done. All of these are based on distances which will return the grayscale value for that pixel. How this is done can vary though. In the code we see 3 commented out lines. If one is uncommented we can get a completely different looking picture. These are the distance functions and they are what make this algorithm so powerful. By simply changing the distance algorithm a stone texture, water texture, or many other textures can be created. We will see examples of all of these when we actually run the algorithm. Let's take a look at how these distances actually work.


Each distance method is a form of the distance formula ( sqrt( x2 - x1 ) ^ 2 + ( y2 - y1 ) ^ 2 ) ), but they all have their own touches. So now that we have a basic understanding of the algorithm, lets see what it actually outputs. Up first we are going to use euclidean distance.

Euclidean Distance

Here we can see the algorithm output a picture that looks similar to cells. It's very unlike every other noise algorithm we've seen this far. Next, manhattan distance. 

Manhattan Distance

Manhattan distance creates diamond-like shapes. It also creates some very light and very dark areas which can be seen above. Now, chebychev distance.

Chebychev Distance

Chebychev has a similar look to manhattan although instead of diamonds they are more square and very interesting looking. Lastly let's look at quadratic distance. 

Quadratic Distance

Quadratic creates a similar look to euclidean but slightly different. All of these distance function can be modified and more can be added to create many different and unique effects. It's just a matter of playing with them.

As usual I hope you learned something new or found this interesting. For the full source code you can go here. See you next time!

Perlin Noise

Welcome back! Last time we discussed the Diamond-Square algorithm. While that algorithm works great for certain cases, it had its drawbacks that we discussed last post. Instead of fixing those we're gonna just implement a different way to get similar results. That way is Perlin Noise!

So what is Perlin Noise? Well similarly to Diamond-Square, it's a way of generating random height-maps that can be used for a number of things. Games are generally a place they are used commonly to create random terrains. It is very simple to implement and produces much better looking results than Diamond-Square as it does not have the same artifacts. The biggest drawback to Perlin Noise is that it is slightly slower than Diamond Square and it can only generate squares. Both of these can be worked around though so lets dive into the code.



Above we can see the constructor for our Perlin Noise class. We haven't looked at most of the constructors before but this one does more than most. In this one we fill a vector with random values. These random values are dependent on our seed and act as the "gradient" for the rest of the algorithm which will be talked about more later on.



Here we have our perlin method. This is where the majority of our calculations and code is. There is a lot of stuff going on here so I will cover the basics. If you are very interested in each low level idea, Ken Perlin wrote an entire paper about Perlin Noise you can read. So, carrying on. First we take the floor of our values and bitwise and them with 255 ( Read here if you don't know what bitwise operations are ). We then subtract these values from the floor of themselves. Then we see another method we haven't seen yet, fade. Let's look at fade.



Here we can see all of the methods we haven't seen yet. Fade and grad are actually unique in that every implementation of Perlin Noise is supposed to/should use the same equation made by Ken. You can see it is just a simple math equation where we multiply and add some values. So carrying on, we can next see where our gradient values come on. These are chosen based from our x, y, and z, and the subsequent variables that came from them. We then see the grad method actually used. Here a series of bitwise operations change the values. These help insure randomness. They are then linear interpreted ( lerp ) with each other in our lerp method. This is just a stand linear interpolation, nothing fancy. This is done multiple times over every point. So how do we actually use this?



Above is our to_png method. We need some visual representation to output this to to see our results and that is how we do it. So lets run it and see what it looks like.

Wow, look at that! It looks random! And every time we run it it will be random. But wait... What is the commented code? Well with Perlin Noise we can easily modify the produced values to create something... different. Let's uncomment that code and run it and see what happens!

Wow! Look at that! That commented code works well for producing a wood-like texture. Pretty nifty. Playing around more can create different effects but I will let you explore them yourselves. Hope you enjoyed this and learned something new. As usual, see the full code here.

Diamond Square

Last time we talked about the Midpoint Displacement algorithm in preparation for the Diamond Square algorithm. Dimond Square is basically a 2D version of Midpoint Displacement. It has lots of use in modern video games due to its speed and ease of implementation. So let's get started to see how it actually works.

Source

Wikipedia has a helpful image to help easily understand the algorithm. First four corners are selected and their height values are remembered. Those values are averaged and given a random offset value. The center of those four is now the new corner. This is the diamond step. The square step is next. The middle is used as a reference and each point out from it is set to a random value and the average of the four corners. This is repeated multiple times. 

In the code below we can see the implementation of the "generate" method. This method is where the bulk of the work for Diamond Square is done. It loops over the grid a certain number of times, each time doing a "diamond' step and a "square" step as discussed above.

Then below we can see the implementation of the actual diamond_step and square_step methods. These do as discussed in the description above.

The last bit we have to talk about is the sample method. This is a clever method that uses bit operations to get locations on the map. Because of how it works it allows the map to wrap around itself and generate maps that have borders that will be seamless. We can see the actual implementation below.

Now that we see how it works, we can see the result!

This is an example output. We can see the high areas are lighter than low areas. This has a fault though which is discussed below.

While this algorithm has advantages, it also comes with some downfalls. One of the notable downfalls that affects many when using this algorithm is that it has a tendency to generate ridges in lines. So many times there will be a set of ridge peaks or valleys at very similar locations. There are ways around this but those are out of the scope of this post. Another downfall is that the map has to be a size of 2^n + 1. This is rarely a problem but can be if you need a certain sized map. The simplicity of this algorithm is what makes it so powerful and why these downfalls are rarely an actual problem.

Thats the basics with Diamond Square. It's a simple implementation and generates random results. As usual hope you learned something and heres the full code.

Midpoint Displacement

Up until now all of our programs have been printing grids to console. These were cool to look at but were often only useful for a very specialized purpose. Because of this were are going to do something very different. We are going to write our own Midpoint Displacement algorithm. Midpoint Displacement is a form of the Diamond-Square algorithm ( another algorithm we will be covering later on ). These two algorithms are very similar the main difference being Midpoint-Displacement outputs a line while Diamond-Square outputs a grid. However, to better understand Diamond-Square we later on we are starting simple with Midpoint-Displacement. So let's get started!

Midpoint-Displacement is an extremely simple algorithm ( I wrote a Java version back in high school its so simple ) but it creates unique and interesting outputs every time we run it. The algorithm works as follows. First, two endpoints are created. These will be used as anchors. A midpoint is then found between the two points and it offset by a random number based on a "roughness" value. The algorithm is then run again doing the same thing. Finding the middle between each point and raising or lowering the point based on the "roughness." The idea is simple so let's see what it looks like in code.

Extremely straightforward. The method calls itself each loop around and makes sure that it is only doing the number of points that there should be. We can see there are two methods that we use that are not in the code so we can look at those briefly below.

The "middle" method is just your run of the mill midpoint formula that you learned in elementary school. Then with the "displace" method we can see that we keep the x-value the same and modify the y-value based on it's current value plus a random number in between the negative roughness and positive roughness.

In order to see how what this outputs, I wrote a small method that plots the x and y values on a black image. So when we run the program, we might expect to see something like this.

Or something like this.

We can see that the Midpoint-Displacement algorithm generates ridges and valleys. This has some practical use in real games too! 

Source

I lot of people probably remember playing that game ( or something similar ). It used an algorithm similar to Midpoint-Displacement to create its random and interesting terrains. 

We've got a basic understanding of Midpoint-Displacement now so we can next talk about the Diamond-Square algorithm! This algorithm also has a lot of use in real life games. As usual, hope you learned something and you can see the source code here.

Mazes

Welcome back! Our first couple posts are helpful for if you are designing a video game, but what if you want an algorithm for something that can be done on paper just for fun? Well you can always do a maze! Mazes are monotonous and time consuming to draw though so you need a better solution. Luckily there are many! There a multiple different algorithms for generating mazes and we are not going over all of them. We are going to go over one called a Recursive backtracker. The basic idea is as follows.

We have a list of unvisited cells. We choose one at random and start there. Next the algorithm loops until there are no more unvisited cells. In each iteration of the loop it checks if the current cell has any unvisited neighbors. If it does it moves to that cell, pushes it to the stack, removes the wall in between and marks it as visited. If the cell has no unvisited neighbors, we pop a cell off the stack and make it the current cell. This may sound confusing but it is actually very straightforward one it is seen in code so let's jump into it.

This is the bulk of the algorithm and where all the hard work is done. We can see in the first two for-loops is where we populate a list with unvisited cells. Then we choose a random cell and make it our start and mark it as visited. Unseen in this snippet is the while loop condition which checks to see if there are still unvisited cells. As usual this can be seen in the Github Repository ( link below ).  This also applies to getting the neighbors. We can see if we have neighbors we get a random one, move there and make it visited and if we don't we pop one of the stack.

So when this is actually run, how does it look!

Look at that maze! Wow that looks complicated. And they are. I spent more time than I care to admit trying to solve that. This algorithm has it's ups and downs. You may notice that there are little or very few long "jagged" corridors. This is due to the nature of the algorithm and there are other maze algorithms, like using a depth-first search algorithm, that will make those long jagged corridors.

I'm happy with how our mazes look though. They are complicated and fun and more common in everyday life than some of topics. As usual, I hope you learned something new.

For the full source code, go here.

Random Cave

Last week we discussed how old games made random dungeons. Today we will be doing something similar, but very different. Our random dungeon algorithm is great if we want to create rooms with hallways, but that puts a big limit on what we can actually generate. Let's say for example, I want to make a cave like environment. Well that is what we are going to discuss today, procedurally generated caves. Below we can see what our output is going to look like.

Looks like a cave doesn't it? This is done using a type of Cellular Automata. Let's begin talking about how this is actually done.

The first thing we have to do is fill the map. In order for this to work we provide a random chance that the map is filled with a '#' or a ' '. In the case above, we filled 45% of the map with '#'. These will represent our walls and the ' ' represents open cave. Below we can see how we filled it. 

We can see that we fill the walls with '#' pieces and the rest of the map is given a percent chance to be a wall or an open space. When we run this we get a map that looks like this.

This looks very odd and nothing like a cave. But we can work with this! We can see perfectly that 45% of the map is '#' and the other 55% is ' '. The next step is where everything starts to take shape. 

In the next step we check what each tile is. If the tile is a '#' and there are 4 or more walls around it we keep a '#' symbol there. However, if there are less than 2 walls around it we make it a ' ' tile. Then, if the tile is a ' ' and and there are 5 or more '#' tiles around it, we make it a '#' tile otherwise it stays the same. This is tested on every tile and generally over multiple iterations. We can see this implemented below. 

Using 1 seed with this algorithm has the ability to generate more than 1 map though depending on the number of iterations. Below we can see the map with the seed '1234' over 1 iteration. 

This generates a good looking cave. It has some rough edges though so lets make it over 5 iterations and see what we get below.

The cave looks very similar, maintaining the same shape, the main difference is that it looks much smoother due to the extra iterations. The number of iterations can be changed depending on the type of cave that you want, the choice is completely arbitrary. 

So that is how we make random caves using Cellular Automata. The process is extremely simple but generates a unique output each time! I hope you learned something new or interesting. As usual the complete source code can be found on my Github here. See you next week for a new topic!

Random Dungeon

Some of the earliest video games were a type of game called roguelike. This game type is characterized by procedural generation of random levels and was generally tile based.

One of the earlier examples of this was the game Rogue ( 1980 ). Rogue used a series of colored ASCII characters to define different objects and characters in the game. However, for the purpose of this blog we are more interested in the creation of one of the games levels. In Rogue, a level consisted of a series of rooms connected by hallways. The layout of a level was always random and always unique. The allowed the game to be played over and over always having a different play experience. Below is an example of your average Rogue level.

Here we can see distinct rooms and different hallways to connect them all. So lets make our own way to do this!

First we need to define what a room is. We do this in a Room class where we will define the two corners in an x/y coordinate system like below.

In the code above we can also see that we defined some methods that will help us later on.

Next we need to actually make some rooms on our map. Our map is simply defined as a vector of characters. When we add a room or hallway it just replaces the character to something else. First we will see the code and then we will explain it.

In the above code we first see our declaration of the RandomDungeon class. Here we define our variables for the width and height of the dungeon level and create the vector for the map. We also define our method headers here. When we go the the .cpp file we can see the actual implementation of generate_dungeon_room_map. First we loop through each room. We create a room with random side lengths of 5-10 characters. We then create them in a random location and check to make sure there are no other rooms at these locations. I ran this to create a map with side lengths of 45 characters and with 9 rooms and got an output that looks like this.

We're starting to get something now. We see clearly defined rooms, however, we have no hallways that connect them so we're going to need to make them. Below we have two methods, horizontal_hallway and vertical_hallway that will generate halls for us. 

These two method simply take the location of the rooms and generates L-shaped hallways that connect them. In the generate_dungeon_room_map method there was a section commented out. When uncommented and the code is run we get a map that looks like this, for example.

Because we used a different seed the generate this map have different room locations except this time we also have hallways connecting them.

This has allowed us to create the very basic parts of a roguelike level. From here we can create special rooms, different hallways, or any number of levels all by changing a few parts of our code.

Hope you learned something new. Since you only saw snippets of code you can view the full code here: https://github.com/CMilby/PCG-Blog. Next time we will be covering another form of procedural generation, expect this time, we will be talking about make caves! See you next time.

PCG Introductory Material

Before we start getting into actual procedurally generated content I need to cover some basics.

All code posted will assume that you have an understanding of programming and the language. I plan on doing much of the code in C++ but this is subject to change based on what I am doing that week. If you do not know the language it should be relatively easy to follow along with an understanding of other languages.

Let's talk about randomness. Nothing is actually random. When I say random what I really mean is pseudo-random. Pseudo-random is when something appears to be random but is actually not. Because computers cannot make decisions they instead rely on algorithms to generate numbers that appear to be random but are actually not and over enough iterations would repeat and a pattern would be noticed. This pattern is so large though that humans will not notice it. For the purposes of this blog we do not actually need real randoms and pseudo-randomness will work perfectly.

When we want to create something random we rely on a seed. If two computers running the same program that rely on random numbers are given the same seed, they will generate the same output. This mean that if you at home run the code you will not necessarily have the exact same output as me. Take the code below for example.

We can see that this is an extremely basic C++ program. We have our main method and in it we create a variable called seed that we get from time. This means that when the program is run we will always print out a different value from rand because we have a different seed.

This covers some of the basic material you will need to know. I will do my best to try and explain the important and confusing parts of the code in detail as well as the general ideas being presented. However, if questions are still pertinent just leave a comment and I will do my best to explain in more detail.  I also do not claim by any means to be a C++ expert so while there are other ways and probably even better ways to accomplish the same task, I am merely presenting A way to do it, not the best.

The first real post will be coming later in the week.

Welcome To The Blog!

Welcome to the Procedural Content Generation ( PCG ) blog. In the next couple of weeks I will be discussing and programming all sorts of different ways to generate procedural content.

Before we get started lets talk about what PCG is. Well, it is the programatic generation of content using a pseudo-random number generator. There are hundreds of methods to do this that all have their own unique uses and implementations. The idea behind this is to allow someone to create a unique something every time a program is run.

Along with discussion and uses of each generator I will also be programming them myself and will walk through certain parts of the code. All of the code will be open source and be made available to anyone who wants to view it or needs some help doing something similar. I will also show examples of the finished product so you don't have to run the code yourself as well as some real-world examples of where that method is used.

In my next post we will be going back to early video games and talk about dungeon generation. See you then!