A*寻路算法

发表于 | 分类于
字数统计: 1,078 | 阅读时长 ≈ 5

你是否在做一款H5游戏的时候想创造一些游戏主角，让它们移动到指定的位置，避开墙壁和障碍物呢？
下面的案例是由纯js实现的,由canvas绘图，并只考虑向上下左右四邻域移动。

效果展示图

有路可走

无路可走

核心思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//第一步：画棋盘，向外扩展一圈
    var $map = drawmap(me.opts, me.$element);
// 第二步：画障碍点和边界，初始化所有点,左上角为（0,0）
    drawpoint(me, $map);
//这里默认把起点放入已检测点
    var startnum = posToindex(me.opts.startY, me.opts.startX, me.opts.mapXnum);
    var endnum = posToindex(me.opts.endY, me.opts.endX, me.opts.mapXnum);
    me.closelist.push(me.wall[startnum]);
//第三步：从起点开始上下左右找扩展点出去，并记录父子点对。如果该点status是0且从未放入过openlist，就放入openlist
//从openlist中找F值最小的点组，我这里做了个优化，并选择点组中最后加入openlist的点放入closelist
//从当前已检测点再向外检测，要么检测到终点就停止，要么待检测点全部检测完还找不到终点就停止。
    searchroad(me, [me.opts.startY, me.opts.startX], startnum);
//第四步:画检测的所有点，用红色细线标出，只需要把每个fatherson里的父子连起来就好了(这一步可以不画，跳过)
    drawroad(me);
//第五步：画最终路线，黄色粗线标出。因为子元素的父元素只有一个，而一个父元素有多个子元素（比较难找），所以我们选择从终点往起点找，把能连的线全部连起来就好
    drawFinalRoad(me.fatherson, startnum, endnum, me);

我是如下初始化参数的：

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
var me = this;
// 原型中的this不是指的原型对象，而是调用对象。
//用于存地图的长和宽
me.opts = $.extend(true, {}, { //用于设弹窗默认值
    mapXnum: 10,
    mapYnum: 10,
    startX: 3,
    startY: 3,
    endX: 6,
    endY: 6,
    wallnum: 10,
    map_Per: 40//每个格子的长度
}, options);
me.wall = [];//整张图信息，村边界和所有的障碍物的坐标标1，起点标2，终点标3,其余标0，距离左边，距离右边
//index从上往下数数，从0开始，下次用二维数组做试试。。。一开始咋先用了一维。。。
me.openlist = [];//待检测的点
me.closelist = [];//已检测的点
me.fatherson = [];//检测过程中记录父子关系对，父节点向上下左右寻找子节点时记录一下
var num = 0;
for (var i = 0; i < Number(me.opts.mapYnum) + 2; i++) {
    for (var j = 0; j < Number(me.opts.mapXnum) + 2; j++) {
        if (i == 0 || i == Number(me.opts.mapYnum) + 1 || j == 0 || j == Number(me.opts.mapXnum) + 1) {
            me.wall.push({
                status: 1,
                pos: [i, j],
                f_score: 9999,
                index: num++
            });
        } else if (i == me.opts.startY && j == me.opts.startX) {
            me.wall.push({
                g_score: 0,
                status: 2,
                pos: [i, j],
                index: num++
            });
        } else if (i == me.opts.endY && j == me.opts.endX) {
            me.wall.push({
                g_score: 0,
                h_score: 0,
                f_score: 0,
                status: 3,
                pos: [i, j],
                index: num++
            });
        } else {
            me.wall.push({
                g_score: 0,
                h_score: Math.abs(i - me.opts.endY) + Math.abs(j - me.opts.endX),
                f_score: 0,
                status: 0,
                pos: [i, j],
                index: num++,
                inopen: 0
            });
        }
    }
}

小结

我是这么理解的，Dijkstra算法就是从起点开始一圈一圈向外扩散，直到扩散到终点，这样做肯定慢，但还是能找到一条最短路径。贪婪算法从直观上理解就是用最快的方法来解决问题，主要目标是快，从数学上来理解就是在做判断时以当前最优解为基础，每次取的都是当前位置距离终点最近的点，因为算法是取的局部最优解，没有考虑以后的问题，所以整体上是很难找到最短路径的。
贪婪是每个人都有的，但也要适可而止。我们的目标是要找到一条最短路径的前提下，速度适当的要快一点。于是，A*算法就应运而生了，既考虑了起点，又考虑了终点（要选取适合的启发函数）。明白了它大概的思想后，童鞋们就可以开始摸索啦~~~嘻嘻

原文链接
代码链接

-------------end·君-------------