Solution to Maze Solver
The solution to the implementation of classes and their inheritance along with methods to solving a maze in JavaScript.
We'll cover the following...
Final step to check if a maze is solvable
With helper methods ready and the maze in front of us, we can finally implement a solution. The method solve
takes the source and target indices and to tell if the maze is solvable. Look at the solution below.
Press + to interact
index.js
grid.js
const Grid = require('./grid').gridClass;// Create MazeSolver class belowclass MazeSolver extends Grid{constructor(arr){super(arr); // initialize the grid}canTraverse(x,y){// check boundsif (x < 0 || y < 0)return false;else if (x >= this.grid.length)return false;else if (y >= this.grid[x].length)return false;// check if 0 or notelse if(this.grid[x][y]===0)return false;elsereturn true; // all passsed}getNeighbours(x,y){// return array of neighboursvar neighbours = [];// upif(this.canTraverse(x-1, y))neighbours.push([x-1,y]);// downif(this.canTraverse(x+1, y))neighbours.push([x+1,y]);// leftif(this.canTraverse(x, y-1))neighbours.push([x,y-1]);// rightif(this.canTraverse(x, y+1))neighbours.push([x,y+1]);return neighbours;}checkVisited(x,y,visited){// traverse array for visited// console.log(x,y,visited)for(var i= 0; i< visited.length; i++){if(visited[i][0]=== x && visited[i][1]===y){return true;}}return false;}solve(x1,y1, x2, y2){// solve from coordinates (x, y)var stack = []; // maintain coordinatesvar visited = [];// check if initial position can be traversedif(this.canTraverse(x1,y1)){visited.push([x1,y1]);stack.push([x1,y1]);}var solved = false;while(stack.length > 0){var currentPos = stack.pop();if(currentPos[0] === x2 && currentPos[1] === y2){// target found and so exit loopsolved = true;break;}// target not found and so traverse neighboursvar neighbours = this.getNeighbours(currentPos[0], currentPos[1]);for(var i = 0; i < neighbours.length; i++){// check visited and if not, throw in stackif (!this.checkVisited(neighbours[i][0],neighbours[i][1],visited)){visited.push([neighbours[i][0],neighbours[i][1]]);stack.push([neighbours[i][0],neighbours[i][1]]);}}}return solved;}}var arr = [[0, 1, 1, 1, 0],[0, 1, 1, 1, 0],[0, 1, 1, 1, 0],[0, 1, 1, 1, 0],[0, 1, 1, 1, 0],]var maze = new MazeSolver(arr);console.log("check solavable -> source (0, 1) and Dest (4,3):")console.log(maze.solve(0,1,4,3));console.log("check solavable -> source (0, 0) and Dest (4,3):")console.log(maze.solve(0,0,4,3));console.log("check solavable -> source (0, 1) and Dest (3,3):")console.log(maze.solve(0,1,3,3));console.log("check solavable -> source (0, 1) and Dest (4,4):")console.log(maze.solve(0,1,4,4));
The solve method
takes 2 pairs of coordinates; x1
and y1
are the source while x2
and y2
are the destination indices. The solution works like this.
-
Initialize an empty array to track which indices to traverse next by the name of ...