算法之广度优先搜索（BFS）及动画演示

效果预览：效果预览
源码下载：关注公众号【RMRF】，回复【algorithm1】可获取源码

在广度优先算法中，使用队列数据结构来保存已经访问过的节点，每次从队首取出一个节点进行访问，然后将该节点的所有未访问的相邻节点加入队尾，直到队列为空为止

一、vue

<template>
  <div class="index">
    <div class="header">
      <el-button @click="back">返回</el-button>
      <el-button type="primary" @click="createWalls">生成障碍物</el-button>
      <el-button type="success" @click="startFindPathByAnimation">开始【带动画】</el-button>
      <el-button type="warning" @click="startFindPath">开始【不带动画】</el-button>
      <el-button type="danger" @click="stopFindPath">停止</el-button>
    </div>
    <div id="canvas"></div>
  </div>
</template>

二、JavaScript

<script lang="ts" setup>
import Konva from 'konva';
import { onMounted } from 'vue';
import { ElMessage } from 'element-plus';
import { useRouter } from 'vue-router';
interface IRectangle {
  x: number
  y: number
  parent?: string
}
interface IPathMap {
  [k: string]: IRectangle
}
interface IGridMap {
  [k: string]: Konva.Node
}
// 画布
let stage: Konva.Stage | null = null
// 图层
const layer: Konva.Layer = new Konva.Layer()
// 主组
const mainGroup: Konva.Group = new Konva.Group()
// 矩形
const rect: Konva.Rect = new Konva.Rect()
// 倍数
const multiples = 10
// 定时器
let timer: NodeJS.Timer
// 图形 map
let gridMap: IGridMap = {}
// 需要查找的点队列
let openList: IRectangle[] = []
// 开始的点
let startPoint: IRectangle = {
  x: 0,
  y: 0
}
// 可以走的路径
let mapPath: IPathMap = {}
// 路径
let pathList: IRectangle[] = []
// 是否成功
let isSuccess = false

onMounted(() => {
  init()
})

