分享一个简单的小游戏,利用 BFS 寻找距离出口的最短路径。
游戏规则如下:
玩家点击空白块截住硬币,双方一次一步, 若硬币到达边界处则逃脱, 成功围住硬币则算赢。
硬币如何找到最近出口呢,这里就用到了 BFS 搜索。
首先我们来看下 BFS ( 广度优先搜索 ) 的描述:
BFS 的思想是从一个顶点 V0 开始,辐射状地优先遍历其周围较广的区域。类似于树的按层次遍历的过程
这种搜索很适合我们游戏里硬币的寻找出口。
在咱们游戏中,每个点一般有六个相邻方向:
其中,寻找的规则大致如下:
1. 从起点开始,查看周围相邻点是否存在出口;
2. 若不存在,标记每个点为已访问,接着从每个点的相邻方向继续寻找下去;
3. 直至找到一个出口或遍历完所有相邻点为止。
搜索的过程如图所示,从起点向外扩散:
算法代码:
/**
* BFS 求离出口最短路径
*
* 1. 初始化一个队列,添加起点
* 2. 遍历队列中每一个元素,与它周围 6 个相邻块
* * 若没遍历过,查找周围是否有出口
* * 若无出口,添加进队列循环查找
* 3. 循环停止条件
* * 寻找到出口,即为最短路径,返回该出口
* * 所有相邻点均遍历,无出口,玩家胜利 ✌️
*/
function getNearestSolver (point) {
const records = {}
// 将当前位置作为队列第一个元素
let arr = [point]
let des = null
// 若队列还有元素,则继续查找
while (arr.length) {
// 取出队首元素
const V = arr.shift()
// 获取队首元素的相邻节点并过滤障碍物和已访问过的节点
const neighbours = getNeighbours(V).filter(p => typeof status[p] !== 'undefined' && !status[p].isWall && !status[p].hasVisited)
// 将节点添加进 records 对象中并指明来源节点,同时状态设为已访问
neighbours.forEach(p => {
records[p] = { source: V }
status[p].hasVisited = true
})
// 查看相邻节点中是否有边界节点,即出口
const hasEdge = neighbours.find(p => status[p].isEdge)
arr = arr.concat(neighbours)
if (hasEdge) {
des = hasEdge
break
}
}
// 遍历结束,重置元素访问状态
for (const s of Object.values(status)) {
s.hasVisited = false
}
// 返回查找的终点和路径记录对象
return { des, records }
}
根据终点倒推第一步的坐标:
function getSolution (point) {
const [x, y] = point
const { des, records } = getNearestSolver(`${x},${y}`)
const sixDir = getNeighbours(`${x},${y}`)
const routes = []
let nextPos = des
// 反向寻找第一个坐标
while (nextPos && !sixDir.includes(nextPos)) {
routes.push(nextPos)
nextPos = records[nextPos].source
}
return { nextPos, routes: routes.concat(nextPos) }
}
用于确定给定点周围六个相邻块的位置:
function getNeighbours (point) {
const split = point.split(',')
const x = +split[0]
const y = +split[1]
// 奇偶行共同的相邻坐标
const commonDir = [`${x},${y+1}`, `${x+1},${y}`, `${x},${y-1}`, `${x-1},${y}`]
// 因奇偶行偏移量导致不同的相邻坐标
const differentDir = y % 2 ? [`${x+1},${y+1}`, , `${x+1},${y-1}`] : [`${x-1},${y+1}`, `${x-1},${y-1}`]
return commonDir.concat(differentDir)
}
至此,JS 部分就结束了,当我们随意点击棋盘上某一空白处时,该位置会变成障碍物,同时硬币会将自己位置传进 getSolution(point)
方法以确定下一步行走的方向。
来看下效果吧:
最后,小小总结下 广度优先搜索:
1. 查找与当前顶点相邻的未访问顶点,将其添加到队列并标为已访问;
2. 从队列中取出下一个顶点,继续(1)的步骤,查找相邻顶点是否存在目标顶点;
3. 循环往复,直至找到目标顶点或队列为空。
用一段通用代码表示如下:
function BFS(s) {
const queue = []
s.visited = true
queue.push(s)
while (queue.length) {
const V = queue.shift()
for each(const w in this.neighbours(V)) {
if (!w.visited) {
w.source = V
w.visited = true
queue.push(w)
if (w.isEdge) break
}
}
}
}
代码仓库在 Catch-the-coin,下载后在浏览器打开 index.html
即可试玩哦(喜欢就点个赞吧,逃~ 😂