网站策划方案目标,图片素材的网站,最新手机资讯,网络优化工程师招聘信息本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法。分享给大家供大家参考#xff0c;具体如下#xff1a;完整实例代码如下#xff1a;A*寻路算法#stage {border: 1px solid lightgray;}window.onload function () {var stage document.querySelector(#stage…本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法。分享给大家供大家参考具体如下完整实例代码如下A*寻路算法#stage {border: 1px solid lightgray;}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;//取区域随机数xmin xfunction 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);//全部置1for (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;}}//中间格子为0for (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;//相邻空单元中间的位置置0arr[pr offR[offPos]][pc offC[offPos]] 0;pos ls;noacc[pos] 1;acc.push(pos);}}}var a init(r, c);process(a);return a;//返回一个二维数组行的数据为2r1个,列的数据为2c1个}//栅格线条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;}//把普通二维数组(全部由10表示)的转换成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 directvar 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;}//定义openListvar openList [];//定义closeListvar 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.length0){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;}})};使用在线HTML/CSS/JavaScript代码运行工具http://tools.jb51.net/code/HtmlJsRun测试运行上述代码可得到如下运行效果希望本文所述对大家JavaScript程序设计有所帮助。
