原创

js生成随机迷宫


迷宫说明

1、只有一个出口,一个入口
2、入口到出口路径是相通的且只有一条唯一的路径

生成方式原理

生成矩阵basicMap的时候,先规定路都被墙包围,并且生成一份用来遍历标识的数据visited,在遍历过程中,标识每一次遍历的格子在visited总标识,取当前临近的上下左右四个格子,并且判断坐标没有越界 且 没有被访问过,打通两个路之间的墙,使得两个路联通

通用style与html

<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 {
        width: 30px;
        height: 30px;
        display: inline-block;
    }

    .wall {
        background: #45494c;
    }

    .road {
        background: #ffffff;
    }

    .cre {
        background: #0366D6;
    }
</style>
<body>
<div id="map">

</div>

栈的方式递归生成

const basicMap = [] // 迷宫数据
const visited = [] // 逻辑访问数据
const range = [[-1, 0], [0, 1], [1, 0], [0, -1]] // 偏移量
/**
 * 生成地基,每个可通行的方格都间隔一堵墙
 */
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))
        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']
    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 = 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
                stack.unshift({x: newX, y: newY})
                visited[newX][newY] = true
            }
        }
    }
}

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

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

过程

用固定的数组操作,规则是非随机的

demo: https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/demo/%E7%94%9F%E6%88%90%E8%BF%B7%E5%AE%AB_%E6%B7%B1%E5%BA%A6_%E6%A0%88.html

递归的方式递归生成

const basicMap = [] // 迷宫数据
const visited = [] // 逻辑访问数据
let createStep = 0 // 播放动画延时栈数
const range = [[-1, 0], [0, 1], [1, 0], [0, -1]] // 偏移量
/**
 * 生成地基,每个可通行的方格都间隔一堵墙
 */
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))
        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']
    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(x = 1, y = 1) {
    // 记录当前被访问
    visited[x][y] = true
    for (let i = 0; i < 4; i++) {
        let newX = x + range[i][0] * 2
        let newY = y + range[i][1] * 2
        // 判断坐标是否越界 且 没有被访问过
        if (isRange(newX, newY) && !visited[newX][newY]) {
            setTimeout(() => {
                // 打通两个方块之间的墙
                basicMap[(newX + x) / 2][(newY + y) / 2] = 1
                renderMap()
            }, createStep++ * 100)
            createMaze(newX, newY)
        }
    }
}

// 创建19*19的地图,路的四面都为墙
createBasis(19, 19)
// 设置开始和结束点为左上角和右下角
basicMap[1][0] = 1
basicMap[basicMap[0].length - 2][basicMap.length - 1] = 1
// 渲染地图
renderMap()
// 处理生成迷宫
createMaze()

过程

用固定的数组操作,规则是非随机的

demo: https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/demo/%E7%94%9F%E6%88%90%E8%BF%B7%E5%AE%AB_%E6%B7%B1%E5%BA%A6_%E9%80%92%E5%BD%92.html

随机队列

const basicMap = [] // 迷宫数据
const visited = [] // 逻辑访问数据
const range = [[-1, 0], [0, 1], [1, 0], [0, -1]] // 偏移量
/**
 * 生成地基,每个可通行的方格都间隔一堵墙
 */
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))
        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']
    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
            }
        }
    }
}

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

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

过程

在【栈的方式递归生成】的基础上,加上随机的stack栈处理,实现随机迷宫

demo: https://web03-1252477692.cos.ap-guangzhou.myqcloud.com/blog/demo/%E7%94%9F%E6%88%90%E8%BF%B7%E5%AE%AB_%E9%9A%8F%E6%9C%BA%E9%98%9F%E5%88%97.html

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