Joachim Ford

Snakes And Ladders Talk Through: Level Generation

The source code for the level generation of Snakes And Ladders is by far the most overwhelming piece of code in the entire game. Despite this, I also think it's also the most interesting part.

Set up

To begin the level generation, we need to start by making a list that stores the level. We can do this by constructing an array:
this.array = [] // an array that stores the level this.width = 100 // the amount of columns this.height = 100 // the amount of rows
The first thing to do to our array is to fill it in with blocks, which we can mine out later. In the code snippet below, a block is represented by 1.
// iterate through the amount of blocks in the world for (let i = 0; i < this.width * this.height; i ++) { this.array.push(1) // fill the level with blocks }
To draw the blocks, you can write code similar to this:
// set the scale const block_size = 50 // iterate through every square in the level for (let x = 0; x < this.width; x ++) { for (let y = 0; y < this.height; y ++) { const block = this.array[x + y * this.width] // draw it if the current square is a block if (block == 1) ctx.fillRect(x * block_size, y * block_size, 1 * block_size, 1 * block_size) } }
That's all you need to set up the map. Now we can start carving bits away.


The next thing to do is to start mining rooms. Each chamber has a random width and height, and is positioned in a grid. Store the chambers in an array, so that the computer can know where to place the tunnels and actors later on.
¬this.array = []¬ this.chambers = [] // make an array that stores the chambers ¬this.width = 100 this.height = 100¬
In the code below, 0 refers to plain air.
// this code makes a single chamber. // note that chamber x, y, width and height have already been defined. for (let x = chamber_x; x < chamber_x + chamber_width; x ++) { for (let y = chamber_y; y < chamber_y + chamber_height; y ++) { this.array[x + y * this.width] = 0 } }


Making the tunnels is a complex part, so I will just give you a simplified overview. To begin, we need to know how each chamber should be connected. I went with the binary-tree maze structure which is the simplest procedural maze that anyone could hope to make. This is how it works:
∙ Get your chambers set up
∙ Starting at the top left, connect your chamber to either:
  ∙ The chamber on the right
  ∙ The chamber underneath
With these rules applied, the maze should start to be taking shape. Note how the passages seem to point towards the bottom right corner:
If we just stop here, though, some channels may never connect. The way to fix this is to cut a channel through the right and bottom edge.
The next thing to add is ladders. This took a very long time for me to get right, but in the end the solution turned out to be really simple: Let's say a chamber decides to connect itself to the one beneath it. To help me explain, I will call the first chamber Jeff and the second chamber Andrew.

A tunnel emerges from the base of Jeff and snakes its way down. At the moment, the tunnel stops as soon as it touches Andrew's head, but let's change that rule. Let's make it so that the tunnel has to proceed through Andrew's body untill it reaches the ground. This may sound pointless, as the tunnel would just be mining through plain air, but it means that we are able to start building a ladder.

Let's add a new rule: If the tunnel finds itself mining though Andrew's body, add a ladder block behind it. This new rule means that ladders will only be generated inside chambers and it also means that Drillo will be able to get into rooms that he couldn't before.

Reverse generation

As you can see, the world still looks very different from the real game. What we are missing is reverse generation - a final "filter" that removes the pointless blocks. At the end of the generation code, I run through every block in the level and do the following:
∙ If the current block is surrounded by other blocks:
 ∙ Turn the current block into thin air
The advantage of this final filter is it speeds up in-game performance, it makes the level look better (in my opinion), and it also gives the world a vast feeling of nothingness - meaning the player is not able to see the sharp boundaries of the map.

Side effects

This final section briefly discusses how each side effect is placed in the level and how the level adapts to them. To set everything up, put a side effect in each chamber, making sure that it does't get dropped above a tunnel hole.

If you played the game, you may have noticed the average size of each chamber grew as the game went on. This is because the size for each side effect is stored from the start. It means that the computer can know exactly how big its chambers should be for the current level.

In the game, there's a function called getLevelEffects(), which returns an array of all the enemy types for the level.
function getLevelEffects() { if (game.level <= 2) return [0] if (game.level <= 3) return [1, 1, 0] if (game.level <= 6) return [2, 2, 1, 0] if (game.level <= 7) return [3, 2, 1] if (game.level <= 8) return [4, 2, 0] if (game.level <= 9) return [6, 4, 1] if (game.level <= 10) return [7, 6, 2] if (game.level <= 11) return [7, 6, 4] }
You may notice that the largest side effects always come first in the array. The reason for this is it means that when the map is being generated, it can take the size of the biggest side effect into consideration. It can thus make sure that its minimum chamber width and height is way larger than the recorded enemy.
// get the biggest enemy sizes const EFFECT = EFFECT_TYPES[getLevelEffects()[0]] // minimum chamber width const MIN_WIDTH = Math.ceil(EFFECT.width.max) * 2 // minimum chamber height const MIN_HEIGHT = Math.ceil(EFFECT.height.max) // result const CHAMBER_W = {min: MIN_WIDTH + 1, max: MIN_WIDTH + 10} const CHAMBER_H = {min: MIN_HEIGHT + 3, max: MIN_HEIGHT + 5}
You can learn more about the enemies of Snakes And Ladders in the next article of this series. That's it for this article, I hope it clarified things for you and maybe it will come in handy for projects in the months to come!
© Copyright —