TOC
由于博客数据丢失，只剩下了代码。。。。。之前写的MD都没了。。
const gameConfig = {
maxLevel: 10// 最大搜索层级 2代表 只搜索经过两次转角能到达的点
}
// 简易队列系统 配合 DFS 广度有限搜索
class Quene {
constructor() {
this._quene = []
}
put(ele) {
this._quene.unshift(ele)
}
get() {
if (this._quene.length > 0) {
return this._quene.pop()
} else {
return null
}
}
}
// 搜索节点 每一个节点都包含了与起始节点直接的信息
class SearchNode {
/**
*
* @param {number} x 在图中的 x 位置
* @param {number} y 在图中的 y 位置
* @param {number} l 该节点的 level 度数 0 代表可以从起始节点直接到达 1代表需要一次转角
* @param {number} dis 从起始节点到该节点的最短距离
* @param {x:number,y:number} pre 该节点的上一个父节点(可以通过这个参数不断最终到距离起始节点的最短路径)
*/
constructor(x, y, l, dis, pre) {
this.x = x
this.y = y
this.l = l
this.dis = dis
this.pre = pre
}
}
/**
*
* @param {x:number,y:number} start 要查询的起始位置
* @param {x:number,y:number} end 要查询的结束位置
*
* @return {boolean} 检测两个点能否在相应 level限定 到达
*/
function checkCanbeRecivece(start, end) {
let quene = new Quene() // 队列放置所有下一次 currentLevel 循环
let allNode = [] // 最终节点仓库 放在里面代表 level 已经确定 (但是 dis 距离还是有可能会更新)
let currentLevel = 0 // 当前的步进
// 初始节点 也就是起始节点 直接放入两个列表中
let initNode = new SearchNode(start.x, start.y, currentLevel, 0)
quene.put(initNode)
allNode.push(initNode)
// 从宏观上来最多只走规定的最大步数
while (currentLevel <= gameConfig.maxLevel) {
// 循环 L1 (到达层级)
// 遍历队列 对队列中的所有节点进行射线标记
let curNode = quene.get()
let temps = [] // 新发现的节点需要放入到临时数组中 循环结束后再放置到队列中(避免一个步进循环直接便利所有节点)
while (curNode) {
// 循环 L2 (所有队列中需要进一步射线探测的新节点)
/**
*
* @param {SearchNode} newNode 通过发射发现的新节点
* @param {boolean} isOhterNode 是否属于一个实体节点 如果实体就没必要放入到
*
*/
const next = (newNode, isOhterNode) => {
if (isOhterNode) {
allNode.push(newNode)
} else {
temps.push(newNode)
}
}
/**
* @description 检测该节点是否有更近的方式到达
*
* @param {number} x 该节点的 X
* @param {number} y 该节点的 Y
* @param {number} dis 该节点到起始节点的距离
* @param {SearchNode} pre 该节点的前置节点
*
* @return {boolean} 该节点是否属于第一次发现的新节点
*/
const updateDistanceAndCheckIsNew = (x, y, dis, pre) => {
let aNodes = allNode.concat(temps)
let fIndex = aNodes.findIndex(v => v.x === x && v.y === y)
let node = allNode[fIndex]
// 发现有更短的路径 重新标记下距离和前置节点
if (node && node.dis > dis) {
node.dis = dis
node.pre = pre
}
return fIndex <= -1
}
/* 进行射线发射 GOGOGO */
// UP 沿着 Y 轴向上发射
rayTagHelper(
0,
-1,
curNode,
currentLevel,
updateDistanceAndCheckIsNew,
next
)
// DOWN 沿着 Y 轴向下发射
rayTagHelper(
0,
1,
curNode,
currentLevel,
updateDistanceAndCheckIsNew,
next
)
// LEFT 沿着 X 轴向左发射
rayTagHelper(
-1,
0,
curNode,
currentLevel,
updateDistanceAndCheckIsNew,
next
)
// RIGHT 沿着 X 轴向右发射
rayTagHelper(
1,
0,
curNode,
currentLevel,
updateDistanceAndCheckIsNew,
next
)
// 取出下一个需要进行发射的节点
curNode = quene.get()
}
// 把所有的临时节点都加入到队列以及 allNode 中
temps.forEach(v => {
quene.put(v)
allNode.push(v)
})
// 步进自增
currentLevel++
}
/*
判断该节点是否能到达，只要检查 allNode 里面是否包含结尾节点就可以
*/
if (
allNode.findIndex(v => {
if (v.x === end.x && v.y === end.y) {
console.log(v)
console.log(`可以到达: level - ${v.l} -- dis - ${v.dis}`)
console.log(allNode)
}
return v.x === end.x && v.y === end.y
}) > -1
) {
} else {
console.log('无法到达')
}
}
/**
* @description 往一个方向上持续探测节点 直到碰到阻挡
*
* @param {number} xOffset 每次单次发射 X 轴的持续偏移
* @param {number} yOffset 每次单次发射 Y 轴的持续偏移
* @param {SearchNode} startNode 发射起始节点
* @param {number} currentLevel 当前的步进
* @param {(x, y, dis, pre) -> boolean} updateDistanceAndCheckIsNew 更新节点最短记录 并检查是否属于新发现的节点
* @param {*} callBack 如果属于新节点 触发该回调 加入到队列中
*/
function rayTagHelper(
xOffset,
yOffset,
startNode,
currentLevel,
updateDistanceAndCheckIsNew,
callBack
) {
let { x, y, dis } = startNode
let pre = null
let cur = null
let isEntityNode = false
do {
pre = {
x,
y
}
// 开始发射 定位为特定方向上的第一个节点
x += xOffset
y += yOffset
dis++
// 避免 JS 错误 查到一个不存在的位置
if (gameGird[x] === undefined || gameGird[x][y] === undefined) return null
cur = gameGird[x][y]
// 检测当前节点是否属于实体节点
isEntityNode = cur !== 0
// 只有新节点才触发回调 加入到temps之中 顺便更新一下最短路径
if (updateDistanceAndCheckIsNew(x, y, dis, pre)) {
callBack(new SearchNode(x, y, currentLevel, dis, pre), isEntityNode)
}
// 当没有触碰到边界和实体节点时 继续发射
} while (cur !== undefined && !isEntityNode)
return null
}
// 层级为0的情况
// let gameGird = [
// [0, 0, 0, 0, 0, 0],
// [0, 1, 0, 0, 0, 0],
// [0, 0, 0, 0, 0, 0],
// [0, 1, 0, 0, 0, 0],
// [0, 0, 0, 0, 0, 0],
// [0, 0, 0, 0, 0, 0]
// ]
// checkCanbeRecivece(
// {
// y: 1,
// x: 1
// },
// {
// x: 3,
// y: 1
// }
// )
// 查找层级为1的情况
let gameGird = [
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]
]
// checkCanbeRecivece(
// {
// y: 1,
// x: 1
// },
// {
// x: 2,
// y: 2
// }
// )
// 查找层级为2的情况
// let gameGird = [
// [0, 0, 0, 0, 0, 0],
// [0, 1, 2, 0, 1, 0],
// [0, 0, 0, 0, 0, 0],
// [0, 0, 0, 0, 0, 0],
// [0, 0, 0, 0, 0, 0],
// [0, 0, 0, 0, 0, 0]
// ]
// checkCanbeRecivece(
// {
// y: 1,
// x: 1
// },
// {
// x: 1,
// y: 4
// }
// )
// 无法到达的情况 maxLevel = 2 情况下
// let gameGird = [
// [0, 0, 0, 0, 2, 0],
// [0, 1, 2, 0, 1, 0],
// [0, 0, 2, 0, 2, 0],
// [0, 0, 2, 0, 2, 0],
// [0, 0, 2, 0, 0, 0],
// [0, 0, 2, 0, 0, 0]
// ]
// checkCanbeRecivece(
// {
// y: 1,
// x: 1
// },
// {
// x: 1,
// y: 4
// }
// )
// 无法到达的情况 没路了 直接死路的情况
// let gameGird = [
// [0, 0, 2, 0, 2, 0],
// [0, 1, 2, 0, 1, 0],
// [0, 0, 2, 0, 2, 0],
// [0, 0, 2, 0, 2, 0],
// [0, 0, 2, 0, 0, 0],
// [0, 0, 2, 0, 0, 0]
// ]
// checkCanbeRecivece(
// {
// y: 1,
// x: 1
// },
// {
// x: 1,
// y: 4
// }
// )
// 查找层级为2的情况 测试下最短路径
// let gameGird = [
// [0, 0, 0, 0, 0, 0],
// [0, 0, 1, 0, 0, 0],
// [0, 1, 1, 1, 0, 0],
// [0, 0, 1, 0, 0, 0],
// [0, 0, 1, 0, 0, 0],
// [0, 0, 0, 0, 0, 0]
// ]
// checkCanbeRecivece(
// {
// y: 1,
// x: 2
// },
// {
// x: 2,
// y: 3
// }
// )