寻路算法小demo
寻路算法有两种，一种是dfs 深度优先算法，一种是
dfs 深度优先算法
深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。
否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。
bfs 广度优先搜索
广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作。
数据结构上的运用
DFS用递归的形式，用到了栈结构，先进后出。
BFS选取状态用队列的形式，先进先出。
<html>
<head>
<title>寻路算法</title>
</head>
<body>
<div class="body">
<div class="body-content1">
<div class="dfs-title">寻路算法</div>
<div id="dfs-content" class="dfs-cell"></div>
<div id="btn-list">
<div id="btn-start-dfs" class="btn-start">dfs</div>
<div id="btn-start-bfs" class="btn-start">bfs</div>
<div id="btn-reset">重置</div>
</div>
</div>
<div class="body-content2">
<div class="dfs-title">.</div>
<div class="start-point point">
开始坐标：
<input id="start-point-x" type="number" placeholder="行" />
<input id="start-point-y" type="number" placeholder="列" />
</div>
<div class="target-point point">
终点坐标：
<input id="target-point-x" type="number" placeholder="行" />
<input id="target-point-y" type="number" placeholder="列" />
</div>
</div>
</div>
</body>
<script>
let count = 0; //步数计数
//迷宫地图
let map = [
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 1],
[0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 1],
[0, 0, 1, 1, 1, 0, 0, 0],
];
let cellSize = 20; //px单元格大小
let startX = 0, //开始坐标
startY = 0;
let targetX = 15, //结束坐标
targetY = 7;
let canFind = false;
//遍历方向
let dx = [0, 1, 0, -1],
dy = [1, 0, -1, 0];
let flag = new Array(map.length); //dfs标记走过的路径
for (let i = 0; i < flag.length; i++) {
flag[i] = new Array(map[i].length).fill(false);
}
//能否到达
let findFlag = false;
let step = new Array(map.length); //bfs标记走过的路径
for (let i = 0; i < step.length; i++) {
step[i] = new Array(map[i].length).fill(Infinity);
}
//单元格点击事件
function cellClick(e) {
let wFlag = 0;
let classList = [...e.classList];
if (classList.includes("now-in")) return;
if (classList.includes("wall")) {
e.classList.remove("wall");
e.classList.add("space");
} else if (classList.includes("space")) {
e.classList.remove("space");
e.classList.add("wall");
wFlag = 1;
}
let id = e.id.split("-");
let x = id[2],
y = id[3];
map[x][y] = wFlag;
// console.log(map[x][y], x, y);
}
//初始化页面
function init() {
initPage();
initData();
}
function initData() {
const startPointX = document.getElementById("start-point-x");
const startPointY = document.getElementById("start-point-y");
const targetPointX = document.getElementById("target-point-x");
const targetPointY = document.getElementById("target-point-y");
startPointX.value = startX;
startPointY.value = startY;
targetPointX.value = targetX;
targetPointY.value = targetY;
startPointX.addEventListener("change", (e) => {
if (
e.target.value < 0 ||
e.target.value >= map.length ||
map[e.target.value][startY] == 1
) {
alert("非法坐标，请重新输入");
startPointX.value = startX;
return;
}
startX = parseInt(e.target.value);
initPage();
});
startPointY.addEventListener("change", (e) => {
if (
e.target.value < 0 ||
e.target.value >= map[0].length ||
map[startX][e.target.value] == 1
) {
alert("非法坐标，请重新输入");
startPointY.value = startY;
return;
}
startY = parseInt(e.target.value);
initPage();
});
targetPointX.addEventListener("change", (e) => {
if (
e.target.value < 0 ||
e.target.value >= map.length ||
map[e.target.value][targetY] == 1
) {
alert("非法坐标，请重新输入");
targetPointX.value = targetX;
return;
}
targetX = parseInt(e.target.value);
initPage();
});
targetPointY.addEventListener("change", (e) => {
if (
e.target.value < 0 ||
e.target.value >= map[0].length ||
map[targetX][e.target.value] == 1
) {
alert("非法坐标，请重新输入");
targetPointY.value = targetY;
return;
}
targetY = parseInt(e.target.value);
initPage();
});
}
function initPage() {
let innerHtml = ``;
count = 0;
findFlag = false;
for (let i = 0; i < map.length; i++) {
for (let j = 0; j < map[i].length; j++) {
flag[i][j] = false;
innerHtml += `<div id="${"dfs-id-" + i + "-" + j}" class="${
map[i][j] == 0 ? "space" : "wall"
} cell" style="width:${cellSize}px;height:${cellSize}px;" click="cellClick"></div>`;
}
}
let dfsContent = document.getElementById("dfs-content");
dfsContent.style.width = map[0].length * (cellSize + 2) + "px";
dfsContent.innerHTML = innerHtml;
let startCell = document.getElementById(
"dfs-id-" + startX + "-" + startY
);
startCell.classList.add("now-in");
let targetCell = document.getElementById(
"dfs-id-" + targetX + "-" + targetY
);
targetCell.classList.add("target-in");
let cell = document.getElementsByClassName("cell");
for (let i = 0; i < cell.length; i++) {
cell[i].addEventListener("click", () => {
cellClick(cell[i]);
});
}
}
function dfs(x, y) {
const dx = [1, 0, -1, 0],
dy = [0, 1, 0, -1];
if (x < 0 || y < 0 || x >= map.length || y >= map[0].length) return;
if (map[x][y] == 1 || flag[x][y] || findFlag) return;
let startCell = document.getElementById("dfs-id-" + x + "-" + y);
startCell.classList.add("now-in");
if (x == targetX && y == targetY) {
findFlag = true;
startCell.innerHTML = `<div style="font-size:small;text-align: center;">${count}</div>`;
canFind = true;
return;
}
for (let i = 0; i < 4 && !findFlag; i++) {
flag[x][y] = true;
startCell.innerHTML = `<div style="font-size:small;text-align: center;">${count}</div>`;
count++;
startCell.classList.add("pass");
startCell.classList.remove("now-in");
if (!findFlag) dfs(x + dx[i], y + dy[i]);
if (!findFlag) flag[x][y] = false;
if (!findFlag) startCell.innerHTML = "";
if (!findFlag) count--;
if (!findFlag) startCell.classList.remove("pass");
}
}
function bfs() {
let quene = [
[startX, startY]
];
step[startX][startY] = 0;
// console.log("开始bfs");
let res = [];
flag[startX][startY] = true;
while (quene.length) {
let p = quene.shift();
res.push(p);
let x = p[0],
y = p[1];
if (x == targetX && y == targetY) break;
let f = false;
for (let i = 0; i < 4; i++) {
let nx = x + dx[i],
ny = y + dy[i];
if (nx < 0 || nx >= map.length || ny >= map[0].length || ny < 0) {
continue;
}
if (map[nx][ny] == 1 || flag[nx][ny] == true) {
continue;
}
flag[nx][ny] = true;
step[nx][ny] = step[x][y] + 1;
quene.push([nx, ny]);
if (nx == targetX && ny == targetY) {
f = true;
canFind = true;
break;
}
}
if (f) break;
}
if (canFind) bfsDrawRoad();
}
//绘制路线
function bfsDrawRoad() {
let road = [
[targetX, targetY]
];
while (road[0][0] != startX || road[0][1] != startY) {
let x = road[0][0],
y = road[0][1];
for (let i = 0; i < 4; i++) {
let nx = x + dx[i],
ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= step.length || ny >= step[0].length)
continue;
if (step[x][y] == step[nx][ny] + 1) {
road.unshift([nx, ny]);
break;
}
}
}
for (let i = 0; i < road.length; i++) {
let startCell = document.getElementById(
"dfs-id-" + road[i][0] + "-" + road[i][1]
);
if (i != road.length - 1) {
startCell.classList.add("pass");
} else {
startCell.classList.add("now-in");
}
startCell.innerHTML = `<div style="font-size:small;text-align: center;">${i}</div>`;
}
}
//页面初始化
init();
//开始dfs
let startBtnDfs = document.getElementById("btn-start-dfs");
startBtnDfs.addEventListener("click", () => {
canFind = false;
init();
dfs(startX, startY);
// console.log(canFind);
if (!canFind) alert("无法达到");
});
//开始bfs
let startBtnBfs = document.getElementById("btn-start-bfs");
startBtnBfs.addEventListener("click", () => {
canFind = false;
init();
bfs();
// console.log(canFind);
if (!canFind) alert("无法达到");
});
//重置页面
let resetBtn = document.getElementById("btn-reset");
resetBtn.addEventListener("click", () => {
init();
});
</script>
<style>
.body {
display: flex;
margin: auto;
}
.body-content1 {
flex: 1;
}
.body-content2 {
flex: 1;
}
.point {
margin-top: 1rem;
}
.dfs-cell {
display: flex;
flex-wrap: wrap;
margin: auto;
}
.dfs-cell>.cell {
border: 1px solid gray;
cursor: pointer;
}
.dfs-cell>.wall {
background-color: black;
}
.now-in {
background-color: yellow;
}
.target-in {
background-color: rgb(245, 162, 9);
}
.pass {
background-color: yellowgreen;
}
.dfs-title {
text-align: center;
margin: 2rem;
}
#btn-list {
display: flex;
justify-content: space-between;
width: 20rem;
margin: auto;
}
.btn-start {
padding: 1rem;
margin: auto;
margin-top: 2rem;
text-align: center;
background-color: violet;
width: 2rem;
cursor: pointer;
}
#btn-reset {
padding: 1rem;
margin: auto;
margin-top: 2rem;
text-align: center;
background-color: violet;
width: 2rem;
cursor: pointer;
}
</style>
</html>
