目录
一、概念
二、现实案例
三、实现迷宫游戏寻找路径
四、结果
一、概念
图搜索算法，设置一个顶点，对相邻节点进行搜索，一旦有可搜索点且未被搜索过，则以同样方式搜索该节点的相邻节点。直到节点无新相邻节点。则回到上一节点搜索其他未搜索过的节点。直到回到起点且无可搜索的节点。
二、现实案例
迷宫
三、实现迷宫游戏寻找路径
js
/*** 迷宫二维数组 1为墙壁* @type {Array}*/
let input = [[0, 1, 0, 0, 0, 1, 0, 0, 0],[0, 0, 1, 0, 1, 0, 0, 1, 0],[0, 0, 0, 0, 0, 1, 0, 1, 0],[1, 1, 0, 0, 1, 1, 0, 1, 0],[0, 0, 1, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 1, 0, 1, 0],[0, 0, 1, 0, 0, 1, 0, 1, 0],]
let rM = input.length - 1;
let cM = input[0].length - 1;
console.log("maze:")
consoleLogFoundPath([])
let startPoint = [0, 0],endPoint = [rM, cM];
let pathArr = [];
let gonePointArr = [];
pathArr.push(startPoint);
gonePointArr.push(startPoint);
let finished = false;
let found = false;
let cP = [0, 0];
do {/*** 上下左右四点* @type {Array}*/let pAround = [[cP[0] - 1, cP[1]],[cP[0], cP[1] + 1],[cP[0] + 1, cP[1]],[cP[0], cP[1] - 1],]let go = false;for (let testP of pAround) {let checkCanGo_ = checkCanGo(testP);let checkGone_ = checkGone(testP);if (checkCanGo(testP) && !checkGone(testP)) {//可以前进gonePointArr.push(testP);pathArr.push(clone(testP));cP = testP;go = true;break;}}if (!go) {if (checkCantFind(cP)) {console.log('cant find end');finished = true;} else if (checkEnd(cP)) {console.log('found end !');found = true;finished = true;} else { //回退pathArr.pop();cP = pathArr[pathArr.length - 1];}}
} while (!finished)
window.pta = JSON.stringify(pathArr)
if (found) { consoleLogFoundPath(pathArr) }
/*** 打印路径*/
function consoleLogFoundPath(pathArr) {for (let item of pathArr) {input[item[0]][item[1]] = "*";}for (let r = 0; r <= rM; r++) {let rConsole = '';for (let c = 0; c <= cM; c++) {rConsole += " " + input[r][c];}console.log(rConsole);}
}
//是否不能找到终点（回到起点）
function checkCantFind(pos) {if (pos[0] === 0 && pos[1] === 0) {if ((!checkCanGo([1, 0]) || checkGone([1, 0]) && (!checkCanGo([0, 1]) || checkGone([0, 1])))) return true;}
}
//是否已经寻找过
function checkGone(pos) {if (!pos) return;for (let item of gonePointArr) {if (item.toString() == pos.toString()) return true;}
}
//是否终点
function checkEnd(pos) {return pos[0] == rM && pos[1] == cM;
}
//是否可行
function checkCanGo(pos) {if (input[pos[0]] == undefined || input[pos[0]][pos[1]] == undefined) return false;return input[pos[0]][pos[1]] == 0;
}
//克隆地点
function clone(pos) {return [pos[0], pos[1]];
}
四、结果
暂无