// 初始化
const init = () => {
  const canvas = document.getElementById("canvas")
  if (!canvas) {
    return
  }
  const { clientWidth, clientHeight } = canvas
  stage = new Konva.Stage({
    container: 'canvas',
    width: clientWidth,
    height: clientHeight,
  })
  stage.add(layer)
  initBaseMap(clientWidth, clientHeight)
  createGrid()
  // 自适应
  window.onresize = () => {
    onresize()
  }
}
// 自适应
const onresize = () => {
  let canvas = document.getElementById('canvas');
  if (!canvas) {
    return
  }
  if (!stage) {
    return
  }
  const { clientWidth, clientHeight } = canvas
  stage.setAttrs({
    width: clientWidth,
    height: clientHeight,
  })
  const baseMap = stage.findOne("#baseMap")
  if (baseMap) {
    const baseMapAttrs = baseMap.getAttrs()
    const x = clientWidth / 2 - baseMapAttrs.width / 2
    const y = clientHeight / 2 - baseMapAttrs.height / 2
    mainGroup.setAttrs({ x, y })
  }
}
// 初始化底图区域
const initBaseMap = (clientWidth: number, clientHeight: number) => {
  const width = 600
  const height = 400
  const x = clientWidth / 2 - width / 2
  const y = clientHeight / 2 - height / 2
  const baseMap = rect.clone({
    id: "baseMap",
    x: 0,
    y: 0,
    width: width,
    height: height,
    fill: "#fff",
    stroke: 'black',
    strokeWidth: 1
  })
  mainGroup.setAttrs({ x, y })
  mainGroup.add(baseMap)
  layer.add(mainGroup)
}
// 初始化网格图形
const createGrid = () => {
  if (!stage) {
    return
  }
  const baseMap = stage.findOne("#baseMap")
  if (!baseMap) {
    return
  }
  const baseMapAttrs = baseMap.getAttrs()

  const xLen = baseMapAttrs.width / multiples
  const yLen = baseMapAttrs.height / multiples
  for (let y = 0; y < yLen; y++) {
    for (let x = 0; x < xLen; x++) {
      const grid = rect.clone({
        id: `${x}-${y}`,
        x: x * 10,
        y: y * 10,
        name: "grid",
        width: 9,
        height: 9,
        type: 1,
        fill: "#999",
      })
      mainGroup.add(grid)
    }
  }
}
// 设置禁区
const createWalls = () => {
  if (!stage) {
    return
  }
  const baseMap = stage.findOne("#baseMap")
  if (!baseMap) {
    return
  }
  clear()
  const baseMapAttrs = baseMap.getAttrs()
  let i = 0
  const xLen = baseMapAttrs.width / multiples - 1
  const yLen = baseMapAttrs.height / multiples - 1
  const rectangleList: IRectangle[] = []
  do {
    let x = Math.round(Math.random() * xLen)
    let y = Math.round(Math.random() * yLen)
    let newRectAngle: IRectangle = {
      x: x,
      y: y
    }
    let overlapping = false;
    for (const rect of rectangleList) {
      if (newRectAngle.x === rect.x && newRectAngle.y === rect.y) {
        overlapping = true
        break
      }
    }
    if (!overlapping) {
      i++
      rectangleList.push(newRectAngle)
    }

  } while (i < 500)
  rectangleList.forEach((item, key) => {
    const { x, y } = item
    const grid = mainGroup.findOne(`#${x}-${y}`)
    if (!grid) {
      return
    }
    if (key === 0) {
      setGridAttrs(grid, 3)
      startPoint = { x, y }
      openList.unshift({ x: x, y: y, parent: `0` })
    } else if (key === 1) {
      setGridAttrs(grid, 4)
    } else {
      setGridAttrs(grid, 2)
    }
  })
  setGridMap()
}
// 设置图形属性
const setGridAttrs = (grid: Konva.Node, type: number) => {
  let fill
  if (type === 2) {  // 禁区
    fill = "#000"
  } else if (type === 3) {// 开始
    fill = "#ff0000"
  } else if (type === 4) {// 结束 
    fill = "#00ff26"
  } else if (type === 5) {// 已访问
    fill = "#ffc800"
  } else if (type === 6) { // 路径
    fill = "#26deff"
  } else { // 默认
    fill = "#999"
  }
  grid.setAttrs({ type: type, fill: fill })
}
// 设置查找到的路径属性
const setPath = () => {
  pathList.forEach((item) => {
    const grid = gridMap[`${item.x}-${item.y}`]
    if (!grid) {
      return
    }
    setGridAttrs(grid, 6)
  })
}
// 设置图形map数据【优化】
const setGridMap = () => {
  const grids = mainGroup.find('.grid')
  grids.forEach((grid) => {
    const gridAttrs = grid.getAttrs()
    const id = `${gridAttrs.x / multiples}-${gridAttrs.y / multiples}`
    gridMap[id] = grid
  })
}
// 清空
const clear = () => {
  openList = []
  pathList = []
  mapPath = {}
  isSuccess = false
  stopFindPath()
  const grids = mainGroup.find('.grid')
  grids.forEach((shapes) => {
    setGridAttrs(shapes, 1)
  })
}
// 开始【带动画】
const startFindPathByAnimation = () => {
  if (isSuccess) {
    ElMessage.warning("请重新设置禁区")
    return
  }
  clearInterval(timer)
  timer = setInterval(() => {
    findPath()
  })
}
// 开始【不带动画】
const startFindPath = () => {
  if (isSuccess) {
    ElMessage.warning("请重新设置禁区")
    return
  }
  if (!stage) {
    return
  }
  const baseMap = stage.findOne("#baseMap")
  if (!baseMap) {
    return
  }
  const baseMapAttrs = baseMap.getAttrs()
  const maxX = baseMapAttrs.width / multiples
  const maxY = baseMapAttrs.height / multiples
  if (openList.length === 0) {
    return
  }
  pathList = []
  do {
    const itemPoint = openList.pop() as IRectangle
    const { x, y } = itemPoint
    if (x < 0 || x >= maxX) {
      continue
    }
    if (y < 0 || y >= maxY) {
      continue
    }
    const id = `${x}-${y}`
    const grid = gridMap[id]
    if (!grid) {
      continue
    }
    const gridAttrs = grid.getAttrs()
    if (gridAttrs.type === 2) {
      continue
    }
    if (gridAttrs.type === 4) {
      mapPath[id] = { x: x, y: y, parent: id }
      getPathPoint(mapPath, itemPoint.parent)
      isSuccess = true
      break
    }
    if (gridAttrs.type === 5) {
      continue
    }
    if (gridAttrs.type !== 3) {
      setGridAttrs(grid, 5)
    }
    mapPath[id] = { x: x, y: y, parent: itemPoint.parent }
    openList.unshift({ x: x + 1, y: y, parent: id })
    openList.unshift({ x: x - 1, y: y, parent: id })
    openList.unshift({ x: x, y: y + 1, parent: id })
    openList.unshift({ x: x, y: y - 1, parent: id })
  } while (openList.length > 0)
  setPath()
}
// 查找路径
const findPath = () => {
  if (!stage) {
    return
  }
  const baseMap = stage.findOne("#baseMap")
  if (!baseMap) {
    return
  }
  const baseMapAttrs = baseMap.getAttrs()
  const maxX = baseMapAttrs.width / multiples
  const maxY = baseMapAttrs.height / multiples

  for (let i = 0; i < openList.length; i++) {
    const itemPoint = openList.pop() as IRectangle
    const { x, y } = itemPoint
    if (x < 0 || x >= maxX) {
      return
    }
    if (y < 0 || y >= maxY) {
      return
    }
    const id = `${x}-${y}`
    const grid = gridMap[id]
    if (!grid) {
      return
    }
    const gridAttrs = grid.getAttrs()
    if (gridAttrs.type === 2) {
      return
    }
    if (gridAttrs.type === 4) {
      isSuccess = true
      mapPath[id] = { x: x, y: y, parent: id }
      getPathPoint(mapPath, itemPoint.parent)
      stopFindPath()
      setPath()
      return
    }
    if (gridAttrs.type === 5) {
      return
    }
    if (gridAttrs.type !== 3) {
      setGridAttrs(grid, 5)
    }
    mapPath[id] = { x: x, y: y, parent: itemPoint.parent }
    openList.unshift({ x: x + 1, y: y, parent: id })
    openList.unshift({ x: x - 1, y: y, parent: id })
    openList.unshift({ x: x, y: y + 1, parent: id })
    openList.unshift({ x: x, y: y - 1, parent: id })
  }
}
// 停止
const stopFindPath = () => {
  clearInterval(timer)
}
// 层层往上找对应的点
const getPathPoint = (pathMap: IPathMap, parent?: string) => {
  if (!parent) {
    return
  }
  let rectangle = pathMap[parent]
  if (parent === `${startPoint.x}-${startPoint.y}`) {
    return
  }
  if (rectangle) {
    pathList.push({ x: rectangle.x, y: rectangle.y })
    getPathPoint(pathMap, rectangle.parent)
  }
}
const router = useRouter()

const back = () => {
  router.push('/')
}
</script>

三、CSS样式

<style lang="scss" scoped>
.index {
  padding: 20px;

  .header {
    height: 50px;
    color: #ffc800;
  }

  #canvas {
    color: #26deff;
    background-color: #eee;
    border: 1px solid #666;
    height: calc(100vh - 92px);
  }
}
</style>