js迷宫自动走html JavaScript简单实现迷宫问题求解

前言

想起大学时老师让用Java GUI解决迷宫问题，当时还真给做出来了，可惜代码不见了

预览

介绍

使用JavaScript解决迷宫问题(使用vue-cli@3搭建环境)，使用深度优先搜索算法计算所有通路条数，并展示最优解之一

环境使用了Element中一些组件和easyicon的一些图标

实现

核心组件

迷宫问题实现-之间

图标来自

href=""

target="_blank">easyicon

v-model="form.row"

:min="limit.min"

:max="limit.max"

@blur="inputBlur"

@change="generateMap"

>

v-model="form.col"

:min="limit.min"

:max="limit.max"

@blur="inputBlur"

@change="generateMap"

>

重置

计算

随机障碍

class="maze-row"

v-for="i of form.row"

:key="`row${i}`">

class="maze-step"

v-for="j of form.col"

:class="mazeStyle[displayMaze[i-1][j-1]]"

:key="`col${j}`"

@click="changeStatus(i,j)"

>

当前迷宫有{{result.routeCount}}条出路，图中显示为最优解之一

import {initMaze, redisplay, findAllRoutes} from '@/utils'

/**

* 规则0-可过，1-障碍，2-死胡同，3-往右，4-往下，5-往左，6-往上

*/

export default {

data() {

return {

form: {

row: 4,

col: 4

},

// 表单限制

limit: {

min: 2,

max: 10

},

// 迷宫

maze: [],

displayMaze: [],

// 迷宫位置样式

mazeStyle: [

'',

'obstacle',

'',

'go-right',

'go-down',

'go-left',

'go-up'

],

// 是否已经计算过了

// 计算过在布置障碍的时候，需要深度遍历

calculated: false,

// 计算出的路线总汇

result: {routeCount: 0, bestRoute: []}

}

},

watch: {

maze(val) {

this.displayMaze = val

}

},

created() {

this.generateMap()

this.displayMaze = this.maze

},

methods: {

// 输入框失去焦点

inputBlur() {

// 删除后该组件不会赋默认值，手动赋值

if (!this.form.row) {

this.form.row = 5

} else if (!this.form.col) {

this.form.col = 5

}

},

// 生成地图

generateMap() {

this.maze = initMaze(this.form)

},

// 生成障碍

autoObstacle() {

this.maze = initMaze(this.form, true)

},

// 计算

calculate() {

// 设置已计算过

this.calculated = true

this.result = findAllRoutes(this.maze)

if (this.result.routeCount === 0) {

this.$message.error('没有出路！！！')

} else {

this.displayMaze = redisplay(this.maze, this.result.bestRoute).maze

}

},

// 在当前位置移除或添加障碍

changeStatus(i, j) {

// 如果是第一个或最后一个，则退出

if ((i === 1 && i === j) || (i === this.form.row && j === this.form.col))

return

// 设置障碍

this.maze[i - 1][j - 1] = this.maze[i - 1][j - 1] ? 0 : 1

// 重置一下地图

if (this.calculated) {

this.calculated = false

this.maze = this.maze.map(row => row.map(col => col !== 1 ? 0 : 1))

} else {

// 简单重塑maze

this.maze = this.maze.filter(() => true)

}

}

}

}

// 小方格border

$step-border: 1px solid;

#app {

display: flex;

justify-content: center;

}

// 障碍

.obstacle {

background-image: url("./assets/images/obstacle.png");

}

// 向左走

.go-left {

background-image: url("./assets/images/left.png");

}

.go-right {

background-image: url("./assets/images/right.png");

}

.go-up {

background-image: url("./assets/images/up.png");

}

.go-down {

background-image: url("./assets/images/down.png");

}

.main {

width: 610px;

.maze-header {

padding: 18px 0;

h2 {

display: inline-block;

}

}

.maze-body {

width: 100%;

height: 600px;

padding: 15px;

margin-bottom: 15px;

box-sizing: border-box;

border: 1px solid #cfcfcf;

display: flex;

// 让每一行按纵向排列

flex-direction: column;

.maze-row {

// 纵向平均分布

flex: 1;

// 将自己设置成弹性容器

display: flex;

.maze-step {

cursor: pointer;

// 水平平均分布

flex: 1;

// 用div的病

display: inline-block;

box-sizing: border-box;

background: {

size: 60%;

repeat: no-repeat;

position: center center;

}

// 所以小格子都设置左上边框

border: {

top: $step-border;

left: $step-border;

}

// 每行最后一个设置右边框

&:last-of-type {

border: {

right: $step-border;

}

}

}

// 第一排第一个

&:first-of-type {

.maze-step:first-of-type {

background-image: url("./assets/images/start.png");

}

}

// 最后一列每个格子都设置下边框

&:last-of-type {

.maze-step {

border-bottom: $step-border;

&:last-of-type {

background-image: url("./assets/images/end.png");

}

}

}

}

}

}

核心算法

/**

* 生成一个二维数组

*

* @param form 包含row,col的值

* @param random 是否随机

* @returns {[]}

*/

