Math Home
Programming

Overview

In this lesson we create a program which will solve a maze that is drawn by the user. To make the boundaries of the maze clear, we use a grid of squares to show the open space and walls of the maze.

The Maze Solver


The Code

The elements needed are a canvas to draw the maze, a buttom to run the solve function, a button to reset the maze, and a paragraph to indicate when a maze has no solution. Here is the HTML:

<canvas id='myCanvas' width='600' height='600'></canvas><br \>
<button onclick = "solveMaze()">Solve!</button>
<button onclick = "reset()">Reset</button>
<p id="outcome"></p>
<script src="maze.js"></script>
		


JavaScript

Click the code or the description to see the connection.

Comments
JavaScript
>Set up a grid of tiles on which to draw the squares. All of the squares are initialized to empty (state e).
>Set the state of the top left square as start (state s), and the state of the bottom right square as finish (state f).
>Create variables for the canvas, its context, and the output message. Initialize the variables when the window loads.
>The maze will run as an animation. Use a loop to update the image of the maze. The maze will be rendered as follows:
>>Clear the screen.
>>Draw the squares by looping through all the tiles.
>>>The rect function is used to render the squares. The state determines the color of the square.
>Create a function that allows the user to change the state of square from empty to wall and back.
>>Use boundX and boundY to prevent the square from rapidly flipping states back and forth.
>>Create a function that also allows users to change the state of squares when they drag the mouse.
>>>The dragging function will require a function that stops squares from changing state when the mouse is released.
>Create a function that solves the maze. The maze will be solved by tracking a current location. All the empty spaces around the location will be stored as places to check.
>>Create a queue of places to check.
>>Create xLoc and yLoc to store the current (x,y) location.
>>Search the maze until a path from start to finish has been found or there is nowhere left to search.
>>>Move the (x,y) location to the next point in the queue of points to be explored. To solve the maze quickly, move to the point that is closest to the finish.
>>>After moving to the next (x,y) location, remove the location from the queue. A position does not need to be explored more than once.
>>>Check whether the finish square is next to the current (x,y) location. If so, a path has been found.
>>>Check all of the neighbors of the current (x,y) location. If they are empty, store them in the queue as places that need to be checked. Keep track of the path to get to the location by storing the state as a string of letters u, d, l and r for up, down, left and right.
>>If no path been found using the above steps, then no path exists. Update the output to indicate that there is no solution.
>>If a path has been found, update the output to indicate the maze has been solved.
>>>Use the state of the final location which is a string of letters 'u', 'd', 'l' and 'r' for up, down, left, and right to color the solution. Change the states of all squares in the solution to 'x'.
>Create a function that resets the program to its original state.
tileW = 20;
tileH = 20;

tileRowCount = 25;
tileColumnCount = 25;

var tiles = [];
for (c = 0; c < tileColumnCount; c++) {
  tiles[c] = [];
  for (r = 0; r < tileRowCount; r++) {
    tiles[c][r] = {x: c*(tileW+3), y: r*(tileH+3), state: 'e'}; //state is e for empty
  }
}
tiles[0][0].state = 's';
tiles[tileColumnCount-1][tileRowCount-1].state = 'f';
boundX = 0;
boundY = 0;
var canvas;
var ctx;
var output;

