Kid.js | Labyrinth Game Using Device Orientation

Part 4: Auto-Generating The Maze 45 Minutes

It was a lot of work to create each wall of the maze, and it’s the same maze each time. Let’s look at an algorithm to create the maze for us.

For this session, it’s recommended that you have some previous JavaScript experience, specifically with arrays and objects.

Imagine the screen is divided into a grid.

Walls are placed between grid squares. If we place a wall between each pair of neighboring squares, the grid is divided into many one square sections and you can’t move from one square to another.

We'll start removing walls in a moment, but first let's look at how we can represent the grid and walls in our code.

Arrays

Arrays are used to store lists of things. Think of arrays as a box divided into sections, each storing a single item. Each section has a unique number, called an index, that we can use to reference it.

In JavaScript, we create an array using square brackets, and optionally including a number of initial items. For example, we could create a list of out favorite things.

let favs = ['pizza', 'rainbows', 'puppies']

We can access an individual item by providing the index, again using square brackets. Be aware that the first item is index 0, the second is index 1, and so on.

favs[0] // 'pizza'

To keep track of each grid square, we'll use a two dimensional array, or an array of arrays.

The following code first creates an empty array to represent the grid. It then uses a nested for loop to assign a section number to each square.

let grid = []
let section = 1
for (let x = 0; x < 8; x = x + 1) {
  grid[x] = []
  for (let y = 0; y < 6; y = y + 1) {
    grid[x][y] = section
    section = section + 1
  }
}

Objects

Objects can be used to store more complex data. Instead of storing a single value, they can store a collection of properties and values. We'll use objects to represent the walls of our maze.

Each wall object will have properties that indicate the x and y coordinates of the squares on either side of the wall. We'll also include a property to indicate whether the wall is horizontal or vertical. This will come in handy later on.

The following code again uses a nested for loop to move through the squares in the grid and create a wall between it and the square to the right, and the square below.

let walls = []
for (let x = 0; x < 8; x = x + 1) {
  for (let y = 0; y < 6; y = y + 1) {
    if (x < 7) {
      walls.push({
        ax: x,
        ay: y,
        bx: x + 1,
        by: y,
        orientation: 'vertical'
      });
    }
    if (y < 5) {
      walls.push({
        ax: x,
        ay: y,
        bx: x,
        by: y + 1,
        orientation: 'horizontal'
      });
    }
  }
}

The Algorithm

To generate the maze, we'll use a version of Kruskal's algorithm, developed by mathematician Joseph Kruskal. It goes a little somethinglike this:

Select a wall at random.
If the wall separates two different sections, remove it and merge the sections.
Otherwise keep the wall.
Repeat until we've gone through all the walls.

Let's look at how we can implement this in code. First create an array that will hold the final walls that make up our maze.

let maze = []

Pick a wall at random, and remove it from the list. We can use the splice() method for this.

let i = random(0, walls.length - 1)
let wall = walls[i]
walls.splice(i, 1)

The grid array contains the section each square currently belongs to. If the two squares separated by the wall are in different sections, merge the sections.

let a = grid[wall.ax][wall.ay]
let b = grid[wall.bx][wall.by]
if (a != b) {
  for (let x = 0; x < 8; x++) {
    for (let y = 0; y < 6; y++) {
      if (grid[x][y] == b) {
        grid[x][y] = a
      }
    }
  }

Otherwise, keep the wall by adding it to the maze array.

} else {
   maze.push(wall)
}

While Loop

Keep doing this until there are no walls left. We can use a while loop for this. A while loop will repeat a block of code as long as a certain condition is true.

let maze = []
while (walls.length > 0) {

  // Pick a wall at random
  let i = random(0, walls.length - 1)
  let wall = walls[i]

  // Remove the wall from the list
  walls.splice(i, 1)

  // Check section on either side of the wall
  let a = grid[wall.ax][wall.ay]
  let b = grid[wall.bx][wall.by]

  // If different sections, combine them
  if (a !== b) {
    for (let x = 0; x < 8; x++) {
      for (let y = 0; y < 6; y++) {
        if (grid[x][y] == b) {
          grid[x][y] = a
        }
      }
    }

  // Otherwise include the wall in the maze
  } else {
    maze.push(wall)
  }
}

Part 5: Drawing The Maze 15 Minutes

Finally, go through each wall in the maze array and draw it using the rect() function. We need to do a little math to figure out the exact size and location, based on the coordinates of the squares it separates, and the width and height of each square.

So first, let's calculate the width and height of each square. We can do this by dividing the width and height of the screen by the number of squares in each direction.

let squareWidth = width / 8
let squareHeight = height / 6

Now we'll loop through each wall.

for (let i = 0; i  < maze.length; i = i + 1) {
  let wall = maze[i]

Our code will be slight different depending on whether the wall is horizontal or vertical. Luckily we included this bit of information in the object representing a wall.

The first two parameters we pass to the rect() function are the x and y coordinates of the center of the shape. For the x coordinate, we'll move over the number of squares specified by the x coordinate of the first square, then go half a square further.

  if (wall.orientation == 'horizontal') {
    let x = wall.ax * squareWidth + (squareWidth / 2)

For the y coordinate, we'll move down the number of squares specified by the y coordinate of the second square.

    let y = wall.by * squareHeight
    rect(x, y, squareWidth + 20, 20)

The code for the vertical wall is similar, just swapped around. It may be helpful to pull out a piece of paper and sketch out a few examples to help get your head around it.

  } else {
    let x = wall.bx * squareWidth
    let y = wall.ay * squareHeight + (squareHeight / 2)
    rect(x, y, 20, squareHeight + 20)
  }
}

Putting It All Together

Taking It Further

Try making the grid squares smaller.
Play a congratulatory sound when you reach the goal.
Generate a new maze after you finish the first one.
Add traps that send you back to the start.
Multiple marbles at once!