Maze Building (part 2)

The next step in our journey to build a more perfect maze is to implement an algorithm to explore and find the endpoint in our maze. One of the most famous and efficient algorithms is the A* algorithm. The A* is a fun algorithm to implement because it follows a set of procedures that are similar to what a human might try do when reasoning to find the best path. In this post we will walk through the algorithm and implement it in Javascript. The goal of this post is to build upon our mazer application using this algorithm.

Generating a graph

Before delving into the heuristics of the A* algorithm, it's worth taking time to get our maze data structure into a shape that will make it easier to explore the maze. One way is to generate a simple graph of the maze. The graph will be an array of arrays that hold cells and only their associated neighbors. A cell cannot be a neighbor if there is a wall between them.

export const mazeToGraph = (maze) => {
  let graph = {};
  for (let x = 0; x < maze.length; x++) {
    for (let y = 0; y < maze[x].length; y++) {
      const cell = maze[x][y];
      const possibleNeighbors = {
        top: maze[cell.coords[0] - 1]?.[cell.coords[1]],
        bottom: maze[cell.coords[0] + 1]?.[cell.coords[1]],
        left: maze[cell.coords[0]]?.[cell.coords[1] - 1],
        right: maze[cell.coords[0]]?.[cell.coords[1] + 1],
      };
      for (const wall of Object.keys(cell.walls)) {
        if (cell.walls[wall]) {
          delete possibleNeighbors[wall];
        }
      }

      graph[`[${x},${y}]`] = [];
      for (const n of Object.values(possibleNeighbors)) {
        graph[`[${x},${y}]`].push(JSON.stringify(n.coords));
      }
    }
  }
  return graph;
};

Algorithm overview

There is an excellent write up on how the A* algorithm works on Wikipedia. However, my simplified explanation is the algorithm starts at a specified node in a graph. It has a goal of reaching an end goal. The first thing we do is keep track of all available nodes we need to examine, the first one in this case is our starting node. We can actually just do this by creating a JS set.

export const aStar = (start, goal, h, graph, maze) => {
  const openSet = new Set([start]);
  const closedSet = new Set();
  ...

We will have both an openSet and a closedSet. The openSet will include nodes we need to explore, and the closedSet will be a list of nodes we have already visited and excluded. The start is a node in our graph, and we will set a couple of values on this node. The first value is what is referred to as the g value. The g value represents the cost needed to traverse this node from the start node. Wikipedia sets this value to be the value of the h value (more on that in a minute), but for our initial implementation, we will set this to 0. Next to we need to also calculate the cost from our current node to the goal. This value will be represented by h and will be generated by a heuristic function. The function we will use is Manhattan distance., which is perfect for grid distances. For formula is represented in the following way:

$$ \text{h}(a, b) = |x_1 - x_2| + |y_1 - y_2| $$ In Javascript our function will be passed into our aStar function and we will calculate this distance for each node:

const path = aStar(start, end, (start, goal) => {
        return Math.abs(start.coords[0] - goal.coords[0]) + Math.abs(start.coords[1] - goal.coords[1])  
      }, graph, maze)

As we mentioned for our start node, we will set our g value to 0. Our h value will be calculated from the current node to the goal. Our current node in this case is start. Finally we will set our parent to null. Next we we will run the algorithm while we have each value in our openSet. Within the while loop, we will sort our openSet based on the lowest f-score. The f score will be the nodes g + h values. Since our first node has an f of undefined, it will be the first node or the current node we will examine. If the node coords match the goal, then we are done with our algorithm, and we will build a path and return it. Finally, we will remove this node from our openSet and add it to our closedSet.

start.g = 0;
  start.h = h(start, goal);
  start.parent = null;

  while (openSet.size > 0) {
    const current = [...openSet].sort((a, b) => a.f - b.f)[0];
    if (
      current.coords[0] === goal.coords[0] &&
      current.coords[1] === goal.coords[1]
    ) {
      const path = [];
      let temp = current;
      while (temp) {
        path.push(temp);
        temp = cameFrom.get(temp);
      }
      return path.reverse();
    }

    openSet.delete(current);
    closedSet.add(current);

The next part of the algorithm consists of examining each neighbor. We set each neighbor's g value to be infinity and we calculate a tentative g value which is our current node + 1 If we find a neighbor that has a value that is greater than the tentative g we capture the neighbors parent, assign its g score, calculate its h score, and finally its f score. And then if the neighbor is not in the openSet, we add it so we can examine its neighbors the next go around.

Display the maze

Now that we have a path, we can display the path and watch the algorithm find its way through the maze to the end. We just shift each node from the path, find it in our drawn maze, and set the color.

const intv = setInterval(() => {
        const node = path.shift();
        if (!node) {
          clearInterval(intv);
          return;
        }
        const current = maze[node.coords[0]][node.coords[1]];
        document.getElementById(`cell-${current.coords[0]}-${current.coords[1]}`)
                .style.backgroundColor = "blue";
      }, 300);

Where to go next

There are other possibilities now that we have a maze finder. Solving mazes is fun, but what if we tweak the algorithm to find a moving target? We could design a game where enemies are dispersed through the maze and using the A* algorithm, they seek out the hero of the game.