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!