function initMaze(form, random = false) {

let maze = []

// 生成行

for (let i = 1; i <= form.row; i++) {

let row = []

for (let j = 1; j <= form.col; j++) {

// 设置障碍状态

// 第一个位置和最后一个位置不能为障碍

if ((i === 1 && i === j) || (i === form.row && j === form.col)) {

row.push(0)

} else {

row.push(random ? Math.random() * 1000 > 750 ? 1 : 0 : 0)

}

}

maze.push(row)

}

return maze

}

/**

* 根据计算出的路径在已知的地图上绘制出可视地图

*

* @param baseMaze 二维数组，包含了障碍的地图数据

* @param ruleWay 给出的行走路线

* @returns {{maze: *, ruleWay: *}}

*/

function redisplay(baseMaze, ruleWay = []) {

// 简单数据执行值拷贝

let maze = JSON.parse(JSON.stringify(baseMaze))

for (let index = 0; index < ruleWay.length; index++) {

// 下一步在路径中的位置

const nextIndex = index + 1

// 地图上X坐标

const row = ruleWay[index][0]

// 地图上Y坐标

const col = ruleWay[index][1]

// 判断最后一步还存在不

if (nextIndex !== ruleWay.length) {

// 向右和向左纵坐标是不会变化的

if (ruleWay[index][0] === ruleWay[nextIndex][0]) {

// 往右

if (ruleWay[index][1] + 1 === ruleWay[nextIndex][1]) {

maze[row][col] = 3

}

// 往左

else {

maze[row][col] = 5

}

} else {

// 往下

if (ruleWay[index][0] + 1 === ruleWay[nextIndex][0]) {

maze[row][col] = 4

}

// 往上

else {

maze[row][col] = 6

}

}

}

}

// 返回一个修改后的地图和路径

return {maze, ruleWay}

}

/**

*

* @param maze 地图

* @param route 递归通路

* @param routeCount 路径条数

* @param bestRoute 最好路径

* @returns {{bestRoute: *, routeCount: *}}

*/

function go(maze = [[]], route = [[]], routeCount = 0, bestRoute = []) {

let location = route[route.length - 1]

// 如果没有，直接返回

if (!location) {

return routeCount

}

const row = location[0]

const col = location[1]

// 向右，第一不越界，第二这个位置还可以向右，第三地图上向右这个位置可行

if (col + 1 !== maze[row].length && maze[row][col + 1] === 0) {

// 判断下一步是否是最后一步

if (row === maze.length - 1 && col + 1 === maze[row].length - 1) {

// 通路条数加1

routeCount++//.push(baseRoute.concat([[row, col + 1]]))

// 当前最短通路为空或者长度大于当前计算出的通路，即保存最优路径

if (bestRoute.length === 0 || bestRoute.length > route.length + 1) {

bestRoute = route.concat([[row, col + 1]])

}

}

// 不是最后一步

else {

// 封锁地图当前位置

maze[row][col] = 3

// 把下一步放入栈中，继续行走

route.push([row, col + 1])

let result = go(maze, route, routeCount, bestRoute)

routeCount = result.routeCount

bestRoute = result.bestRoute

}

}

// 向下

if (row + 1 !== maze.length && maze[row + 1][col] === 0) {

// 判断下一步是否是最后一步

if (row + 1 === maze.length - 1 && col === maze[row].length - 1) {

// 通路条数加1

routeCount++ //.push(baseRoute.concat([[row + 1, col]]))

// 当前最短通路为空或者长度大于当前计算出的通路，即保存最优路径

if (bestRoute.length === 0 || bestRoute.length > route.length + 1) {

bestRoute = route.concat([[row + 1, col]])

}

}

// 不是下一步

else {

// 封锁地图当前位置

maze[row][col] = 4

// 把下一步放入栈中，继续行走

route.push([row + 1, col])

let result = go(maze, route, routeCount, bestRoute)

routeCount = result.routeCount

bestRoute = result.bestRoute

}

}

// 向左

if (col - 1 !== -1 && maze[row][col - 1] === 0) {

// 封锁地图当前位置

maze[row][col] = 5

// 目前的迷宫，不可能向左走和向上走是出口

// 所以不需要判断下一步是不是出口

// 把下一步放入栈中，继续行走

route.push([row, col - 1])

let result = go(maze, route, routeCount, bestRoute)

routeCount = result.routeCount

bestRoute = result.bestRoute

}

// 向上

if (row - 1 !== -1 && maze[row - 1][col] === 0) {

// 封锁地图当前位置

maze[row][col] = 6

route.push([row - 1, col])

let result = go(maze, route, routeCount, bestRoute)

routeCount = result.routeCount

bestRoute = result.bestRoute

}

route.pop()

// 释放当前位置

maze[row][col] = 0

return {routeCount, bestRoute}

}

/**

* @param baseMaze

* @param baseRoute

* @returns {{bestRoute: *, routeCount: *}}

*/

function findAllRoutes(baseMaze, baseRoute = [[0, 0]]) {

// 该方法会改变迷宫和基础路线

// 需要进行深拷贝

// 简单数据执行值拷贝

let {maze} = redisplay(baseMaze, baseRoute)

return go(maze, baseRoute, 0, [])

}

export {

initMaze,

findAllRoutes,

redisplay

}

错误优化项请留言指出，谢谢！😁