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 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.
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;
} } } } }