前言

A*算法要解决的问题是找出一条起点到终点的最优路径，本文主要演示使用js代码实现的方法。讨论A*算法原理的优质文章很多，我会在下面附上相关文章链接，不文不再详细讨论原理。在后面的文章中我将用Cesium结合A*实现依照地形的路径规划。

算法核心

$$
f = g + h
$$

A*算法的核心在于它通过代价f来决定下一个要探索的节点。g为历史代价，从起始到当前节点的实际成本；h为预期代价，从当前节点到终点的估计成本。

计算过程

  1. 将起点加入开放列表（openList），这是一个待处理节点的集合。
  2. 重复以下过程直到开放列表为空。
    • 从开放列表中选择f最小的节点作为当前节点。
    • 如果当前节点是终点，则构造路径并结束。
    • 否则，遍历当前节点的每一个邻居节点。
    • 如果邻居节点已经被关闭，则忽略它。
    • 反之，则计算它的f值，设置当前节点为它的父节点，并将其加入开放列表。
    • 如果邻居节点已经被计算过f值，则检查通过当前节点到达该邻居节点是否提供了一条更短的路径。如果是，则更新它的g值和父节点。
    • 将当前关闭并从开放列表移除。
  3. 如果开放列表为空而没有找到路径，则表示不存在从起点到目标的路径。

在线Demo

计算过程演示

交互式演示

交互式演示（只走直线）

完整代码

下面是直接可以运行且添加了详细注解的代码，可以参照上面的计算过程理解下面的代码。

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
<!DOCTYPE html>
<html lang="en">

<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<title>Document</title>
	<style>
		canvas {
			margin: 20px;
		}
	</style>
</head>

<body>
	<canvas width="600" height="600"></canvas>
