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

简介: 这篇文章详细介绍了如何在Three.js中完整实现基于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])
        }
      }
    },

演示地址:贝壳智能制造

效果如下:这里不支持上传视频,我发个效果图代替,如果想看动态效果可以私我,我发给你视频
WechatIMG132.jpg
基于A*算法的Threejs动画

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

相关文章
|
3月前
|
数据采集 机器学习/深度学习 算法
|
1月前
|
存储 分布式计算 算法
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
58 0
|
3月前
|
搜索推荐 前端开发 数据可视化
【优秀python web毕设案例】基于协同过滤算法的酒店推荐系统,django框架+bootstrap前端+echarts可视化,有后台有爬虫
本文介绍了一个基于Django框架、协同过滤算法、ECharts数据可视化以及Bootstrap前端技术的酒店推荐系统,该系统通过用户行为分析和推荐算法优化,提供个性化的酒店推荐和直观的数据展示,以提升用户体验。
147 1
|
19天前
|
存储 算法 搜索推荐
这些算法在实际应用中有哪些具体案例呢
【10月更文挑战第19天】这些算法在实际应用中有哪些具体案例呢
25 1
|
1月前
|
存储 算法 机器人
Threejs路径规划_基于A*算法案例V2
这篇文章详细介绍了如何在Three.js中使用A*算法进行高效的路径规划,并通过三维物理电路的实例演示了路径计算和优化的过程。
58 0
|
3月前
|
机器学习/深度学习 人工智能 算法
【人工智能】传统语音识别算法概述,应用场景,项目实践及案例分析,附带代码示例
传统语音识别算法是将语音信号转化为文本形式的技术,它主要基于模式识别理论和数学统计学方法。以下是传统语音识别算法的基本概述
71 2
|
3月前
|
机器学习/深度学习 算法 数据可视化
决策树算法介绍:原理与案例实现
决策树算法介绍:原理与案例实现
|
3月前
|
自然语言处理 算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
56 0
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
|
3月前
|
算法 定位技术
路径规划算法 - 求解最短路径 - A*(A-Star)算法
路径规划算法 - 求解最短路径 - A*(A-Star)算法
67 0
|
3月前
|
算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
64 0