<!DOCTYPE html> <html lang="en"> <head> <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0"> <meta charset="UTF-8"> <title>A*寻路算法</title> <style> #stage { border: 1px solid lightgray; } </style> </head> <body> <canvas></canvas> </body> <script> window.onload = function () { var stage = document.querySelector('#stage'), ctx = stage.getContext('2d'); stage.width = 600; stage.height = 600; var row = 7, column = 7, r = 40; //取区域随机数x>=min && x<max function randInt(min, max) { max = max || 0; min = min || 0; var step = Math.abs(max - min); var st = (arguments.length < 2) ? 0 : min;//参数只有一个的时候，st = 0; var result; result = st + (Math.ceil(Math.random() * step)) - 1; return result; } //普里姆算法生成连通图的二维数组 row 行 column 列 function primMaze(r, c) { //初始化数组 function init(r, c) { var a = new Array(2 * r + 1); //全部置1 for (let i = 0, len = a.length; i < len; i++) { var cols = 2 * c + 1; a[i] = new Array(cols); for (let j = 0, len1 = a[i].length; j < len1; j++) { a[i][j] = 1; } } //中间格子为0 for (let i = 0; i < r; i++) for (let j = 0; j < c; j++) { a[2 * i + 1][2 * j + 1] = 0; } return a; } //处理数组，产生最终的数组 function process(arr) { //acc存放已访问队列，noacc存放没有访问队列 var acc = [], noacc = []; var r = arr.length >> 1, c = arr[0].length >> 1; var count = r * c; for (var i = 0; i < count; i++) { noacc[i] = 0; } //定义空单元上下左右偏移 var offs = [-c, c, -1, 1], offR = [-1, 1, 0, 0], offC = [0, 0, -1, 1]; //随机从noacc取出一个位置 var pos = randInt(count); noacc[pos] = 1; acc.push(pos); while (acc.length < count) { var ls = -1, offPos = -1; offPos = -1; //找出pos位置在二维数组中的坐标 var pr = pos / c | 0, pc = pos % c, co = 0, o = 0; //随机取上下左右四个单元 while (++co < 5) { o = randInt(0, 5); ls = offs[o] + pos; var tpr = pr + offR[o]; var tpc = pc + offC[o]; if (tpr >= 0 && tpc >= 0 && tpr <= r - 1 && tpc <= c - 1 && noacc[ls] == 0) { offPos = o; break; } } if (offPos < 0) { pos = acc[randInt(acc.length)]; } else { pr = 2 * pr + 1; pc = 2 * pc + 1; //相邻空单元中间的位置置0 arr[pr + offR[offPos]][pc + offC[offPos]] = 0; pos = ls; noacc[pos] = 1; acc.push(pos); } } } var a = init(r, c); process(a); return a; //返回一个二维数组，行的数据为2r+1个,列的数据为2c+1个 } //栅格线条 function drawGrid(context, color, stepx, stepy) { context.strokeStyle = color; context.lineWidth = 0.5; for (var i = stepx + 0.5; i < context.canvas.width; i += stepx) { context.beginPath(); context.moveTo(i, 0); context.lineTo(i, context.canvas.height); context.stroke(); } for (var i = stepy + 0.5; i < context.canvas.height; i += stepy) { context.beginPath(); context.moveTo(0, i); context.lineTo(context.canvas.width, i); context.stroke(); } } //方块创造方法 function createRect(x, y, r, c) { ctx.beginPath(); ctx.fillStyle = c; ctx.rect(x, y, r, r); ctx.fill(); } //定义点对象【a*点对象】 function Point(x, y) { this.x = x; this.y = y; this.parent = null; this.f = 0; this.g = 0; this.h = 0; //当前点状态，0：表示在openlist 1:表示closelist,-1表示还没处理 this.state = -1; //flag表明该点是否可通过 this.flag = 0; } //把普通二维数组(全部由1，0表示)的转换成a*所需要的点数组 function convertArrToAS(arr) { var r = arr.length, c = arr[0].length; var a = new Array(r); for (var i = 0; i < r; i++) { a[i] = new Array(c); for (var j = 0; j < c; j++) { var pos = new Point(i, j); pos.flag = arr[i][j]; a[i][j] = pos; } } return a; } //A*算法,pathArr表示最后返回的路径 function findPathA(pathArr, start, end, row, col) { //添加数据到排序数组中 function addArrSort(descSortedArr, element, compare) { var left = 0; var right = descSortedArr.length - 1; var mid = (left + right) >> 1; while (left <= right) { var mid = (left + right) >> 1; if (compare(descSortedArr[mid], element) == 1) { left = mid + 1; } else if (compare(descSortedArr[mid], element) == -1) { right = mid - 1; } else { break; } } for (var i = descSortedArr.length - 1; i >= left; i--) { descSortedArr[i + 1] = descSortedArr[i]; } descSortedArr[left] = element; } //判断两个点是否相同 function pEqual(p1, p2) { return p1.x == p2.x && p1.y == p2.y; } //获取两个点距离，采用曼哈顿方法 function posDist(pos, pos1) { return (Math.abs(pos1.x - pos.x) + Math.abs(pos1.y - pos.y)); } function between(val, min, max) { return (val >= min && val <= max) } //比较两个点f值大小 function compPointF(pt1, pt2) { return pt1.f - pt2.f; } //处理当前节点 function processCurrpoint(arr, openList, row, col, currPoint, destPoint) { //get up,down,left,right direct var ltx = currPoint.x - 1; var lty = currPoint.y - 1; for (var i = 0; i < 3; i++){ for (var j = 0; j < 3; j++) { var cx = ltx + i; var cy = lty + j; if ((cx === currPoint.x || cy === currPoint.y) && between(ltx, 0, row - 1) && between(lty, 0, col - 1)) { var tp = arr[cx][cy]; if (tp.flag === 0 && tp.state !== 1) { if (pEqual(tp, destPoint)) { tp.parent = currPoint; return true; } if (tp.state === -1) { tp.parent = currPoint; tp.g = 1 + currPoint.g; tp.h = posDist(tp, destPoint); tp.f = tp.h + tp.f; tp.state = 0; addArrSort(openList, tp, compPointF); } else { var g = 1 + currPoint.g; if (g < tp.g) { tp.parent = currPoint; tp.g = g; tp.f = tp.g + tp.h; openList.quickSort(compPointF); } } } } } } return false; } //定义openList var openList = []; //定义closeList var closeList = []; start = pathArr[start[0]][start[1]]; end = pathArr[end[0]][end[1]]; //添加开始节点到openList; addArrSort(openList, start, compPointF); var finded = false; while ((openList.length > 0)) { var currPoint = openList.pop(); currPoint.state = 1; closeList.push(currPoint); finded = processCurrpoint(pathArr, openList, row, col, currPoint, end); if (finded) { break; } } if (finded) { var farr = []; var tp = end.parent; farr.push(end); while (tp != null) { farr.push(tp); tp = tp.parent; } return farr; } else { return null; } } //定位屏幕坐标到数组位置 function mapSCPos(i, j) { return [i / r | 0, j / r | 0]; } //检测数组中的位置是否存在方块 function mapHasRect(map, i, j) { return (map[i][j]); } var mapArr = primMaze(row, column); var startRect = { x: function () { for (var i = 0, len = mapArr.length; i < len; i++) { for (var j = 0, len1 = mapArr[i].length; j < len1; j++) { if (!mapArr[i][j]) { return j * r; break; } } } }(), y: function () { for (var i = 0, len = mapArr.length; i < len; i++) { for (var j = 0, len1 = mapArr[i].length; j < len1; j++) { if (!mapArr[i][j]) { return i * r; break; } } } }(), pos: function () { return [this.x, this.y]; } }, endRect = { hasCreate:false, x:null, y:null, pos: function () { return [this.x, this.y]; } }, startPoint = mapSCPos(startRect.pos()[1], startRect.pos()[0]), endPoint, path = null, next = null; //计算路经 function update() { ctx.clearRect(0, 0, 600, 600); drawGrid(ctx, 'lightgray', r, r); //根据地图二维数组创建色块 for (var i = 0, len = mapArr.length; i < len; i++) { for (var j = 0, len1 = mapArr[i].length; j < len1; j++) { if (mapArr[i][j]) { createRect(j * r, i * r, r, "black"); } } } //绘制开始方块 createRect(startRect.x, startRect.y, r, "red"); if (endRect.hasCreate) { //绘制跟随方块 createRect(endRect.pos()[0], endRect.pos()[1], r, "blue"); endPoint = mapSCPos(endRect.pos()[1], endRect.pos()[0]); if(path === null){ var ASmap = convertArrToAS(mapArr); path = findPathA(ASmap, startPoint, endPoint, ASmap.length, ASmap.length); }else{ next = path.pop(); startRect.y = next.x * r; startRect.x = next.y * r; if(path.length===0){ startPoint = mapSCPos(startRect.pos()[1], startRect.pos()[0]); path = null; endRect.hasCreate = false; } } } requestAnimationFrame(update); } update(); stage.addEventListener('click', function () { //标准的获取鼠标点击相对于canvas画布的坐标公式 var x = event.clientX - stage.getBoundingClientRect().left, y = event.clientY - stage.getBoundingClientRect().top; var endRectPos = mapSCPos(y, x);//[i,j] endRect.x = endRectPos[1]*r; endRect.y = endRectPos[0]*r; if (mapHasRect(mapArr, endRectPos[0], endRectPos[1])) { console.log('这个位置已经有方块啦！'); } else { endRect.pos(); endRect.hasCreate = true; } }) }; </script> </html>
JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完
内容版权声明：除非注明，否则皆为本站原创文章。
转载注明出处：http://www.heiqu.com/cfc4546c73eeba23fd7e5a21e5fcfb17.html