上节利用了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动画
如果觉得不错，给我点个赞吧，需要源码可以关注微信公众号“贝壳智能制造”获取，或者可以给我留言。
