Threejs路径规划_基于A*算法案例完整版

上节利用了A*实现了基础的路径规划，这节把整个功能完善好，A*算法一方面是基于当前点找到可以到达的点，计算从出发点到此点，以及此点到目的地的总成本，比较出最小的那个，再用最小成本的点继续找到它可以到达的点，直到目的地，同时会创建两个集合，一个叫open集合，一个叫close集合，open是用于存放到达过且没有继续探索的点，close集合是存放到达过且继续探索的点，简单的说A*算法会一边探索的同时会把新探索到的点放到open集合中，一边把探索过的点加入到close集合中。这样可以防止重复探索之前的点，如果探测到的点包含目标点。则探索结束。下面我们用图例的方式演示整个过程

如图在网格中有出发点和目的地，分别在网格的两侧，如果要从出发点到达目的地，A*算法会先获取到Start可以到达的四个点，将四个点放到open集合中，然后选出四个点中到达End成本做小的，

此时可以明显的看出右侧的格子到End点的成本最小，这里的成本包括已经花费的成本和到End点预估的成本，

得到了成本最小的点后，再继续基于这个点继续探索周围的点，同时会将探索过的Start点放到close集合中，经过探索，仍然是右侧点成本最低，然后将探索到的点放到open中，探索过的点放到close中，继续探索，依此类推，直到探索到End点。

然后我们按照上述方式将方法改造如下：

buildPath() {
      // 选择的起始点和目标点
      if (this.beginPoint.x > 30 || this.beginPoint.y > 30 || this.endPoint.x > 30 || this.endPoint.y > 30) {
        this.$message.error('超出地图范围')
        return
      }
      const begin = (parseInt(this.beginPoint.x) - 1) + '.' + (this.beginPoint.y - 1)
      const end = (parseInt(this.endPoint.x) - 1) + '.' + (this.endPoint.y - 1)
      this.removeOnce() // 移除上一次规划的内容
      this.drawPoint(begin) // 将出发点绘制到地图上
      this.openPoint.push({ point: begin, distance: 0 })
      let current = { point: begin, path: [begin], distance: 0 }
      while (current.point !== end) {
        const result = this.recursion(current, end)
        current = result
      }
      this.pathRoad = current.path.split('_')
      for (let i = 0; i < this.pathRoad.length; i++) {
        this.drawPoint(this.pathRoad[i])
      }
    },
    calcDistance(start, end) {
      const beginX = start.split('.')[0]
      const beginY = start.split('.')[1]
      const endX = end.split('.')[0]
      const endY = end.split('.')[1]
      // 获取到达的点与目的地的曼哈顿距离
      const distance = Math.abs(parseInt(endX - beginX)) + Math.abs(parseInt(endY - beginY))
      return distance
    },
    recursion(current, end) {
      const tempPoints = [] // 当前点可以连接的路线
      // 获取到这个点能到达的所有点的路线
      for (let i = 0; i < this.roadList.length; i++) {
        if (this.roadList[i].begin === current.point) {
          tempPoints.push(this.roadList[i].end)
        }
      }

      for (let i = 0; i < tempPoints.length; i++) {
        const hadSpend = parseInt(current.distance) + 1 // 已经花费的成本，也就是起点到当前点的成本（是上一个点+1得到）
        const remainingEstimated = this.calcDistance(tempPoints[i], end) // 下一个点到目标点的成本，也就是剩余预估成本
        const totalCost = parseInt(hadSpend) + parseInt(remainingEstimated)
        const path = current.path + '_' + tempPoints[i]

        // 如果点已经在close中了就不加入openList中
        let havaClose = false
        for (let j = 0; j < this.closePoint.length; j++) {
          if (this.closePoint[j].point === tempPoints[i]) {
            havaClose = true
          }
        }
        if (!havaClose) {
          this.openPoint.push({ point: tempPoints[i], haveCost: hadSpend, path: path, remainingCost: remainingEstimated, distance: totalCost })
        }
      }
      // 从开放点中去掉已经走过的点，并加入到close点集合中
      for (let i = 0; i < this.openPoint.length; i++) {
        if (this.openPoint[i].point === current.point) {
          this.openPoint.splice(i, 1)
          this.closePoint.push(current)
          i--
        }
      }
      // 比较openList中哪个distance的成本最小就用此继续递归
      let result = { point: this.openPoint[0].point, distance: this.openPoint[0].distance }
      // 获取到目的地最近的点并返回
      for (let i = 0; i < this.openPoint.length; i++) {
        if (this.openPoint[i].distance <= result.distance) {
          result = { point: this.openPoint[i].point, haveCost: this.openPoint[i].haveCost, path: this.openPoint[i].path, distance: this.openPoint[i].distance }
        }
      }
      const data = { point: result.point, path: result.path, distance: result.haveCost }
      return data
    },

效果如下：

此时输入出发点和目标点后会直接算出路径，并把路径绘制在网格上，但是我们是基于threejs的，可以再增加点动画效果，在计算出路径后，通过threejs的动画每隔一定的时间绘制出一个点，就时间了动画效果，代码如下：

      roadIndex: 0,
      pathRoad: [],
      times: 0 
initAnimate() {
      requestAnimationFrame(this.initAnimate)
      this.renderer.render(this.scene, this.camera)
      if (this.pathRoad.length > 0 && this.roadIndex < this.pathRoad.length - 1) {
        this.times += 0.1
        if (this.times > 1) {
          this.times = 0
          this.roadIndex += 1
          this.drawPoint(this.pathRoad[this.roadIndex])
        }
      }
    },

演示地址：贝壳智能制造

效果如下：这里不支持上传视频，我发个效果图代替，如果想看动态效果可以私我，我发给你视频

基于A*算法的Threejs动画

如果觉得不错，给我点个赞吧，需要源码可以关注微信公众号“贝壳智能制造”获取，或者可以给我留言。