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