您好,登錄后才能下訂單哦!
本文實(shí)例講述了JS/HTML5游戲常用算法之路徑搜索算法 A*尋路算法。分享給大家供大家參考,具體如下:
原理可參考:https://www.jb51.net/article/152744.htm
完整實(shí)例代碼如下:
<!DOCTYPE html> <html lang="en"> <head> <meta name="viewport" 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 id="stage"></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; //取區(qū)域隨機(jī)數(shù)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;//參數(shù)只有一個(gè)的時(shí)候,st = 0; var result; result = st + (Math.ceil(Math.random() * step)) - 1; return result; } //普里姆算法生成連通圖的二維數(shù)組 row 行 column 列 function primMaze(r, c) { //初始化數(shù)組 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; } //處理數(shù)組,產(chǎn)生最終的數(shù)組 function process(arr) { //acc存放已訪問隊(duì)列,noacc存放沒有訪問隊(duì)列 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]; //隨機(jī)從noacc取出一個(gè)位置 var pos = randInt(count); noacc[pos] = 1; acc.push(pos); while (acc.length < count) { var ls = -1, offPos = -1; offPos = -1; //找出pos位置在二維數(shù)組中的坐標(biāo) var pr = pos / c | 0, pc = pos % c, co = 0, o = 0; //隨機(jī)取上下左右四個(gè)單元 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; //返回一個(gè)二維數(shù)組,行的數(shù)據(jù)為2r+1個(gè),列的數(shù)據(jù)為2c+1個(gè) } //柵格線條 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(); } } //方塊創(chuàng)造方法 function createRect(x, y, r, c) { ctx.beginPath(); ctx.fillStyle = c; ctx.rect(x, y, r, r); ctx.fill(); } //定義點(diǎn)對(duì)象【a*點(diǎn)對(duì)象】 function Point(x, y) { this.x = x; this.y = y; this.parent = null; this.f = 0; this.g = 0; this.h = 0; //當(dāng)前點(diǎn)狀態(tài),0:表示在openlist 1:表示closelist,-1表示還沒處理 this.state = -1; //flag表明該點(diǎn)是否可通過 this.flag = 0; } //把普通二維數(shù)組(全部由1,0表示)的轉(zhuǎn)換成a*所需要的點(diǎn)數(shù)組 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) { //添加數(shù)據(jù)到排序數(shù)組中 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; } //判斷兩個(gè)點(diǎn)是否相同 function pEqual(p1, p2) { return p1.x == p2.x && p1.y == p2.y; } //獲取兩個(gè)點(diǎn)距離,采用曼哈頓方法 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) } //比較兩個(gè)點(diǎn)f值大小 function compPointF(pt1, pt2) { return pt1.f - pt2.f; } //處理當(dāng)前節(jié)點(diǎn) 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]]; //添加開始節(jié)點(diǎn)到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; } } //定位屏幕坐標(biāo)到數(shù)組位置 function mapSCPos(i, j) { return [i / r | 0, j / r | 0]; } //檢測(cè)數(shù)組中的位置是否存在方塊 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; //計(jì)算路經(jīng) function update() { ctx.clearRect(0, 0, 600, 600); drawGrid(ctx, 'lightgray', r, r); //根據(jù)地圖二維數(shù)組創(chuàng)建色塊 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 () { //標(biāo)準(zhǔn)的獲取鼠標(biāo)點(diǎn)擊相對(duì)于canvas畫布的坐標(biāo)公式 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('這個(gè)位置已經(jīng)有方塊啦!'); } else { endRect.pos(); endRect.hasCreate = true; } }) }; </script> </html>
使用在線HTML/CSS/JavaScript代碼運(yùn)行工具:http://tools.jb51.net/code/HtmlJsRun,測(cè)試運(yùn)行上述代碼,可得到如下運(yùn)行效果:
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。