A star 寻路算法

基本上就是在最短路算法上,增加了优先对列或者叫评估函数。其作用就是有方向性的寻找目标,去掉那些一定不正确的路。以此达到性能上的优化。

看看demo, 黑色点是开始点,红色是墙,白色是目标节点。

贴一下关键代码,源码在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
function g() {
var start = {
x: 3,
y: 1
};
var end = {
x: 3,
y: 5
};
// 优先队列
var q = [],
now, hash = {};
q.push(start);
while (now = q.pop()) {
console.log(now.x, now.y);
if (hash[now.x + '' + now.y]) {
// 已经走过了
continue;
}
if (now.x < 0 || now.x >= H || now.y < 0 || now.y >= W) {
// 超出地图了
continue;
}
if (!~map[now.x][now.y]) {
// 撞墙了
continue;
}
if (now.x == end.x && now.y == end.y) {
console.log('found');
return;
}
map[now.x][now.y] = 1;
hash[now.x + '' + now.y] = true;
render();
$.map(dir, (i) => {
var cx = now.x + i[0],
cy = now.y + i[1]
q.push({
x: cx,
y: cy,
v: h({
x: cx,
y: cy
}, end)
});
//console.log('q', q);
});
q.sort((a, b) => {
if (a.v > b.v) return -1;
else return 1;
});
}
}