原创

js迷宫求解


在生成随机迷宫的基础上进行操作

生成随机迷宫异步: https://web03.cn/blog/252

通用的css以及js

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>生成迷宫</title>
    <style>
        html, body {
            width: 100%;
            height: 100%;
            padding: 0;
            margin: 0;
            text-align: center;
        }

        #map {
            display: inline-block;
            border: 2px solid #6a6f77;
            margin-top: 120px;
        }

        .line {
            height: 30px;
            width: 100%;
        }

        .wall, .road, .path {
            width: 30px;
            height: 30px;
            display: inline-block;
        }

        .wall {
            background: #45494c;
        }

        .road {
            background: #ffffff;
        }

        .path {
            background: #f57a7a;
        }
    </style>
</head>
<body>
<div id="map">

</div>
</body>
<script>
    const basicMap = [] // 迷宫数据
    const visited = [] // 逻辑访问数据
    const range = [[-1, 0], [0, 1], [1, 0], [0, -1]] // 偏移量
    const pathVisited = []//求解访问数据
    let exitX = 0
    let exitY = 0
    /**
     * 生成地基,每个可通行的方格都间隔一堵墙
     */
    function createBasis(x, y) {
        for (let i = 0; i < x; i++) {
            let line = new Array(y).fill(0)
            visited.push(new Array(y).fill(false))
            pathVisited.push(new Array(y).fill(false))
            if (i % 2 === 1) {
                for (let j = 0; j < line.length; j++) {
                    if (j % 2 === 1) {
                        line[j] = 1
                    }
                }
            }
            basicMap.push(line)
        }
    }

    /**
     * 渲染map
     */
    function renderMap() {
        const className = ['wall', 'road', 'path']
        let dom = ''
        for (let i = 0; i < basicMap.length; i++) {
            let line = '<div class="line">'
            for (let j = 0; j < basicMap[i].length; j++) {
                line += `<div class="${className[basicMap[i][j]]}"></div>`
            }
            line += '</div>'
            dom += line
        }
        const mapDom = document.getElementById('map')
        mapDom.style.height = 30 * basicMap.length + 'px'
        mapDom.style.width = 30 * basicMap[0].length + 'px'
        mapDom.innerHTML = dom
    }

    /**
     * 判断是否越界
     * @param x
     * @param y
     * @returns {boolean|boolean}
     */
    function isRange(x, y) {
        return x > 0 && x < basicMap.length - 1 && y > 0 && y < basicMap[0].length - 1
    }

    function* createMaze() {
        let stack = []
        stack.push({x: 1, y: 1})
        visited[1][1] = true
        while (stack.length > 0) {
            let curPos
            if (Math.random() > 0.5) {
                curPos = stack.shift()
            } else {
                curPos = stack.pop()
            }
            for (let i = 0; i < 4; i++) {
                let newX = curPos.x + range[i][0] * 2  // 两步是 *2
                let newY = curPos.y + range[i][1] * 2
                // 坐标没有越界 且 没有被访问过
                if (isRange(newX, newY) && !visited[newX][newY]) {
                    yield
                    basicMap[(newX + curPos.x) / 2][(newY + curPos.y) / 2] = 1
                    if (Math.random() > 0.5) {
                        stack.push({x: newX, y: newY})
                    } else {
                        stack.unshift({x: newX, y: newY})
                    }
                    visited[newX][newY] = true
                }
            }
        }
    }
</script>
</html>

深度优先、递归求解

在基础代码上增加求解方法

    let answerStep = 0 // 播放动画延时栈数
	    /**
     * 求解
     */
    function getMazePath(x, y) {
        if (isRange(x, y)) {
            pathVisited[x][y] = true // 求解时访问过
            // 渲染当前点
            timeOutRender(x, y, 2)
            if (x === exitX && y === exitY) {
                return true // 出口
            }
            // 遍历该点的四个方向是否可继续遍历
            for (let i = 0; i < 4; i++) {
                let newX = x + range[i][0]
                let newY = y + range[i][1]
                // 没有越界 是路 且没有被访问,继续访问
                if (isRange(newX, newY) && basicMap[newX][newY] === 1 && !pathVisited[newX][newY]) {
                    if (getMazePath(newX, newY)) {
                        return true
                    }
                }
            }
            // 没有return终止,回溯 遍历完四个方向都没有找到出口和其他能行的路(死胡同) 则表示该点不是解的路径上的点 还原为路
            timeOutRender(x, y, 1)
            return false
        }
    }

    /**
     * 延时动画
     * @param x
     * @param y
     * @param t
     */
    function timeOutRender(x, y, t) {
        setTimeout(() => {
            basicMap[x][y] = t
            renderMap()
        }, answerStep++ * 30)
    }

    // 创建29*29的地图,路的四面都为墙
    createBasis(29, 29)
    // 设置开始和结束点为左上角和右下角
    basicMap[1][1] = 1
    exitX = basicMap[0].length - 2
    exitY = basicMap.length - 2
    basicMap[exitX][exitY] = 1

    // 渲染地图
    renderMap()
    // 处理生成迷宫
    const createStep = createMaze()
    const t = setInterval(() => {
        let n = createStep.next()
        // 渲染地图
        renderMap()
        if (n.done) {
            // 求解
            getMazePath(1, 1)
            clearInterval(t)
        }
    }, 10)

过程
https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/images/a8469e7e316046f892c38f48ab5ebb6b.gif

demo:https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/demo/%E8%BF%B7%E5%AE%AB%E6%B1%82%E8%A7%A3_%E6%B7%B1%E5%BA%A6_%E9%80%92%E5%BD%92.html

