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; } }
<body> <div id="box" class="box"></div> </body>
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:#d1d1d1; } .path { background-color:#57e700; -webkit-transition:.5s all ease; }