Procedural Level Generation

I’ve written a little example program to illustrate the level generation algorithm that I’ll be using in “Run Bobo Run”.

The Game class is the main entry point, it simply creates an instance of Level, calls the generateLevel method (supplying relevant parameters), then calls printLevel (which outputs a representation of the level to standard out).

Here’s the sourcecode:

 public class Game {  
  public static void main(String args[]) {  
  Level level = new Level();  
  level.generateLevel(45,15,5,5);  
  level.printLevel();  
  }  
 }  

The Level class is where the level generation algorithm lives. Let’s think about what we need it to do:

1. Create a 2D level comprised of a set amount of tiled rows and columns
2. Create a path of a certain width that runs down the level
3. Potentially shift the path one tile left or right on each consecutive row that is created (randomising means unique levels on repeated playthroughs)
4. Ensure the path never strays outside the world bounds

Here’s the sourcecode:

 /********************************************************************************************  
 * RANDOM LEVEL GENERATOR  
 *  
 * This algorithm procedurally generates levels for use in simple 2D games where the object  
 * is to remain on the path and avoid crossing any blocked tiles.  
 ********************************************************************************************/  
 import java.util.Random;  
 public class Level {  
     int levelHeight; // Height of the level measured in tiles  
     int levelWidth; // Width of the level measured in tiles  
     int pathWidth; // Width of the path measured in tiles  
     int pathOffset; // Number of tiles to the left of the path  
     char[][] level; // Two dimensional array representing the level  
     Random randomGenerator = new Random();  
     public void generateLevel(int levelHeight, int levelWidth, int pathWidth, int pathOffset) {  
         this.levelHeight = levelHeight;  
         this.levelWidth = levelWidth;  
         this.pathWidth = pathWidth;  
         this.pathOffset = pathOffset;  
         this.level = new char[levelHeight][levelWidth];  
         for (int row=0; row<level.length; row++) { // for each row in the level  
             for (int col=0; col<level[row].length; col++) { // for each element in the row  
                 // set value based on elements location in the array  
                 if ((col < pathOffset) || (col >= pathOffset+pathWidth))  
                     level[row][col] = 'X'; // this tile is not on the path  
                 else  
                     level[row][col] = ' '; // this tile is on the path  
             }  
             // generate a random integer (-1 or 0 or +1)  
             int stepModifier = (randomGenerator.nextInt(3)) - 1;  
             // apply modifier to path offset provided the path would remain within world bounds  
             if ((pathOffset + stepModifier >= 0) && (pathOffset + stepModifier + pathWidth <= levelWidth))  
                 pathOffset = pathOffset + stepModifier;  
         }  
     }  
     public void printLevel() {      
         for (int row=0; row<level.length; row++) {  
             System.out.print("|");  
             for (int col=0; col<level[row].length; col++) {  
                 System.out.print(level[row][col]);  
             }  
             System.out.println("|");  
         }  
     }  
 }  

A two dimensional array is the perfect data structure for a 2D tiled level. In this toy example it’s an array of char’s (so I can output a human readable representation to console), in the real game it’ll be an array of Tile objects.

I use nested iterators to touch every element in the array. In English-ish - “For each row in the Level do {for each column in the current row do {depending on what column you’ve reached, set the value to something or other}}”.

How do we decide between setting the value to ‘something’ or ‘other’? This condition should shed a little light “if ((col < pathOffset) || (col >= pathOffset+pathWidth))”. If we have not yet reached the column that that marks the start of the path, or we have reached/passed the column that is the end of the path, we should set the current element to blocked. If the evaluation of the condition returns false, set the current element to be part of the path.

Finally, how do we introduce the random change in path offset per row? First, we generate a random integer between -1 and 1, “(randomGenerator.nextInt(3)) – 1″. Next, we check to see if applying this randomly generated modifier to the current path offset would result in the whole path remaining within the world bounds, “if ((pathOffset + stepModifier >= 0) && (pathOffset + stepModifier + pathWidth <= levelWidth))”. If the condition returns true, we apply the modifier, but otherwise we do nothing.

I think that about covers it. Next time I’ll likely be looking at how to move a sprite around the game world, and forcing the camera viewport to follow it. For now I’ll leave you with a super exciting screenshot of a procedurally generated level output to the console: