我试图使用Javascript以递归方式解决迷宫,如何从递归函数调用返回我的解决方案?
我试图在Javascript中使用递归创建迷宫求解器算法。我的迷宫应遵循以下模式:
let rawMaze =
[
[0, 1, 3],
[0, 1, 0],
[2, 1, 0]
],
哪里
0: wall
1: valid path
2: start
3: end
我从源数组创建一个对象,
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);
}
我还使用辅助函数来获取任何给定单元格的邻居,
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;
}
主要逻辑发生在我的checkNeighbours函数中,在那里我确定下一个可能的移动并跟进它们,
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
);
});
}
然后我继续尝试将这一切放在一起并解决迷宫,
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);
}
我的问题如下。使用这个非常人为和简单的迷宫配置,我已经逐步完成了代码并且可以确认我的
checkNeighbours()
函数将递归到达结尾。此时,该函数有一个数组(变量路径),其中包含通过迷宫的正确步骤。如果您愿意,如何通过递归调用返回此分支?当有多个分支时会发生什么?我唯一能想到的是使用全局变量,但我觉得这不正确。
这是从React前端中删除的,这里是可运行的代码:
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);
}
我可能会建议添加另一个类:
function Path() {
this.isValidPath = false;
this.pathArray = [];
}
还重新加工checkNeighbours
函数来重命名/包含这些参数?
checkNeighbours(neighbours, paths, currentPathIndex, visited)
这样,paths
可以包含Path
类的数组,并且当您找到有效路径时可以将isValidPath
标志设置为true(假设您还希望在数组中包含无效和有效路径)。这将允许您返回所有路径(分支)。每个分支都位于paths
位置的currentPathIndex
数组中,一旦一条路径完成并且您想要开始搜索另一条路径,您将在代码中递增。
此外,目前checkNeighbours
函数似乎首先搜索有效的移动。也许如果您将其重新编写为深度优先遍历,那么您可以将每个有效路径(并排除任何无效路径)添加到您返回的路径数组中。