Maze Building

In this next series, I'd like to explore the A* search algorithm. The algorithm is a path finding algorithm. A path finding algorithm is used in computing to find the shortest between two points. The algorithm is useful in many applications. For example, mapping and directions software utilizes path finding. It is also found extensively in many game applications. However, before we can delve into the details of the A* algorithm, we need a graph for our algorithm to explore. A maze is one such application. We can apply the A* algorithm to a maze to find the most efficient and direct route. In this blog post, we will explore how to build a maze to exercise the A* algorithm.

We could manually create a data structure that represents our maze and render it on an html page. However, there are algorithms available to programmatically build mazes. One of the simplest algorithms is the Randomized depth-first search. The recursive version of this algorithm, as described by Wikipedia, involves the following six steps:

First, create a function that receives a cell in a maze.
In the function, the cell is marked as being visited.
We gather any unvisited neighbors of a given cell, and for each one, we do the following:
1. Randomly select a neighbor.
2. Remove the wall from the current cell and neighbor.
3. Finally, we call our function recursively and supply the current neighbor.

Let's build it

First, let's build an html page to display the maze. To begin, we can set up a simple box. Our maze will be rendered in this box. We also add some styling for our cells and walls. The walls are represented as individual div elements. The page will look something like the following.

<html>
  <head>
    <script type="module">
    import { buildMaze, renderMaze } from './mazer.js';
    document.addEventListener('DOMContentLoaded', () => {
      const mazeEl = document.getElementById('maze');
      const maze = buildMaze(mazeEl);
       renderMaze(mazeEl, maze);
    });
    </script>
    <style>
      #maze {
        position: relative;
        height: 500px;
        width: 500px;
        border: 1px solid red;
      }

      .wall-left {
        position: absolute;
        display: block;
        height: 50px;
        width: 1px;
        background: red;
      }

      .wall-top {
        position: absolute;
        display: block;
        height: 1px;
        width: 50px;
        background: red;
      }

      .cell {
        height: 50px;
        width: 50px;
        position: absolute;
      }

      @media print {
        body {-webkit-print-color-adjust: exact;}
      }
    </style>
  </head>
  <body>
    <div id="maze">
    </div>
  </body>
</html>

The code to generate our maze lies within the internals of the imported buildMaze function. We will represent our maze with an array of arrays data structure. The code will begin by building a 10x10 array of arrays. Each cell will have an internal state. The state will track if the cell visitation state, the cell coordinates, and which walls are visible for each cell. We will also create two variables that will be assigned the random start coordinates.

const maze = [];
for (let x = 0; x < 10; x++) {
  maze[x] = [];
  for (let y = 0; y < 10; y++) {
    maze[x][y] = {
      _visited: false,
      coords: [x, y],
      walls: { top: true, right: true, bottom: true, left: true },
    }
  }
}

let randomStartx;
let randomStarty;

Next, we will create a recursive function that receives a cell as a parameter. It will immediately set the visited state to true and then set up an array of potential neighbors to scan. We will then look at each neighbor and filter out any unvisited neighbors.

export const buildMaze = () => {

  const _buildMaze = cell => {
    cell._visited = true;

    const neighbors = [
      [maze[cell.coords[0] - 1]?.[cell.coords[1]], 'top'],
      [maze[cell.coords[0] + 1]?.[cell.coords[1]], 'bottom'],
      [maze[cell.coords[0]]?.[cell.coords[1] - 1], 'left'],
      [maze[cell.coords[0]]?.[cell.coords[1] + 1], 'right'],
    ];

    const unvisitedNeighbors = []
    for (const n of neighbors) {
      if (n && n[0] && !n[0]._visited) {
        unvisitedNeighbors.push(n);
      }
    };
    ...
  }
}

Within a while loop, we will randomly select an unvisited neighbor, and if it hasn't been visited remove the walls between the neighbor and the current cell. Next, we will call _buildMaze and pass the neighbor cell as a parameter.

while (unvisitedNeighbors.length) {
    const idx = parseInt(Math.random() * unvisitedNeighbors.length);
    const neighbor = unvisitedNeighbors.splice(idx, 1)[0];
    const neighborCell = neighbor[0];
    const wall = neighbor[1];

    if (!neighborCell._visited) {
        const neighborWall = wall == 'top' && 'bottom' ||
            wall == 'bottom' && 'top' ||
            wall == 'left' && 'right' ||
            wall == 'right' && 'left';
        cell.walls[wall] = false;
        neighborCell.walls[neighborWall] = false;
    
        _buildMaze(neighborCell);
    }
}

The recursive calling will end once we mark all the cells as visited. The buildMaze function will return the maze data structure to be passed into renderMaze. The job of renderMaze will iterate over our maze and create a maze with html elements. The function renderMaze will walk through each cell and remove each cell's top and left wall if needed.

conclusion

Every time this page is loaded a new maze will be rendered. The code can be found here.