Skip to content

Instantly share code, notes, and snippets.

@miladabc
Created July 7, 2018 16:45
Show Gist options
  • Save miladabc/607f962f008ccfed9a6e1f9502688c58 to your computer and use it in GitHub Desktop.
Save miladabc/607f962f008ccfed9a6e1f9502688c58 to your computer and use it in GitHub Desktop.
Finding the first available path in a maze
//Milad Abbasi
//06-07-2018
//Finding the first available path in a maze
var buckets = require('../modules/buckets.js');
var stack = new buckets.Stack();
function Element(row, col, dir) {
this.row = row;
this.col = col;
this.dir = dir;
}
const mazeRow = 12, mazeCol = 12;
const exitRow = mazeRow -2, exitCol = mazeCol - 2;
var row, col, nextRow, nextCol, dir;
var found = false;
var position = new Element(1, 1, 1);
var visited = new Array(mazeRow -2)
for (var i = 0; i < mazeRow -2; i++)
visited[i] = new Array(mazeCol - 2);
visited[1][1] = 1;
var move = [
[-1, 0], //N
[-1, 1], //NE
[0, 1], //E
[1, 1], //SE
[1, 0], //S
[1, -1], //EW
[0, -1], //W
[-1, -1] //NW
];
var maze = [
[1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1],
[1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1],
[1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1],
[1 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 1],
[1 , 1 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 1],
[1 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1],
[1 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1],
[1 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1],
[1 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1],
[1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1],
[1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 1],
[1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1]
];
stack.push([1, 1, 1]);
while(!stack.isEmpty() && !found){
row = position.row = stack.peek()[0];
col = position.col = stack.peek()[1];
dir = position.dir = stack.peek()[2];
stack.pop();
while(dir < 8 && !found){
nextRow = row + move[dir][0];
nextCol = col + move[dir][1];
if(nextRow == exitRow && nextCol == exitCol)
found = true;
else if(!maze[nextRow][nextCol] && !visited[nextRow][nextCol])
{
visited[nextRow][nextCol] = 1;
position.row = row;
position.col = col;
position.dir = ++dir;
stack.push([position.row, position.col, position.dir]);
row = nextRow;
col = nextCol;
dir = 0;
}
else
dir++;
}
}
if(found){
console.log('The path is:');
console.log(`(${exitRow}, ${exitCol})`);
console.log(`(${row}, ${col})`);
while(!stack.isEmpty()){
console.log(`(${stack.peek()[0]}, ${stack.peek()[1]})`);
stack.pop();
}
}
else
console.log('The maze does NOT have a path!');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment