前言
想起大学时老师让用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
}
错误优化项请留言指出,谢谢!😁