I am trying to recursively solve a maze using Javascript, how do I return my solution from my recursive function call?
I am attempting to create a maze solver algorithm using recursion, in Javascript. My maze shall follow the following pattern:
let rawMaze =
[
[0, 1, 3],
[0, 1, 0],
[2, 1, 0]
],
Where
0: wall
1: valid path
2: start
3: end
I create an object from the source array,
let maze = []
constructMaze() {
for (let i = 0; i < 3; i++) {
maze[i] = [];
for (let j = 0; j < 3; j++) {
const Cell = {
x: j,
y: i,
state: rawMaze[i][j],
id: uniqueId()
};
this.maze[i].push(Cell);
}
}
console.table(this.maze);
}
I also use a helper function to get the neighbours of any given cell,
getNeighbours(x, y) {
let maze = this.maze;
let neighbours = [];
maze.forEach(row => {
row.forEach(cell => {
if (
(cell.x == x && cell.y == y + 1) ||
(cell.x == x && cell.y == y - 1) ||
(cell.y == y && cell.x == x + 1) ||
(cell.y == y && cell.x == x - 1)
) {
neighbours.push(cell);
}
});
});
return neighbours;
}
The main logic happens in my checkNeighbours function, where I determine the next possible moves and follow them up,
checkNeighbours(neighbours, path, visited) {
let validMoves = [];
neighbours.forEach(potentialMove => {
if (visited.indexOf(potentialMove.id) < 0) {
if (potentialMove.state !== 0) {
validMoves.push(potentialMove);
}
}
});
if (validMoves.length === 0) {
return;
} else {
let finish = validMoves.filter(cell => cell.state === 3);
console.log(finish);
if (finish.length === 1) {
return path;
}
}
validMoves.forEach(validMove => {
path.push(validMove);
visited.push(validMove.id);
this.checkNeighbours(
this.getNeighbours(validMove.x, validMove.y),
path,
visited
);
});
}
I then proceed to try and put this all together and solve the maze,
initSolve(maze) {
let maze = maze;
let start = [];
let paths = [];
let visited = [];
let current = null;
maze.forEach(row => {
row.forEach(cell => {
// Is start?
if ((start.length == 0) & (cell.state == 2)) {
start.push(cell);
visited.push(cell.id);
current = cell;
}
});
});
let result = this.checkNeighbours(
this.getNeighbours(current.x, current.y),
paths,
visited
);
console.log("test", result);
}
My question is the following. Using this very contrived and simple maze configuration, I have stepped through the code and can confirm that my
checkNeighbours()
function will recursively arrive at the end. At that point, the function has an array (the variable path) that contains the correct steps through the maze. How do I return this branch, if you will, from the recursive call? What happens when there are multiple branches? The only thing I can think of is using a global variable, but I feel this can not be correct.
This is ripped from a React frontend , here is runnable code:
let rawMaze = [
[0, 1, 3],
[0, 1, 0],
[2, 1, 0]
]
let maze = []
function constructMaze() {
let counter = 0
for (let i = 0; i < 3; i++) {
maze[i] = [];
for (let j = 0; j < 3; j++) {
const Cell = {
x: j,
y: i,
state: rawMaze[i][j],
id: counter
};
maze[i].push(Cell);
counter++
}
}
}
function getNeighbours(x, y) {
let maze = this.maze;
let neighbours = [];
maze.forEach(row => {
row.forEach(cell => {
if (
(cell.x == x && cell.y == y + 1) ||
(cell.x == x && cell.y == y - 1) ||
(cell.y == y && cell.x == x + 1) ||
(cell.y == y && cell.x == x - 1)
) {
neighbours.push(cell);
}
});
});
return neighbours;
}
function checkNeighbours(neighbours, path, visited) {
let validMoves = [];
neighbours.forEach(potentialMove => {
if (visited.indexOf(potentialMove.id) < 0) {
if (potentialMove.state !== 0) {
validMoves.push(potentialMove);
}
}
});
if (validMoves.length === 0) {
return;
} else {
let finish = validMoves.filter(cell => cell.state === 3);
console.log(finish);
if (finish.length === 1) {
return path;
}
}
validMoves.forEach(validMove => {
path.push(validMove);
visited.push(validMove.id);
this.checkNeighbours(
this.getNeighbours(validMove.x, validMove.y),
path,
visited
);
});
}
function initSolve() {
let maze = constructMaze()
let start = [];
let paths = [];
let visited = [];
let current = null;
maze.forEach(row => {
row.forEach(cell => {
// Is start?
if ((start.length == 0) & (cell.state == 2)) {
start.push(cell);
visited.push(cell.id);
current = cell;
}
});
});
let result = this.checkNeighbours(
this.getNeighbours(current.x, current.y),
paths,
visited
);
console.log("test", result);
}
Might I recommend adding another class:
function Path() {
this.isValidPath = false;
this.pathArray = [];
}
And also reworking the checkNeighbours function to rename/include these parameters?
checkNeighbours(neighbours, paths, currentPathIndex, visited)
This way, paths could contain an array of Path classes, and you could set the isValidPath flag to true when you found a valid path (assuming you want to also include invalid and valid paths in the array). This would allow you to return all paths (branches). Each branch would be in the paths array at position currentPathIndex, which you'd increment in the code once one path is complete and you want to start searching for another path.
Also, currently the checkNeighbours function appears to do a breadth first search for valid moves. Perhaps if you reworked it into more of a depth-first traversal, then you could add each valid path (and exclude any invalid paths) to the paths array you return.