</body>
<script>
	let grid = [[{ "x": 0, "y": 0, "id": "0-0" }, { "x": 1, "y": 0, "id": "1-0" }, { "x": 2, "y": 0, "id": "2-0" }, { "x": 3, "y": 0, "id": "3-0" }, { "x": 4, "y": 0, "id": "4-0" }, { "x": 5, "y": 0, "id": "5-0" }, { "x": 6, "y": 0, "id": "6-0" }, { "x": 7, "y": 0, "id": "7-0" }, { "x": 8, "y": 0, "id": "8-0" }, { "x": 9, "y": 0, "id": "9-0" }, { "x": 10, "y": 0, "id": "10-0" }, { "x": 11, "y": 0, "id": "11-0" }, { "x": 12, "y": 0, "id": "12-0" }, { "x": 13, "y": 0, "id": "13-0" }, { "x": 14, "y": 0, "id": "14-0" }, { "x": 15, "y": 0, "id": "15-0" }, { "x": 16, "y": 0, "id": "16-0" }, { "x": 17, "y": 0, "id": "17-0" }, { "x": 18, "y": 0, "id": "18-0" }, { "x": 19, "y": 0, "id": "19-0" }], [{ "x": 0, "y": 1, "id": "0-1" }, { "x": 1, "y": 1, "id": "1-1" }, { "x": 2, "y": 1, "id": "2-1" }, { "x": 3, "y": 1, "id": "3-1" }, { "x": 4, "y": 1, "id": "4-1" }, { "x": 5, "y": 1, "id": "5-1" }, { "x": 6, "y": 1, "id": "6-1" }, { "x": 7, "y": 1, "id": "7-1" }, { "x": 8, "y": 1, "id": "8-1" }, { "x": 9, "y": 1, "id": "9-1" }, { "x": 10, "y": 1, "id": "10-1" }, { "x": 11, "y": 1, "id": "11-1" }, { "x": 12, "y": 1, "id": "12-1" }, { "x": 13, "y": 1, "id": "13-1" }, { "x": 14, "y": 1, "id": "14-1" }, { "x": 15, "y": 1, "id": "15-1" }, { "x": 16, "y": 1, "id": "16-1" }, { "x": 17, "y": 1, "id": "17-1" }, { "x": 18, "y": 1, "id": "18-1" }, { "x": 19, "y": 1, "id": "19-1" }], [{ "x": 0, "y": 2, "id": "0-2" }, { "x": 1, "y": 2, "id": "1-2" }, { "x": 2, "y": 2, "id": "2-2" }, { "x": 3, "y": 2, "id": "3-2" }, { "x": 4, "y": 2, "id": "4-2" }, { "x": 5, "y": 2, "id": "5-2" }, { "x": 6, "y": 2, "id": "6-2" }, { "x": 7, "y": 2, "id": "7-2" }, { "x": 8, "y": 2, "id": "8-2" }, { "x": 9, "y": 2, "id": "9-2" }, { "x": 10, "y": 2, "id": "10-2" }, { "x": 11, "y": 2, "id": "11-2" }, { "x": 12, "y": 2, "id": "12-2" }, { "x": 13, "y": 2, "id": "13-2" }, { "x": 14, "y": 2, "id": "14-2" }, { "x": 15, "y": 2, "id": "15-2" }, { "x": 16, "y": 2, "id": "16-2" }, { "x": 17, "y": 2, "id": "17-2" }, { "x": 18, "y": 2, "id": "18-2" }, { "x": 19, "y": 2, "id": "19-2" }], [{ "x": 0, "y": 3, "id": "0-3", "isClose": true }, { "x": 1, "y": 3, "id": "1-3", "isClose": true }, { "x": 2, "y": 3, "id": "2-3", "isClose": true }, { "x": 3, "y": 3, "id": "3-3", "isClose": true }, { "x": 4, "y": 3, "id": "4-3", "isClose": true }, { "x": 5, "y": 3, "id": "5-3", "isClose": true }, { "x": 6, "y": 3, "id": "6-3" }, { "x": 7, "y": 3, "id": "7-3" }, { "x": 8, "y": 3, "id": "8-3" }, { "x": 9, "y": 3, "id": "9-3" }, { "x": 10, "y": 3, "id": "10-3" }, { "x": 11, "y": 3, "id": "11-3" }, { "x": 12, "y": 3, "id": "12-3" }, { "x": 13, "y": 3, "id": "13-3" }, { "x": 14, "y": 3, "id": "14-3" }, { "x": 15, "y": 3, "id": "15-3" }, { "x": 16, "y": 3, "id": "16-3" }, { "x": 17, "y": 3, "id": "17-3" }, { "x": 18, "y": 3, "id": "18-3" }, { "x": 19, "y": 3, "id": "19-3" }], [{ "x": 0, "y": 4, "id": "0-4" }, { "x": 1, "y": 4, "id": "1-4" }, { "x": 2, "y": 4, "id": "2-4" }, { "x": 3, "y": 4, "id": "3-4" }, { "x": 4, "y": 4, "id": "4-4" }, { "x": 5, "y": 4, "id": "5-4" }, { "x": 6, "y": 4, "id": "6-4" }, { "x": 7, "y": 4, "id": "7-4" }, { "x": 8, "y": 4, "id": "8-4" }, { "x": 9, "y": 4, "id": "9-4" }, { "x": 10, "y": 4, "id": "10-4" }, { "x": 11, "y": 4, "id": "11-4" }, { "x": 12, "y": 4, "id": "12-4" }, { "x": 13, "y": 4, "id": "13-4" }, { "x": 14, "y": 4, "id": "14-4" }, { "x": 15, "y": 4, "id": "15-4" }, { "x": 16, "y": 4, "id": "16-4" }, { "x": 17, "y": 4, "id": "17-4" }, { "x": 18, "y": 4, "id": "18-4" }, { "x": 19, "y": 4, "id": "19-4" }], [{ "x": 0, "y": 5, "id": "0-5" }, { "x": 1, "y": 5, "id": "1-5" }, { "x": 2, "y": 5, "id": "2-5" }, { "x": 3, "y": 5, "id": "3-5" }, { "x": 4, "y": 5, "id": "4-5" }, { "x": 5, "y": 5, "id": "5-5" }, { "x": 6, "y": 5, "id": "6-5" }, { "x": 7, "y": 5, "id": "7-5" }, { "x": 8, "y": 5, "id": "8-5" }, { "x": 9, "y": 5, "id": "9-5" }, { "x": 10, "y": 5, "id": "10-5" }, { "x": 11, "y": 5, "id": "11-5" }, { "x": 12, "y": 5, "id": "12-5" }, { "x": 13, "y": 5, "id": "13-5" }, { "x": 14, "y": 5, "id": "14-5" }, { "x": 15, "y": 5, "id": "15-5" }, { "x": 16, "y": 5, "id": "16-5" }, { "x": 17, "y": 5, "id": "17-5" }, { "x": 18, "y": 5, "id": "18-5" }, { "x": 19, "y": 5, "id": "19-5" }], [{ "x": 0, "y": 6, "id": "0-6" }, { "x": 1, "y": 6, "id": "1-6" }, { "x": 2, "y": 6, "id": "2-6" }, { "x": 3, "y": 6, "id": "3-6" }, { "x": 4, "y": 6, "id": "4-6" }, { "x": 5, "y": 6, "id": "5-6" }, { "x": 6, "y": 6, "id": "6-6" }, { "x": 7, "y": 6, "id": "7-6" }, { "x": 8, "y": 6, "id": "8-6" }, { "x": 9, "y": 6, "id": "9-6" }, { "x": 10, "y": 6, "id": "10-6" }, { "x": 11, "y": 6, "id": "11-6" }, { "x": 12, "y": 6, "id": "12-6" }, { "x": 13, "y": 6, "id": "13-6" }, { "x": 14, "y": 6, "id": "14-6" }, { "x": 15, "y": 6, "id": "15-6" }, { "x": 16, "y": 6, "id": "16-6" }, { "x": 17, "y": 6, "id": "17-6" }, { "x": 18, "y": 6, "id": "18-6" }, { "x": 19, "y": 6, "id": "19-6" }], [{ "x": 0, "y": 7, "id": "0-7" }, { "x": 1, "y": 7, "id": "1-7" }, { "x": 2, "y": 7, "id": "2-7" }, { "x": 3, "y": 7, "id": "3-7" }, { "x": 4, "y": 7, "id": "4-7" }, { "x": 5, "y": 7, "id": "5-7" }, { "x": 6, "y": 7, "id": "6-7" }, { "x": 7, "y": 7, "id": "7-7" }, { "x": 8, "y": 7, "id": "8-7" }, { "x": 9, "y": 7, "id": "9-7" }, { "x": 10, "y": 7, "id": "10-7" }, { "x": 11, "y": 7, "id": "11-7" }, { "x": 12, "y": 7, "id": "12-7" }, { "x": 13, "y": 7, "id": "13-7" }, { "x": 14, "y": 7, "id": "14-7" }, { "x": 15, "y": 7, "id": "15-7" }, { "x": 16, "y": 7, "id": "16-7" }, { "x": 17, "y": 7, "id": "17-7" }, { "x": 18, "y": 7, "id": "18-7" }, { "x": 19, "y": 7, "id": "19-7" }], [{ "x": 0, "y": 8, "id": "0-8" }, { "x": 1, "y": 8, "id": "1-8" }, { "x": 2, "y": 8, "id": "2-8" }, { "x": 3, "y": 8, "id": "3-8" }, { "x": 4, "y": 8, "id": "4-8" }, { "x": 5, "y": 8, "id": "5-8" }, { "x": 6, "y": 8, "id": "6-8" }, { "x": 7, "y": 8, "id": "7-8" }, { "x": 8, "y": 8, "id": "8-8" }, { "x": 9, "y": 8, "id": "9-8" }, { "x": 10, "y": 8, "id": "10-8" }, { "x": 11, "y": 8, "id": "11-8" }, { "x": 12, "y": 8, "id": "12-8" }, { "x": 13, "y": 8, "id": "13-8" }, { "x": 14, "y": 8, "id": "14-8" }, { "x": 15, "y": 8, "id": "15-8" }, { "x": 16, "y": 8, "id": "16-8" }, { "x": 17, "y": 8, "id": "17-8" }, { "x": 18, "y": 8, "id": "18-8" }, { "x": 19, "y": 8, "id": "19-8" }], [{ "x": 0, "y": 9, "id": "0-9" }, { "x": 1, "y": 9, "id": "1-9" }, { "x": 2, "y": 9, "id": "2-9" }, { "x": 3, "y": 9, "id": "3-9" }, { "x": 4, "y": 9, "id": "4-9" }, { "x": 5, "y": 9, "id": "5-9", "isClose": true }, { "x": 6, "y": 9, "id": "6-9" }, { "x": 7, "y": 9, "id": "7-9" }, { "x": 8, "y": 9, "id": "8-9" }, { "x": 9, "y": 9, "id": "9-9" }, { "x": 10, "y": 9, "id": "10-9" }, { "x": 11, "y": 9, "id": "11-9" }, { "x": 12, "y": 9, "id": "12-9" }, { "x": 13, "y": 9, "id": "13-9" }, { "x": 14, "y": 9, "id": "14-9" }, { "x": 15, "y": 9, "id": "15-9" }, { "x": 16, "y": 9, "id": "16-9" }, { "x": 17, "y": 9, "id": "17-9" }, { "x": 18, "y": 9, "id": "18-9" }, { "x": 19, "y": 9, "id": "19-9" }], [{ "x": 0, "y": 10, "id": "0-10" }, { "x": 1, "y": 10, "id": "1-10" }, { "x": 2, "y": 10, "id": "2-10" }, { "x": 3, "y": 10, "id": "3-10" }, { "x": 4, "y": 10, "id": "4-10" }, { "x": 5, "y": 10, "id": "5-10", "isClose": true }, { "x": 6, "y": 10, "id": "6-10" }, { "x": 7, "y": 10, "id": "7-10" }, { "x": 8, "y": 10, "id": "8-10" }, { "x": 9, "y": 10, "id": "9-10" }, { "x": 10, "y": 10, "id": "10-10" }, { "x": 11, "y": 10, "id": "11-10" }, { "x": 12, "y": 10, "id": "12-10" }, { "x": 13, "y": 10, "id": "13-10" }, { "x": 14, "y": 10, "id": "14-10" }, { "x": 15, "y": 10, "id": "15-10" }, { "x": 16, "y": 10, "id": "16-10" }, { "x": 17, "y": 10, "id": "17-10" }, { "x": 18, "y": 10, "id": "18-10" }, { "x": 19, "y": 10, "id": "19-10" }], [{ "x": 0, "y": 11, "id": "0-11" }, { "x": 1, "y": 11, "id": "1-11" }, { "x": 2, "y": 11, "id": "2-11" }, { "x": 3, "y": 11, "id": "3-11" }, { "x": 4, "y": 11, "id": "4-11" }, { "x": 5, "y": 11, "id": "5-11", "isClose": true }, { "x": 6, "y": 11, "id": "6-11" }, { "x": 7, "y": 11, "id": "7-11" }, { "x": 8, "y": 11, "id": "8-11" }, { "x": 9, "y": 11, "id": "9-11" }, { "x": 10, "y": 11, "id": "10-11" }, { "x": 11, "y": 11, "id": "11-11" }, { "x": 12, "y": 11, "id": "12-11" }, { "x": 13, "y": 11, "id": "13-11" }, { "x": 14, "y": 11, "id": "14-11" }, { "x": 15, "y": 11, "id": "15-11" }, { "x": 16, "y": 11, "id": "16-11" }, { "x": 17, "y": 11, "id": "17-11" }, { "x": 18, "y": 11, "id": "18-11" }, { "x": 19, "y": 11, "id": "19-11" }], [{ "x": 0, "y": 12, "id": "0-12" }, { "x": 1, "y": 12, "id": "1-12" }, { "x": 2, "y": 12, "id": "2-12" }, { "x": 3, "y": 12, "id": "3-12" }, { "x": 4, "y": 12, "id": "4-12" }, { "x": 5, "y": 12, "id": "5-12" }, { "x": 6, "y": 12, "id": "6-12" }, { "x": 7, "y": 12, "id": "7-12" }, { "x": 8, "y": 12, "id": "8-12" }, { "x": 9, "y": 12, "id": "9-12" }, { "x": 10, "y": 12, "id": "10-12" }, { "x": 11, "y": 12, "id": "11-12" }, { "x": 12, "y": 12, "id": "12-12" }, { "x": 13, "y": 12, "id": "13-12" }, { "x": 14, "y": 12, "id": "14-12" }, { "x": 15, "y": 12, "id": "15-12" }, { "x": 16, "y": 12, "id": "16-12" }, { "x": 17, "y": 12, "id": "17-12" }, { "x": 18, "y": 12, "id": "18-12" }, { "x": 19, "y": 12, "id": "19-12" }], [{ "x": 0, "y": 13, "id": "0-13" }, { "x": 1, "y": 13, "id": "1-13" }, { "x": 2, "y": 13, "id": "2-13" }, { "x": 3, "y": 13, "id": "3-13" }, { "x": 4, "y": 13, "id": "4-13" }, { "x": 5, "y": 13, "id": "5-13" }, { "x": 6, "y": 13, "id": "6-13" }, { "x": 7, "y": 13, "id": "7-13" }, { "x": 8, "y": 13, "id": "8-13" }, { "x": 9, "y": 13, "id": "9-13" }, { "x": 10, "y": 13, "id": "10-13" }, { "x": 11, "y": 13, "id": "11-13" }, { "x": 12, "y": 13, "id": "12-13" }, { "x": 13, "y": 13, "id": "13-13" }, { "x": 14, "y": 13, "id": "14-13" }, { "x": 15, "y": 13, "id": "15-13" }, { "x": 16, "y": 13, "id": "16-13" }, { "x": 17, "y": 13, "id": "17-13" }, { "x": 18, "y": 13, "id": "18-13" }, { "x": 19, "y": 13, "id": "19-13" }], [{ "x": 0, "y": 14, "id": "0-14" }, { "x": 1, "y": 14, "id": "1-14" }, { "x": 2, "y": 14, "id": "2-14" }, { "x": 3, "y": 14, "id": "3-14" }, { "x": 4, "y": 14, "id": "4-14" }, { "x": 5, "y": 14, "id": "5-14" }, { "x": 6, "y": 14, "id": "6-14" }, { "x": 7, "y": 14, "id": "7-14" }, { "x": 8, "y": 14, "id": "8-14" }, { "x": 9, "y": 14, "id": "9-14" }, { "x": 10, "y": 14, "id": "10-14" }, { "x": 11, "y": 14, "id": "11-14" }, { "x": 12, "y": 14, "id": "12-14" }, { "x": 13, "y": 14, "id": "13-14" }, { "x": 14, "y": 14, "id": "14-14" }, { "x": 15, "y": 14, "id": "15-14" }, { "x": 16, "y": 14, "id": "16-14" }, { "x": 17, "y": 14, "id": "17-14" }, { "x": 18, "y": 14, "id": "18-14" }, { "x": 19, "y": 14, "id": "19-14" }], [{ "x": 0, "y": 15, "id": "0-15" }, { "x": 1, "y": 15, "id": "1-15" }, { "x": 2, "y": 15, "id": "2-15" }, { "x": 3, "y": 15, "id": "3-15" }, { "x": 4, "y": 15, "id": "4-15" }, { "x": 5, "y": 15, "id": "5-15" }, { "x": 6, "y": 15, "id": "6-15" }, { "x": 7, "y": 15, "id": "7-15" }, { "x": 8, "y": 15, "id": "8-15" }, { "x": 9, "y": 15, "id": "9-15" }, { "x": 10, "y": 15, "id": "10-15" }, { "x": 11, "y": 15, "id": "11-15" }, { "x": 12, "y": 15, "id": "12-15" }, { "x": 13, "y": 15, "id": "13-15" }, { "x": 14, "y": 15, "id": "14-15" }, { "x": 15, "y": 15, "id": "15-15" }, { "x": 16, "y": 15, "id": "16-15" }, { "x": 17, "y": 15, "id": "17-15" }, { "x": 18, "y": 15, "id": "18-15" }, { "x": 19, "y": 15, "id": "19-15" }], [{ "x": 0, "y": 16, "id": "0-16" }, { "x": 1, "y": 16, "id": "1-16" }, { "x": 2, "y": 16, "id": "2-16" }, { "x": 3, "y": 16, "id": "3-16" }, { "x": 4, "y": 16, "id": "4-16" }, { "x": 5, "y": 16, "id": "5-16", "isClose": true }, { "x": 6, "y": 16, "id": "6-16", "isClose": true }, { "x": 7, "y": 16, "id": "7-16", "isClose": true }, { "x": 8, "y": 16, "id": "8-16", "isClose": true }, { "x": 9, "y": 16, "id": "9-16", "isClose": true }, { "x": 10, "y": 16, "id": "10-16", "isClose": true }, { "x": 11, "y": 16, "id": "11-16", "isClose": true }, { "x": 12, "y": 16, "id": "12-16", "isClose": true }, { "x": 13, "y": 16, "id": "13-16", "isClose": true }, { "x": 14, "y": 16, "id": "14-16", "isClose": true }, { "x": 15, "y": 16, "id": "15-16", "isClose": true }, { "x": 16, "y": 16, "id": "16-16", "isClose": true }, { "x": 17, "y": 16, "id": "17-16", "isClose": true }, { "x": 18, "y": 16, "id": "18-16", "isClose": true }, { "x": 19, "y": 16, "id": "19-16", "isClose": true }], [{ "x": 0, "y": 17, "id": "0-17" }, { "x": 1, "y": 17, "id": "1-17" }, { "x": 2, "y": 17, "id": "2-17" }, { "x": 3, "y": 17, "id": "3-17" }, { "x": 4, "y": 17, "id": "4-17" }, { "x": 5, "y": 17, "id": "5-17" }, { "x": 6, "y": 17, "id": "6-17" }, { "x": 7, "y": 17, "id": "7-17" }, { "x": 8, "y": 17, "id": "8-17" }, { "x": 9, "y": 17, "id": "9-17" }, { "x": 10, "y": 17, "id": "10-17" }, { "x": 11, "y": 17, "id": "11-17" }, { "x": 12, "y": 17, "id": "12-17" }, { "x": 13, "y": 17, "id": "13-17" }, { "x": 14, "y": 17, "id": "14-17" }, { "x": 15, "y": 17, "id": "15-17" }, { "x": 16, "y": 17, "id": "16-17" }, { "x": 17, "y": 17, "id": "17-17" }, { "x": 18, "y": 17, "id": "18-17" }, { "x": 19, "y": 17, "id": "19-17" }], [{ "x": 0, "y": 18, "id": "0-18" }, { "x": 1, "y": 18, "id": "1-18" }, { "x": 2, "y": 18, "id": "2-18" }, { "x": 3, "y": 18, "id": "3-18" }, { "x": 4, "y": 18, "id": "4-18" }, { "x": 5, "y": 18, "id": "5-18" }, { "x": 6, "y": 18, "id": "6-18" }, { "x": 7, "y": 18, "id": "7-18" }, { "x": 8, "y": 18, "id": "8-18" }, { "x": 9, "y": 18, "id": "9-18" }, { "x": 10, "y": 18, "id": "10-18" }, { "x": 11, "y": 18, "id": "11-18" }, { "x": 12, "y": 18, "id": "12-18" }, { "x": 13, "y": 18, "id": "13-18" }, { "x": 14, "y": 18, "id": "14-18" }, { "x": 15, "y": 18, "id": "15-18" }, { "x": 16, "y": 18, "id": "16-18" }, { "x": 17, "y": 18, "id": "17-18" }, { "x": 18, "y": 18, "id": "18-18" }, { "x": 19, "y": 18, "id": "19-18" }], [{ "x": 0, "y": 19, "id": "0-19" }, { "x": 1, "y": 19, "id": "1-19" }, { "x": 2, "y": 19, "id": "2-19" }, { "x": 3, "y": 19, "id": "3-19" }, { "x": 4, "y": 19, "id": "4-19" }, { "x": 5, "y": 19, "id": "5-19" }, { "x": 6, "y": 19, "id": "6-19" }, { "x": 7, "y": 19, "id": "7-19" }, { "x": 8, "y": 19, "id": "8-19" }, { "x": 9, "y": 19, "id": "9-19" }, { "x": 10, "y": 19, "id": "10-19" }, { "x": 11, "y": 19, "id": "11-19" }, { "x": 12, "y": 19, "id": "12-19" }, { "x": 13, "y": 19, "id": "13-19" }, { "x": 14, "y": 19, "id": "14-19" }, { "x": 15, "y": 19, "id": "15-19" }, { "x": 16, "y": 19, "id": "16-19" }, { "x": 17, "y": 19, "id": "17-19" }, { "x": 18, "y": 19, "id": "18-19" }, { "x": 19, "y": 19, "id": "19-19" }]]
	let origin = grid[0][0];//定义起点
	let destination = grid[19][19];//定义终点
	let canvas = document.querySelector("canvas");
	let ctx = canvas.getContext("2d");
	//在canvas上绘制网格,并为grid数组中的每一项添加boundingClientRect(left,top,width,height)属性和h属性(预期代价)
	for (let i = 0; i < grid.length; i++) {
		for (let j = 0; j < grid[i].length; j++) {
			ctx.beginPath();
			let node = grid[i][j];
			let width = canvas.width / grid[i].length;
			let height = canvas.height / grid.length;
			if (node.isClose) {
				ctx.fillStyle = "#868679";
			} else {
				ctx.fillStyle = "#eee";
			}
			let left = node.x * width;
			let top = node.y * height;
			ctx.rect(left, top, width, height);
			node.boundingClientRect = {
				left,
				top,
				width,
				height
			};
			ctx.fill();
			ctx.strokeStyle = "#fff";
			ctx.lineWidth = 1;
			ctx.stroke();
			if (origin.id == node.id) {
				let img = new Image();
				img.src = "./images/origin.png";
				img.onload = function () {
					ctx.drawImage(img, left, top, width, height);
				}
			} else if (destination.id == node.id) {
				let img = new Image();
				img.src = "./images/destination.png";
				img.onload = function () {
					ctx.drawImage(img, left, top, width, height);
				}
			}
			//计算每个节点的预期代价（与终点的距离）
			node.h = Math.sqrt(Math.pow(j - destination.x, 2) + Math.pow(i - destination.y, 2));
		}
	}


	let openList = [];//待计算的节点
	origin.g = 0;//初始化起点的历史代价
	openList.push(origin);
	while (openList.length) {
		//根据代价逆序排序，从openList中获取到代价最小的节点（如果有多个代价相同的点，优先选择 g 值（历史代价）较小的节点，这更有可能导向最短路径。）
		let sortedByF = openList.sort((a, b) => {
			if (a.f == b.f) {
				return a.g - b.g;
			}
			return a.f - b.f
		});
		//将代价最小的节点设置为当前要计算节点
		let nodeCurrent = sortedByF[0];
		//如果当前节点是终点，构造路径并结束
		if (nodeCurrent.id == destination.id) {
			ctx.beginPath();
			let parentId = destination.parentId;
			ctx.moveTo(destination.boundingClientRect.left + destination.boundingClientRect.width / 2, destination.boundingClientRect.top + destination.boundingClientRect.height / 2);
			//根据parentId一层层回溯出最短路径
			while (parentId) {
				let lastNode = grid.flat().find(({ id }) => id == parentId);
				ctx.strokeStyle = "#6c76ca";
				ctx.lineTo(lastNode.boundingClientRect.left + lastNode.boundingClientRect.width / 2, lastNode.boundingClientRect.top + lastNode.boundingClientRect.height / 2);
				ctx.stroke();
				parentId = lastNode.parentId;
			}
			break;
		}
		//获取当前节点周围的节点
		let childUp = grid[nodeCurrent.y - 1]?.[nodeCurrent.x];//上
		let childRight = grid[nodeCurrent.y]?.[nodeCurrent.x + 1];//下
		let childDown = grid[nodeCurrent.y + 1]?.[nodeCurrent.x];//左
		let childLeft = grid[nodeCurrent.y]?.[nodeCurrent.x - 1];//右边
		let childList = [childUp, childRight, childDown, childLeft];
		//只有当左边和上边不全是障碍物，才能走左上的节点
		if (!childUp?.isClose || !childLeft?.isClose) {
			let childLeftUp = grid[nodeCurrent.y - 1]?.[nodeCurrent.x - 1];
			childList.push(childLeftUp);
		}
		//只有当右边和上边不全是障碍物，才能走右上的节点
		if (!childUp?.isClose || !childRight?.isClose) {
			let childRightUp = grid[nodeCurrent.y - 1]?.[nodeCurrent.x + 1];
			childList.push(childRightUp);
		}
		//只有当右边和下边不全是障碍物，才能走右下的节点
		if (!childDown?.isClose || !childRight?.isClose) {
			let childRightDown = grid[nodeCurrent.y + 1]?.[nodeCurrent.x + 1];
			childList.push(childRightDown);
		}
		//只有当左边和下边不全是障碍物，才能走左下的节点
		if (!childDown?.isClose || !childLeft?.isClose) {
			let childLeftDown = grid[nodeCurrent.y + 1]?.[nodeCurrent.x - 1];
			childList.push(childLeftDown);
		}
		//为周围的节点设置父节点id
		for (let i = 0; i < childList.length; i++) {
			let child = childList[i];
			if (!child || child.isClose) {//child.isClose代表已经关闭或为障碍，不计算
				continue
			}
			//计算当前节点到它子节点的距离
			let currentToChild = Math.sqrt(Math.pow(nodeCurrent.x - child.x, 2) + Math.pow(nodeCurrent.y - child.y, 2));
			if (child.f === undefined) {//这个子节点的代价从来没有被计算过，现在计算它的代价
				child.parentId = nodeCurrent.id;
				//子节点的历史代价是当前节点历史代价加上当前节点到子节点的距离
				child.g = nodeCurrent.g + currentToChild;
				//子节点的未来期望代价是子节点到终点的距离
				child.h = Math.sqrt(Math.pow(child.x - destination.x, 2) + Math.pow(child.y - destination.y, 2));
				//得出最终代价
				child.f = child.g + child.h;
				openList.push(child);//将这个子节点加入到待计算列表中
			} else {//这个子节点被计算过
				// 将子节点的父级替换为当前节点重新计算历史代价
				let g = nodeCurrent.g + currentToChild;
				//如果更换为新父级后历史代价比以前小，就更新它的父节点为当前节点
				if (g < child.g) {
					child.g = g;
					child.f = child.g + child.h;
					child.parentId = nodeCurrent.id;
				}
			}
		}
		//将当前节点从待计算列表中移除并将它关闭
		let index = openList.findIndex(({ id }) => id == nodeCurrent.id);
		openList[index].isClose = true;
		openList.splice(index, 1);
	}
</script>
</html>

参照

通俗易懂聊A*算法 - 知乎

A* 寻路算法 - christanxw的专栏 - C++博客