非递归、栈、深度优先

    let prePath = [] // 上一次访问数据
    /**
     * 求解
     */
    function* getMazePath(x,y){
        let stack = []
        stack.unshift({x, y}) // 入栈
        while (stack.length > 0) {
            let curPos = stack.pop()
            pathVisited[curPos.x][curPos.y] = true // 求解时访问过
            basicMap[curPos.x][curPos.y] = 3
            renderMap()
            yield
            // 找到出口
            if (curPos.x === exitX && curPos.y === exitY) {
                // 绘制解
                basicMap[curPos.x][curPos.y] = 2
                renderMap()
                let prePos = prePath[curPos.x][curPos.y] // 获取上个点
                while(prePos != null) {
                    basicMap[prePos.x][prePos.y] = 2// 渲染上一个点
                    renderMap()
                    yield
                    prePos = prePath[prePos.x][prePos.y] // 获取上上个点
                }
                break;
            }

            for (let i = 0; i < 4; i++) {
                let newX = curPos.x + range[i][0]
                let newY = curPos.y + range[i][1]
                if (isRange(newX, newY) && basicMap[newX][newY] === 1 && !pathVisited[newX][newY]) {
                    prePath[newX][newY] = {x: curPos.x, y: curPos.y} // 记录新的点以及该点由谁走过来
                    stack.push({x: newX, y: newY}) // 入栈
                }
            }
        }
    }

    // 创建29*29的地图,路的四面都为墙
    createBasis(29, 29)
    // 设置开始和结束点为左上角和右下角
    basicMap[1][1] = 1
    exitX = basicMap[0].length - 2
    exitY = basicMap.length - 2
    basicMap[exitX][exitY] = 1

    // 渲染地图
    renderMap()
    // 处理生成迷宫
    const createStep = createMaze()
    const t = setInterval(() => {
        let n = createStep.next()
        // 渲染地图
        renderMap()
        if (n.done) {
            clearInterval(t)
            // 求解
            const answerStep = getMazePath(1,1)
            const t2 = setInterval(() => {
                let n2 = answerStep.next()
                // 渲染地图
                renderMap()
                if (n2.done) {
                    clearInterval(t2)
                }
            }, 30)
        }
    }, 10)

过程
https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/images/18db009dbfa94f2b80b682bbdc640039.gif

demo: https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/demo/%E8%BF%B7%E5%AE%AB%E6%B1%82%E8%A7%A3_%E9%9D%9E%E9%80%92%E5%BD%92_%E6%B7%B1%E5%BA%A6_%E6%A0%88.html

非递归、栈、广度优先

    let prePath = [] // 上一次访问数据
    /**
     * 求解
     */
    function* getMazePath(x,y){
        let stack = []
        stack.unshift({x, y}) // 入栈
        while (stack.length > 0) {
            let curPos = stack.shift()
            pathVisited[curPos.x][curPos.y] = true // 求解时访问过
            basicMap[curPos.x][curPos.y] = 3
            renderMap()
            yield
            // 找到出口
            if (curPos.x === exitX && curPos.y === exitY) {
                // 绘制解
                basicMap[curPos.x][curPos.y] = 2
                renderMap()
                let prePos = prePath[curPos.x][curPos.y] // 获取上个点
                while(prePos != null) {
                    basicMap[prePos.x][prePos.y] = 2// 渲染上一个点
                    renderMap()
                    yield
                    prePos = prePath[prePos.x][prePos.y] // 获取上上个点
                }
                break;
            }

            for (let i = 0; i < 4; i++) {
                let newX = curPos.x + range[i][0]
                let newY = curPos.y + range[i][1]
                if (isRange(newX, newY) && basicMap[newX][newY] === 1 && !pathVisited[newX][newY]) {
                    prePath[newX][newY] = {x: curPos.x, y: curPos.y} // 记录新的点以及该点由谁走过来
                    stack.push({x: newX, y: newY}) // 入栈
                }
            }
        }
    }

    // 创建29*29的地图,路的四面都为墙
    createBasis(29, 29)
    // 设置开始和结束点为左上角和右下角
    basicMap[1][1] = 1
    exitX = basicMap[0].length - 2
    exitY = basicMap.length - 2
    basicMap[exitX][exitY] = 1

    // 渲染地图
    renderMap()
    // 处理生成迷宫
    const createStep = createMaze()
    const t = setInterval(() => {
        let n = createStep.next()
        // 渲染地图
        renderMap()
        if (n.done) {
            clearInterval(t)
            // 求解
            const answerStep = getMazePath(1,1)
            const t2 = setInterval(() => {
                let n2 = answerStep.next()
                // 渲染地图
                renderMap()
                if (n2.done) {
                    clearInterval(t2)
                }
            }, 30)
        }
    }, 10)

过程
https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/images/04a1a296b193406c812bacb7bbdc0cf9.gif

demo: https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/demo/%E8%BF%B7%E5%AE%AB%E6%B1%82%E8%A7%A3_%E9%9D%9E%E9%80%92%E5%BD%92_%E5%B9%BF%E5%BA%A6_%E6%A0%88.html

深度与广度的差别在于,取当前格子的时候使用shift()和pop()
因为入栈是push,旁边四个都是先入栈,在栈底,pop()取栈尾,会先寻找更深的路径【深度】, 相反,如果是shift()的话,你旁边的一入栈就进行路径的校验寻找,就会把边上所有的都找完才会去找更深的地方【广度】

JavaScript
算法技巧
  • 作者:零三(联系作者)
  • 最后更新时间:2021-05-30 15:20
  • 版权声明:自由转载-非商用-非衍生-保持署名
  • 转载声明:来源地址 https://web03.cn