迷宫求解器跳过Javasript块

Question

我正在尝试制作迷宫求解器，但有时会跳过块。该代码解决了二维数组中的迷宫问题。我认为每次回溯都会发生跳过。在代码b中是一堵墙，p是一个已访问的块。

function solveMaze(maze, start, end){
    let here = start,
    path = [here]
    maze[here.y][here.x] = 'p'

    while(!(path[path.length-1].x == end.x && path[path.length-1].y == end.y)){
        let options = [{x: here.x + 1, y: here.y}, {x: here.x - 1, y: here.y}, {x: here.x, y: here.y + 1}, {x: here.x, y: here.y - 1}]
        let moves = []

        for(let i = 0; i < options.length; i++){
            if(typeof maze[options[i].y] !== 'undefined' && typeof maze[options[i].y][options[i].x] !== 'undefined' && maze[options[i].y][options[i].x] != 'b' && maze[options[i].y][options[i].x] != 'p'){
                moves.push(options[i])
            }
        }
        if(moves.length){
            let next = moves[Math.floor(Math.random()*moves.length)]

            maze[next.y][next.x] = 'p'

            path.push(here = next)
        }
        else{
            here = path.pop()
        }
    }
    return path
}

Fiddle

Answer 1

看起来问题是当您备份并尝试其他路径时。因此，将当前位置放回路径堆栈中。

此：

   maze[next.y][next.x] = 'p'

   path.push(here = next)

成为：

   maze[next.y][next.x] = 'p'
   path.push(here)  // put the current location back on there
   path.push(here = next)

位置会被添加到路径中，因此会重复很多次，因此，如果您使用路径进行计数，那么它将不准确，但是对于绘制红色路径，这是个不错的选择。

顺便说一下，如果您只需要唯一性，则可以使用Set或尝试更改推送/弹出逻辑。