Have you ever wondered how “Tetris” picks which block will come next or how “Candy Crush” decides how to place each candy. Did someone sit down and write out the order to all of this? No, no one has time for that. However, someone sat down to make it so the game could decide for itself. Now before you start thinking the game is thinking for itself, it is not. The game is simply using a set of rules it follows to decide what block to give to the player next. This is known as procedural generation.
Procedural generation can very basically be described as the creation of something by a computer instead of a human. In “Candy Crush” the placement of the candies is determined by a computer and not predetermined by the game developers. This does not mean a human had no part in how the candies are placed. The game developers created a set of rules and math equations that the computer uses to allow it to determine what candy to place and where. This might seem a little confusing and even pointless right now but it will all make sense by the end.
Procedural generation has been used in games from very early in gaming history to now and from a wide range of game genres. There are many different reasons why game’s developers may choose to use procedural generation. Two of the biggest reasons is the amount of content for a game and replayability of a level. A game of “Tetris” could technically go on forever because the rules for picking the next block has no end. A player could replay the stage in “Candy Crush” for the rest of time and never have the same exact experience. These were the primary reasons we chose to use procedural generation in our game “Donut Slinger”.
What we were aiming for
If you are not familiar with “Donut Slinger” please go download and play it now. Go ahead, I’ll wait. The game is about you taking your food truck around the city to throw donuts to people walking around. We chose to procedurally generate the crowds of people walking around each level in the game. This lets us easily include over 40 levels into the game and make it so each level never felt the same as the one before.
After determining that we would use procedural generation, the first thing we had to do was decide how we were going to implement it in our game. There is no one set method for how procedural generation is implemented in a game. Just take a look at the list on the Procedural Content Generation Wiki for a taste of all the methods. Some methods are great for some cases and terrible in other situations. In order to figure out which method we would implement we had to figure out what we wanted our crowds to look like and do.
We came up with three principles that would guide us. We wanted our crowd to grow denser over time, embedding the concept of risk versus reward, and finally providing some order to the randomness. The first two principles made sure the generated crowd would feel like an actual crowd in the game. In a game, the difficulty generally increases as time goes on, so in our case, more people in the crowd makes it harder to hit a particular person. Many games also have the concept of making more valuable items more difficult to get. The last principle came from early playtesting of the game when we used a purely random crowd.
At this point let’s take a quick pause to define what will be in the crowd. The crowd will be made up of people but not all people are the same, in this case, some people like donuts and others don’t. We’ll call the people that want donuts as “good” and the people that don’t like donuts “bad”. In the game hitting a “good” person earns the player points where as hitting a “bad” person loses the player points. So our crowd will be made up of some number of “good” and/or “bad” people.
Now back to why pure random was destroying things. A common problem of any procedural generation is that the computer will create something that is undesired. In our case, this would create moments early in a play session where a “bad” person is blocking the only “good” person. It also leads to situations where a very valuable “good” person would be easy for the player to hit. In both cases, the difficulty to hit the “good” person does not fit with the game’s desired difficulty curve or the risk factor for hitting a “bad” person.
But how will we build it
With these three principles to guide us, we set to work looking for a method to generate our crowd. At this point, nothing we found would allow us to have control over the positioning of the people in the crowd as each person could be walking in a different direction, at a different speed or different distance away from each other. Through some early play testing, we discovered a few situations where the positioning of people created interesting and challenging moments. This lead to the idea of instead of thinking about generating an entire crowd, generate an individual group of people. Then generate a number of these groups that together would form a crowd. Thinking of the crowd as a collection of groups of people meant that the difficulty could be controlled by increasing the number of groups or the size of each group.
One principle was taken care of so it was time to focus on the next one, risk versus reward. If only there was a way to add more “bad” people the more valuable a “good” person was. Well if we knew from the start that there was a “good” person we could then know to add more “bad” people. This meant that we wanted to look at procedural generation methods that built a sequence of objects where what came before affects what comes later. And like magic, we discovered Markov chains. A Markov chain, at its simplest, is a list of probabilities of what comes after a given input, for a better definition check its Wiki article.
Our secret recipe
We had our method now it was time to set to working building a system that would allow our game to build our crowds. In order to build a group of people, we need two different sets of information: person type and a person’s location in a group. To get this information we use two different Markov chains where the value of one chain is used as the input to the other.
The first chain builds a sequence people types, “good” or “bad”. The chains starts with an empty string as the input, zero order. It then uses the probabilities in the Markov chain to determine if it should select a “good” or “bad” person. After it has done this it looks up the probability of what can come after whichever type of person it previously picked, first order. One of the possibilities at this point is also to end the sequence. It repeats the last step until it selects to end the sequence. There is a visualization of this Markov chain below. As stated before this length limit is increased with time to make the crowd more complex over time.
The second chain takes each individual person from the first chain as its input to determine where they will be placed in the group. Each person is placed into one of three rows near, middle and far. This is in relation to the position of the player so near would be the closes to the player and far being the farthest away from them. Just like in the previous Markov chain the is a probability of what can come after “good” or “bad”. However unlike the previous chain the next link the sequence does not depend on the previous link. Instead, it relies on the next link in the sequence of the first chain.
The end results
This method did have a few shortcomings that we had to work around but it the end we got the results we wanted for our game. We had to add a max sequence length to the person type chain that could be altered over time. This allowed us to increase the complexity of the crowd over time and ensure a group did not grow too large. The person placement chain also needs to have a limit as to how many people could fit onto a particular row. If a row had reached its limit the Markov chain would remove its probabilities from the list for the rest of that group. Without this, groups ended up being too wide for some of the game’s other logic and caused bugs.
Below is an example of a group generated for the crowd. The first Markov chain generated the sequence “GBBBE”. Each of link in the sequence was then used to generate a corresponding sequence of “MNFN”. On the right side, you can see a bird's eye view of how this group would look like in the game. The value of the “good” target would be very high as it would need a very precise throw to hit the target with a donut.
By combining the results of both chain outputs, we were able to create a random-feeling crowd fit for any stage of our game. All we had left to do was serve up as many warm tasty donuts as our virtual crowds could handle!
Download Donut Slinger here!