广度优先搜索 ( BFS ) 寻找最短路径

4,538 阅读3分钟

分享一个简单的小游戏,利用 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 即可试玩哦(喜欢就点个赞吧,逃~ 😂