寻路算法

在线演示

A 星算法

A*搜寻算法俗称A星算法。A*算法是比较流行的启发式搜索算法之一,被广泛应用于路径优化领域。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价该节点处于最短路线上的可能性的量度

概念

OpenList: 能走的节点
CloseList: 走过的节点
节点评估公式:F = G + H

  • G:从起点到当前节点走过的节点数
  • H:忽视障碍物,从当前节点到目的节点距离
  • F:总体评估值,越低表示最优

举例

活动图

代码片段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
var row = 20, // y轴
col= 20, // x轴
start = {
y: 1,
x: 1
}, // 开始节点信息
end = {
y: 1,
x: 5
}, // 目的节点
opens: [], // 能走的节点
closes: [], // 走过的节点
// 节点结构
class Node {
x;
y;
f = 0;
g = 0;
h = 0;
id = 0;
parent = null;
constructor(x, y) {
this.x = Number(x);
this.y = Number(y);
}
insertParentNode(parent, end) {
this.parent = parent;
this.g = parent.g + 1;
this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
this.f = this.g + this.h;
}
}
// 主要逻辑
find() {
let that = this,
start = that.start,
end = that.end,
opens = [],
closes = [],
startNode = new Node(start.x, start.y),
endNode = new Node(end.x, end.y),
result = null;
opens.push(startNode);
// 遍历 openList
while (opens.length > 0) {
// 找出 openList 中 F 最低的节点作为当前节点
let { node, index } = this.findMindPath(opens);
// 移动至 closeList
opens.splice(index, 1);
closes.push(node);
// 找出当前节点能走的下个节点,放入 openList
for (const neighbour of this.findNeighbors(node, opens, closes)) {
neighbour.insertParentNode(node, endNode);
opens.push(neighbour);
}
// 若当前节点为目的节点则结束循环
if (node.x == end.x && node.y == end.y) {
result = node;
break;
}
}
while (result?.parent?.parent != null) {
this.$refs[result.parent.getNodeId(this.col)][0].style.backgroundColor = "#ffd400";
result = result.parent;
}
}
// 找出最优节点
findMindPath(opens) {
let node = opens[0];
let index = 0;
opens.forEach(function(temp, i) {
if (node.f > temp.f) {
node = temp;
index = i;
}
});
return { node, index };
}
// 找出下一个节点
findNeighbors(node, opens, closes) {
let neighbors = [];
if (this.hasValidNode(node.x, node.y - 1, opens, closes)) {
neighbors.push(new Node(node.x, node.y - 1));
}
if (this.hasValidNode(node.x, node.y + 1, opens, closes)) {
neighbors.push(new Node(node.x, node.y + 1));
}
if (this.hasValidNode(node.x - 1, node.y, opens, closes)) {
neighbors.push(new Node(node.x - 1, node.y));
}
if (this.hasValidNode(node.x + 1, node.y, opens, closes)) {
neighbors.push(new Node(node.x + 1, node.y));
}
return neighbors;
},
hasValidNode(x, y, opens, closes) {
if (
x < 1 ||
x > this.col ||
y < 1 ||
y > this.row
) {
return false;
}

if (opens.filter(n => n.x == x && n.y == y).length > 0) {
return false;
}

if (closes.filter(n => n.x == x && n.y == y).length > 0) {
return false;
}

return true;
}

完整代码 gitee