-
Notifications
You must be signed in to change notification settings - Fork 1
/
index.html
342 lines (333 loc) · 10.3 KB
/
index.html
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
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title>js自动寻路算法-js A*算法 | jQuery特效|H5网站特效| H5游戏</title>
<meta name="keywords" content="canvas动画, 手机微信网站特效, css3动画, html5特效, 网页特效" />
<meta name="description" content="网页特效库-专注于HTML5、CSS3、js、jQuery、手机移动端等网页特效的手机与分享。所有的资源都免费提供广大童鞋下载学习和使用。" />
<style>
body,
dl,
dd {
margin: 0;
padding: 0;
}
html {
font-size: 12px;
background: #F5F5F5;
}
.block {
border: 1px solid #eaeaea;
width: 30px;
background: #FFF;
}
.start,
.start.path {
background-color: #007de7;
}
.end,
.end.path {
background-color: #333;
}
.fence {
background-color: red;
}
.path {
background-color: #57e700;
-webkit-transition: .5s all ease;
}
</style>
</head>
<body>
<div id="box" class="box"></div>
</body>
</html>
<script>
window.onload = function() {
var oBox = document.getElementById('box'); // 主容器
//创建一个文档碎片，把所有的新结点附加上，然后把文档碎片的内容一次性添加到document中，只需要一次页面刷新就可
var oFrag = document.createDocumentFragment(); // 存放临时文档碎片
var oStart = null; // 起始点
var oEnd = null; // 结束点
var aPoint = oBox.getElementsByTagName('div'); // 存放地图元素
var aMaps = []; // 存放地图数据
var maps = [];
//参数设置
var iRnd = 100; // 随机障碍数
var iRow = 30; // 存放行数
var iCol = 30; // 存放列数
var iWidth = 20; // 单元格宽
var iHeight = 20; // 单元格高
var iTime = 50; // 动画延时
//创建div元素，加入到oBox中
function render() {
oBox.innerHTML = '';
for(var i = 0; i < iRow; i++) {
for(var j = 0; j < iCol; j++) {
var oBlock = document.createElement('div');
oBlock.className = 'block';
oBlock.row = i;
oBlock.col = j;
oBlock.style.position = 'absolute';
oBlock.style.left = iWidth * j + 'px';
oBlock.style.top = iHeight * i + 'px';
oBlock.style.width = iWidth - 1 + 'px';
oBlock.style.height = iHeight - 1 + 'px';
//先加入到文档碎片中
oFrag.appendChild(oBlock);
}
}
//再将文档碎片加入oBox中
oBox.appendChild(oFrag);
oBox.style.width = iWidth * iCol + 'px';
oBox.style.height = iHeight * iRow + 'px';
oBox.style.position = 'absolute';
oBox.style.left = '50%';
oBox.style.top = '50%';
oBox.style.marginLeft = -oBox.offsetWidth / 2 + 'px';
oBox.style.marginTop = -oBox.offsetHeight / 2 + 'px';
}
//将oBox中的div添加到aMaps中（创建地图）
function module() {
aMaps = [];
aPoint = oBox.getElementsByTagName('div'); //此时已经有div加入到oBox中
for(var i = 0; i < iRow; i++) {
aMaps[i] = [];
for(var j = 0; j < iCol; j++) {
aMaps[i][j] = aPoint[i * iCol + j];
}
}
}
render(); //创建div加入oBox中
module(); //创建地图aMaps
rndFence(aMaps, iRnd, maps); //随机生成障碍物
//在地图上的点击事件
oBox.onclick = function(ev) {
var ev = ev || window.event; //ev代表事件
var target = ev.target || ev.srcElement; //target代表事件的目标对象，oBox中的div元素
// 设置起点、设置终点、设置障碍物
//test() 方法用于检测一个字符串是否匹配某个模式
if(/(\b|\s)+block(\b|\s)+/i.test(target.className)) {
if(!oStart && target.val != 1)
target.start = true,
target.className += ' start',
oStart = target;
else if(oStart && !oEnd) {
if(!target.start && target.val != 1)
target.end = true,
target.className += ' end',
oEnd = target;
else if(target.start)
return alert('起止点不能相同点');
} else if(oStart && oEnd) {
if(!target.start && !target.end && target.val != 1) {
target.val = 1;
target.className += ' fence';
} else if(target.start || target.end)
return alert('障碍点熊放置在起止点上');
}
}
//添加完起止点和障碍点后，将所有元素加入地图
module();
//开始计算路径（选择起止点后自动开始计算路径）
if(oStart && oEnd) {
var path = findway(aMaps, oStart, oEnd);
if(!path) alert('无路可走');
else {
for(var i = 0; i < path.length; i++) {
//function之前加上运算符，由于解析的缘故 ,function会即时触发，就是一个语言特征
~ function(i) {
var timer = null;
timer = setTimeout(function() {
path[i].className += ' path';
clearTimeout(timer);
}, i * iTime) //iTime为动画延时，下一个path都比上一个path延时iTime
}(i);
}
}
}
};
};
// 随机生成障碍物
function rndFence(points, num, maps) {
var total = points.length * points[0].length; //总数=行*列
var index = 0;
var col = 0;
var row = 0;
var n = 0;
var arr = [];
//当maps=null时
if(!maps || !maps.length) {
while(n < num) {
index = rnd(0, total); //在0-总数之间生成随机数
row = parseInt(index / points[0].length); //取得随机数在地图中第几行
col = index % points[0].length; //第几列
//points[row][col].val=undefine，因为里面只有div元素，没有value值
if(!points[row][col].val) {
points[row][col].val = 1;
points[row][col].className += ' fence';
n++;
} else {
continue;
}
}
}
//当maps！=null时，将maps中的障碍添加到points中
else {
for(var i = 0; i < maps.length; i++) {
for(var j = 0; j < maps[0].length; j++) {
if(maps[i][j] == 1) {
points[i][j].val = 1;
points[i][j].className += ' fence';
}
}
}
}
}
// 生成随机数
function rnd(begin, end) {
return Math.floor(Math.random() * (end - begin)) + begin;
}
// 获取四周点
function getRounds(points, current) {
var u = null; //上
var l = null; //左
var d = null; //下
var r = null; //右
var rounds = [];
// 上
if(current.row - 1 >= 0) {
u = points[current.row - 1][current.col];
rounds.push(u);
}
// 左
if(current.col - 1 >= 0) {
l = points[current.row][current.col - 1];
rounds.push(l);
}
// 下
if(current.row + 1 < points.length) {
d = points[current.row + 1][current.col];
rounds.push(d);
}
// 右
if(current.col + 1 < points[0].length) {
r = points[current.row][current.col + 1];
rounds.push(r);
}
return rounds;
}
// 监测是否在列表中
function inList(list, current) {
for(var i = 0, len = list.length; i < len; i++) {
if((current.row == list[i].row && current.col == list[i].col) || (current == list[i]))
return true;
}
return false;
}
//寻找路径（astar算法）-地图、起点、终点
function findway(points, start, end) {
var opens = []; // 存放可检索的方块(开启列表)
var closes = []; // 存放已检索的方块（关闭列表）
var cur = null; // 当前指针
var bFind = true; // 是否检索
// 设置开始点的F、G为0并放入opens列表（F=G+H）
start.F = 0;
start.G = 0;
start.H = 0;
// 将起点压入closes数组，并设置cur指向起始点
closes.push(start);
cur = start;
// 如果起始点紧邻结束点则不计算路径直接将起始点和结束点压入closes数组
if(Math.abs(start.row - end.row) + Math.abs(start.col - end.col) == 1) {
end.P = start;
closes.push(end);
bFind = false;
}
// 计算路径
while(cur && bFind) {
//如果当前元素cur不在closes列表中，则将其压入closes列表中
if(!inList(closes, cur))
closes.push(cur);
// 然后获取当前点四周点
var rounds = getRounds(points, cur);
// 当四周点不在opens数组中并且可移动，设置G、H、F和父级P，并压入opens数组
for(var i = 0; i < rounds.length; i++) {
if(rounds[i].val == 1 || inList(closes, rounds[i]) || inList(opens, rounds[i]))
continue;
else if(!inList(opens, rounds[i]) && rounds[i].val != 1) {
rounds[i].G = cur.G + 1; //不算斜的，只算横竖，设每格距离为1
rounds[i].H = Math.abs(rounds[i].col - end.col) + Math.abs(rounds[i].row - end.row);
rounds[i].F = rounds[i].G + rounds[i].H;
rounds[i].P = cur; //cur为.P的父指针
opens.push(rounds[i]);
}
}
// 如果获取完四周点后opens列表为空，则代表无路可走，此时退出循环
if(!opens.length) {
cur = null;
opens = [];
closes = [];
break;
}
// 按照F值由小到大将opens数组排序
opens.sort(function(a, b) {
return a.F - b.F;
});
// 取出opens数组中F值最小的元素，即opens数组中的第一个元素
var oMinF = opens[0];
var aMinF = []; // 存放opens数组中F值最小的元素集合
// 循环opens数组，查找F值和cur的F值一样的元素，并压入aMinF数组。即找出和最小F值相同的元素有多少
for(var i = 0; i < opens.length; i++) {
if(opens[i].F == oMinF.F)
aMinF.push(opens[i]);
}
// 如果最小F值有多个元素
if(aMinF.length > 1) {
// 计算元素与cur的曼哈顿距离
for(var i = 0; i < aMinF.length; i++) {
aMinF[i].D = Math.abs(aMinF[i].row - cur.row) + Math.abs(aMinF[i].col - cur.col);
}
// 将aMinF按照D曼哈顿距离由小到大排序（按照数值的大小对数字进行排序）
aMinF.sort(function(a, b) {
return a.D - b.D;
});
oMinF = aMinF[0];
}
// 将cur指向D值最小的元素
cur = oMinF;
// 将cur压入closes数组
if(!inList(closes, cur))
closes.push(cur);
// 将cur从opens数组中删除
for(var i = 0; i < opens.length; i++) {
if(opens[i] == cur) {
opens.splice(i, 1); //将第i个值删除
break;
}
}
// 找到最后一点，并将结束点压入closes数组
if(cur.H == 1) {
end.P = cur;
closes.push(end);
cur = null;
}
}
if(closes.length) {
// 从结尾开始往前找
var dotCur = closes[closes.length - 1];
var path = []; // 存放最终路径
var i = 0;
while(dotCur) {
path.unshift(dotCur); // 将当前点压入path数组的头部
dotCur = dotCur.P; // 设置当前点指向父级
if(!dotCur.P) {
dotCur = null;
}
}
return path;
} else {
return false;
}
}
</script>