window.onload = function () {
  canvas = document.getElementById("myCanvas");
  ctx = canvas.getContext("2d");
  output = document.getElementById("outcome");
  canvas.onmousedown = myDown;
  canvas.onmouseup = myUp;
  return setInterval(draw, 10);
}
function rect(x,y,w,h,state) {
  //red red green green blue blue
  if (state == 's') {
    ctx.fillStyle = '#00FF00';
  }
  else if (state == 'f') {
    ctx.fillStyle = '#FF0000';
  }
  else if (state == 'e') {
    ctx.fillStyle = '#CCCCCC';
  }
  else if (state == 'w') {
    ctx.fillStyle = '#003366';
  }
  else if (state == 'x') {
    ctx.fillStyle = '#FFCC00';
  }
  else {
    ctx.fillStyle = '#CCCCCC';
  }

  ctx.beginPath();
  ctx.rect(x,y,w,h);
  ctx.closePath();
  ctx.fill();
}
function draw() {
  ctx.clearRect(0,0,canvas.width,canvas.height);
  for (c = 0; c < tileColumnCount; c++) {
    for (r = 0; r < tileRowCount; r++) {
      rect(tiles[c][r].x, tiles[c][r].y, tileW, tileH, tiles[c][r].state);
    }
  }
}
function distanceToFinish (xVal, yVal) {
  return (xVal-24)*(xVal-24) + (yVal-24)*(yVal-24);
}
function solveMaze() {
  var queue = [[0, 0]];
  var xLoc;
  var yLoc;
  var pathFound = false;
  while (queue.length > 0 && !pathFound) {
    xLoc = queue[0][0];
    yLoc = queue[0][1];
    var index = 0;
    for (var i = 1; i < queue.length; i++) {
      if (distanceToFinish(queue[i][0], queue[i][1]) < distanceToFinish(xLoc, yLoc)) {
        xLoc = queue[i][0];
        yLoc = queue[i][1];
        index = i;
      }
    }
    queue.splice(index, 1);
    if (xLoc < tileColumnCount - 1) {
      if (tiles[xLoc+1][yLoc].state == 'f') {
        pathFound = true;
      }
    }
    if (yLoc < tileRowCount - 1) {
      if (tiles[xLoc][yLoc+1].state == 'f') {
        pathFound = true;
      }
    }
    if (xLoc > 0) {
      if (tiles[xLoc-1][yLoc].state == 'e') {
        queue.push([xLoc-1, yLoc]);
        tiles[xLoc-1][yLoc].state = tiles[xLoc][yLoc].state + 'l';
      }
    }
    if (xLoc < tileColumnCount - 1) {
      if (tiles[xLoc+1][yLoc].state == 'e') {
        queue.push([xLoc+1, yLoc]);
        tiles[xLoc+1][yLoc].state = tiles[xLoc][yLoc].state + 'r';
      }
    }
    if (yLoc > 0) {
      if (tiles[xLoc][yLoc-1].state == 'e') {
        queue.push([xLoc, yLoc-1]);
        tiles[xLoc][yLoc-1].state = tiles[xLoc][yLoc].state + 'u';
      }
    }
    if (yLoc < tileRowCount - 1) {
      if (tiles[xLoc][yLoc+1].state == 'e') {
        queue.push([xLoc, yLoc+1]);
        tiles[xLoc][yLoc+1].state = tiles[xLoc][yLoc].state + 'd';
      }
    }
  }
  if (!pathFound) {
    output.innerHTML = 'No Solution';
  }
  else {
    output.innerHTML = 'Solved!';
    var path = tiles[xLoc][yLoc].state;
    var pathLength = path.length;
    var currX = 0;
    var currY = 0;
    for (var i = 0; i < pathLength-1; i++) {
      if (path.charAt(i+1) == 'u') {
        currY -= 1;
      }
      if (path.charAt(i+1) == 'd') {
        currY += 1;
      }
      if (path.charAt(i+1) == 'r') {
        currX += 1;
      }
      if (path.charAt(i+1) == 'l') {
        currX -= 1;
      }
      tiles[currX][currY].state = 'x';
    }
  }
}
function reset() {
  for (c = 0; c < tileColumnCount; c++) {
    tiles[c] = [];
    for (r = 0; r < tileRowCount; r++) {
      tiles[c][r] = {x: c*(tileW+3), y: r*(tileH+3), state: 'e'}; //state is e for empty
    }
  }
  tiles[0][0].state = 's';
  tiles[tileColumnCount-1][tileRowCount-1].state = 'f';

  output.innerHTML = 'Green is start. Red is finish.';
}
function myMove(e) {
  x = e.pageX - canvas.offsetLeft;
  y = e.pageY - canvas.offsetTop;

  for(c=0; c < tileColumnCount; c++) {
    for(r=0; r < tileRowCount; r++) {
      if (c*(tileW+3) < x && x < c*(tileW+3)+tileW && r*(tileH+3) < y && y < r*(tileH+3)+tileH) {
        if (tiles[c][r].state == "e" && (c != boundX || r != boundY)) {
          tiles[c][r].state = "w";
          boundX = c;
          boundY = r;
        }
        else if (tiles[c][r].state == "w" && (c != boundX || r != boundY)) {
          tiles[c][r].state = "e";
          boundX = c;
          boundY = r;
        }
      }
    }
  }
}
function myUp() {
  canvas.onmousemove = null;
}
function myDown(e) {
  canvas.onmousemove = myMove;
  x = e.pageX - canvas.offsetLeft;
  y = e.pageY - canvas.offsetTop;

  for(c=0; c < tileColumnCount; c++) {
    for(r=0; r < tileRowCount; r++) {
      if (c*(tileW+3) < x && x < c*(tileW+3)+tileW && r*(tileH+3) < y && y < r*(tileH+3)+tileH) {
        if (tiles[c][r].state == "e") {
          tiles[c][r].state = "w";
          boundX = c;
          boundY = r;
        }
        else if (tiles[c][r].state == "w") {
          tiles[c][r].state = "e";
          boundX = c;
          boundY = r;
        }
      }
    }
  }
}