Algorithm/A_star.html at master · zyh1994/Algorithm · GitHub

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<canvas id="myCanvas" width="1800" height="1800" style="background-color: black">
</canvas>
</body>
<script>
    var c = document.getElementById("myCanvas");
    var ctx = c.getContext("2d");

    function removeFromArray(arr, elt) {
        for (var i = arr.length - 1; i >= 0; i--) {
            if (arr[i] === elt) {
                arr.splice(i, 1);
            }
        }
    }

    function heuristic(a, b) {
        return Math.sqrt((a.i - b.i) * (a.i - b.i) + (a.j - b.j) * (a.j - b.j));
        // return Math.abs(a.i - b.i) + Math.abs(a.j - b.j);
        // return 0;
    }

    var cols = 25;
    var rows = 25;
    var grid = new Array(cols);

    var openSet = [];
    var closeSet = [];
    var start, end, w, h, path = [], t;

    function Spot(i, j) {
        this.i = i;
        this.j = j;
        this.f = 0;
        this.g = 0;
        this.h = 0;
        this.neighbors = [];
        this.previous = undefined;
        this.wall = Math.random() < 0.2 ;


        this.show = function (col) {
            if (this.wall)
                col = "#000000";
            ctx.fillStyle = col;
            ctx.fillRect(this.i * w + 1, this.j * h + 1, w - 2, h - 2);
        };

        this.addNeighbors = function (grid) {
            var i = this.i;
            var j = this.j;

            if (i < cols - 1) {
                this.neighbors.push(grid[i + 1][j]);
            }
            if (i > 0) {
                this.neighbors.push(grid[i - 1][j]);
            }
            if (j < rows - 1) {
                this.neighbors.push(grid[i][j + 1]);
            }
            if (j > 0) {
                this.neighbors.push(grid[i][j - 1]);
            }
            if (i > 0 && j > 0) {
                this.neighbors.push(grid[i - 1][j - 1]);
            }
            if (i > 0 && j < rows - 1) {
                this.neighbors.push(grid[i - 1][j + 1]);
            }
            if (i < cols - 1 && j < rows - 1) {
                this.neighbors.push(grid[i + 1][j + 1]);
            }
            if (i > cols - 1 && j > 0) {
                this.neighbors.push(grid[i + 1][j - 1]);
            }

        }
    }

    function setup() {
        console.log('A*');

        w = c.width / cols;
        h = c.height / rows;


        //create 2d
        for (var i = 0; i < rows; i++) {
            grid[i] = new Array(cols);
        }

        for (var i = 0; i < cols; i++) {
            for (var j = 0; j < rows; j++) {
                grid[i][j] = new Spot(i, j);
            }
        }
        for (var i = 0; i < cols; i++) {
            for (var j = 0; j < rows; j++) {
                grid[i][j].addNeighbors(grid);
            }
        }

    }
    function dist_between(current, neighbor) {
        // if(current.i==neighbor.i||current.j==neighbor.j){
        //     return 1;
        // }else{
        //     return 1.414;
        // }
        return 1;
    }

    /**
     * 为了达到动画效果，设置定时器，进行循环计算，当结果计算完成，取消定时器
     */
    function draw() {
        //计算开始，判断可选集合是否为空，不为空开始计算。计算中可以得到计算结果，得到最短路径取消定时器。
        //当可选集的元素被取完，仍然没有结果时，返回无结果，并终止定时器。
        if (openSet.length > 0) {
            //在可选集中循环获取最短路径评价f值。
            var winner = 0;
            for (var i = 0; i < openSet.length; i++) {
                if (openSet[i].f < openSet[winner].f) {
                    winner = i;
                }
            }

            var current = openSet[winner];
            //判断最短路点是否为目标点，是停止计算，取消定时器
            if (current == end) {
                console.log("over !");
                clearInterval(t);
            }
            //从可选集中移除当前点，并加入到最优集
            removeFromArray(openSet, current);
            closeSet.push(current);
            //获取当前点的边界点集，循环判断边界点的
            var neighbors = current.neighbors;
            for (var i = 0; i < neighbors.length; i++) {
                var neighbor = neighbors[i];
                //判断边界点是否已经属于最优解集，或者为障碍物
                //如果都不是，表明边界点可以被作为候选点，
                if (!closeSet.includes(neighbor) && !neighbor.wall) {
                    //该处需要重新考虑，通常上下左右的g值要小于肩的g值，
                    // 且肩的g值要小于左右或上下两值和的g值（满足三角形定义：两边之和大于第三边）
                    //此处未做任何处理。tentative_gScore := gScore[current] + dist_between(current, neighbor)
                    var tempG = current.g + dist_between(current, neighbor);
                    //
                    // var newPath = false;
                    // // 判断边界点是否在可选集中，如果处于可选集中；当新计算的g值比原值小时，
                    // // 表明路径需要被更换，且需要更新边界点的g值。
                    //     if (openSet.includes(neighbor)) {
                    //         if (tempG < neighbor.g) {
                    //             neighbor.g = tempG;
                    //             newPath = true;
                    //         }
                    //     } else {
                    //         //不在可选集中，将边界点添加进可选集。且该条路径为新路径
                    //         neighbor.g = tempG;
                    //         newPath = true;
                    //         openSet.push(neighbor);
                    //     }
                    //     if (newPath) {
                    //         //计算h和f，并将边界点的父节点指向为当前点，用以构成路线
                    //         neighbor.h = heuristic(neighbor, end);
                    //         neighbor.f = neighbor.g + neighbor.h;
                    //         neighbor.previous = current;
                    // }
                    //如果临界点不在开放集合，将之加入到开放集合中
                    if (!openSet.includes(neighbor)) {
                        openSet.push(neighbor);
                    } else if (tempG >= neighbor.g) {
                        //如果在开放集合中，判断g值是否小于所需要的扩增值
                        continue;
                    }

                    neighbor.h = heuristic(neighbor, end);
                    neighbor.g = tempG;
                    neighbor.f = neighbor.g + neighbor.h;
                    neighbor.previous = current;
                    //为什么？
                    //1、如果边界点不在开放集合中，计算边界点的f，g，h值，并绑点初始点。
                    //2、如果在集合内，由步进值重新判断该点的g值。
                }
            }


        } else {
            clearInterval(t);
            alert("no solution!");
            return;
            //no solution
        }
        //绘图
        for (var i = 0; i < cols; i++) {
            for (var j = 0; j < rows; j++) {
                grid[i][j].show("#FFFFFF");
            }
        }
        for (var i = 0; i < closeSet.length; i++) {
            closeSet[i].show("#FF0000");
        }

        for (var i = 0; i < openSet.length; i++) {
            openSet[i].show("#00FF00");
        }

        //Find the path
        path = [];
        var temp = current;
        path.push(temp);
        while (temp.previous) {
            path.push(temp.previous);
            temp = temp.previous;
        }

        for (var i = 0; i < path.length; i++) {
            path[i].show("#0000FF");
        }
    }


    setup();
    start = grid[0][0];
    end = grid[cols - 1][rows - 1];
    openSet.push(start);
    start.wall = false;
    end.wall = false;

    t = setInterval(draw, 100);
    // console.log(grid);
    // console.log(path);
    //1、起点，终点，从起点获取所有可达边界集，
    //2、筛选最低评价值f，获取当前边界点。
    //3、移除当前边界点，扩充可达集，修正f与路线集
    //3.1、评价函数f=g+h，g代表：当前点到原点的成本值，h代表当前点到终点的成本值。
    //4、循环上述步骤
</script>
</html>