TOC
非常酷的一个启发式搜索算法，整体类似于dij最短路径算法，只不过加入了预估距离的概念，当然由于博客数据丢失，之前的博客内容没了，不过还好代码还在，大家凑活看看吧。
// 使用了 p5.js
// 基本配置
const GameConfig = {
col: 25,
row: 25,
width: 600,
height: 600
}
// 主矩阵
let gameGrid
// 所有还未确定最短路径的集合
let openSet = []
// 所有已经确定最短路径的集合
let closedSet = []
// 当前的路径集合
let pathSet = []
// 起点
let start = null
// 终点
let end = null
// 启发式距离预估函数
// 常用的有 曼哈顿距离 欧几里得距离
// 这里采用欧几里得距离
function heuristic(a, b) {
return dist(a.x, a.y, b.x, b.y)
// return Math.abs(a.x - b.x) + Math.abs(a.y - b.y)
}
// 矩阵节点类
class Spot {
constructor(x, y, width, height) {
this.x = x
this.y = y
// 距离起点的实际距离
this.g = 0
// 距离终点的预估距离
this.h = 0
// 综合距离 通过 g + h
this.f = 0
this.width = width
this.height = height
this.prev = null
// 所有邻接边
this.neighBors = []
this.isWall = Math.random() < 0.2 ? true : false
}
draw(_color) {
if (this.isWall) {
_color = color(0)
}
fill(_color)
noStroke(0)
rect(
this.x * this.width,
this.y * this.height,
this.width - 1,
this.height - 1
)
}
// 记录所有邻接边
addNeighbors(grid, col, row) {
const { x, y } = this
// RIGHT
if (this.x < col - 1) {
this.neighBors.push(grid[x + 1][y])
}
// LEFT
if (this.x > 0) {
this.neighBors.push(grid[x - 1][y])
}
// TOP
if (this.y < row - 1) {
this.neighBors.push(grid[x][y + 1])
}
// BOT
if (this.y > 0) {
this.neighBors.push(grid[x][y - 1])
}
// LEFT TOP
if (this.x > 0 && this.y > 0) {
this.neighBors.push(grid[x - 1][y - 1])
}
// RIGHT BOT
if (this.x < col - 1 && this.y < row - 1) {
this.neighBors.push(grid[x + 1][y + 1])
}
}
}
class GameGrid {
constructor(col, row, width, height) {
this._grid = []
this.col = col
this.row = row
let spWidth = width / col
let spHeight = height / row
for (let i = 0; i < col; i++) {
this._grid[i] = []
for (let j = 0; j < row; j++) {
this._grid[i][j] = new Spot(i, j, spWidth, spHeight)
}
}
this.forEach(v => {
v.addNeighbors(this._grid, this.col, this.row)
})
}
get(i, j) {
return this._grid[i][j]
}
forEach(callback) {
for (let i = 0; i < this.col; i++) {
for (let j = 0; j < this.row; j++) {
callback(this._grid[i][j])
}
}
}
draw() {
this.forEach(item => {
item.draw(color(255))
})
}
}
function setup() {
createCanvas(GameConfig.width, GameConfig.height)
gameGrid = new GameGrid(
GameConfig.col,
GameConfig.row,
GameConfig.width,
GameConfig.height
)
start = gameGrid.get(0, 0)
end = gameGrid.get(GameConfig.col - 1, GameConfig.row - 1)
start.isWall = false
end.isWall = false
openSet.push(start)
}
function draw() {
let winner = null
if (openSet.length > 0) {
// 找到 openSet 中 F 最小的节点
let winnerIndex = 0
openSet.forEach((item, index) => {
if (item.f < openSet[winnerIndex].f) {
winnerIndex = index
}
})
winner = openSet[winnerIndex]
// 如果这个winner正好等于终点 结束
if (winner === end) {
console.log('END!')
console.log(end)
noLoop()
}
// 将这个节点放入到 closedSet 中
openSet.splice(winnerIndex, 1)
closedSet.push(winner)
// 遍历该节点所有的邻接边
// 更新他们的预估最短距离
winner.neighBors.forEach(n => {
// 该节点必须还没有被确定 && 不属于墙
if (!closedSet.includes(n) && !n.isWall) {
let tempG = winner.g + 1
let newPath = false
if (openSet.includes(n)) {
// 为这个节点找到了一条更短的路径
if (tempG < n.g) {
n.g = tempG
newPath = true
}
} else {
// 该节点属于新节点 放入到 openSet 中
n.g = tempG
openSet.push(n)
newPath = true
}
// 如果路径有更新 更新 综合距离
if (newPath) {
n.h = heuristic(n, end)
n.f = n.h + n.g
n.prev = winner
}
}
})
} else {
console.log('i cant')
noLoop()
}
background(0)
gameGrid.draw()
openSet.forEach(item => {
item.draw(color(0, 255, 0))
})
closedSet.forEach(item => {
item.draw(color(255, 0, 0))
})
pathSet = []
let prev = winner
while (prev) {
pathSet.push(prev)
prev = prev.prev
}
pathSet.forEach(item => {
item.draw(color(0, 0, 255))
})
noFill()
stroke(255)
strokeWeight(1)
beginShape()
pathSet.forEach(item => {
const { x, y, width, height } = item
vertex(x * width + width / 2, y * height + height / 2)
})
endShape(0)
}