Randomly generated, fast paced platformer. Can you escape The Dungeon?
Play NowPlatforms: 

Status: 
Work in Progress 
Genre: 
Platformer 
Audience: 
Everyone 
Hello!
So for this post I wanted to talk about the background tiles of my game and how I did procedural generation.
With tile sets something you will run into is the difficulty to randomly generate them because not all the tiles in your tile set can be seamlessly lined up next to one another. The issue this creates is if you were to just randomly place them you would have brakes in your background and it would make the scene distracting for the player because its not seamless. So how do you overcome this? How do you create a system that is still random but will not brake the cohesion of your background.
Simple (kinda of)! You use a Markov Chain. Now there are probably other ways to achieve a similar result but this is the what I used and it worked great. A Markov Chain is named after a Russian mathematician Andrey Markov. This is a random process where future predictions are based solely on the present state independent of the history of your previous results. Don't worry if that sounds complicated because we're going to simplify it right now.
Imagine we have 3 tiles and we want them to be randomly placed so that they create a seamless background image that looks great! So lets create 3 states:
1...............
2...............
3...............
Each state will represent our tiles respectively. Now lets create a random integer and name it R. R will hold a value between 0 and 100. Now where do we go from here? Well to be a Markov Chain we need our states to decide what tile to draw based on what tile was just drawn. Another way to think about it is, what state do we move to based on the state we currently in. This is where we use R to help us decided this. Lets say we never want 2 tile 1's next to each other, but we want to have a 75% chance that tile 2 will be drawn directly following and then the other 15% of the time tile 3 can be drawn directly after tile 1. So then we change our diagram to the following:
1.0..75..100.
2...............
3...............
If this layout is starting to look familiar to you it should because it is setup like a 2d array! Each location the numbers are in represent a different state in our diagram. The number 0 represents state 1, 75 represents state 2, and 100 represents state 3. So what happens is after we get R we compare it to the values in state 1 and loop through it till R is less then the value present. Since R's values are between 0100 R can never be less then 0 so by making the first value 0 we know that we can never transition back to state 1 from state 1, thus tile 1 will never draw next to itself. What if our value R is 55, then we see that it is not less then 0, but it is less then 75 so we draw tile 2. Now since we drawn tile 2 we have changed states to tile 2 and thus the process repeats itself. Ill fill out the rest for example purposes and then will write some pseudo code as an example.
1.0..75..100.
2.0..50..100.
3.100..0...0...
//This code will loop through the area that we want to have our tiles drawn.
for(int j = 0; j < tilesHeight; j ) {
for(int i = 0; i < tilesWidth; i ) {
int R = Random.range(0,100); //define our random integer
while(!found) { //our loop till we find what state value our random integer is less then.
if(R < states[currentState][iteration]) {
found = true; //this tells us we found the state we need to change to and to exit the loop to start drawing our tiles.
currentState = iteration; //This changed our current state to match the tile we are about to draw so that the next time we come through we are comparing the right values
}
else iteration ;
if(iteration > states[currentState].size)
found = true;
}
}
//Here you will draw your sprite before moving onto the next one.
}
I know it looks kind of rough but try it out! If you have any questions please leave them in the comments and I will be happy to help where I can!