A* 寻路 +寻路演示(js)
生活随笔
收集整理的這篇文章主要介紹了
A* 寻路 +寻路演示(js)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
效果
每個單元格內文字：
(F) (Price)
(G) (H)
原理
原理是參考另一篇csdn博文，不過忘記收藏找不到了
個人理解
1、不用考慮死胡同情況，不同于普通的按照方向搜索，a* 遍歷臨近節點，即使碰到死胡同，也不需要回歸到非死胡同節點。
代碼
直接保存以下為html執行
<!DOCTYPE html> <html lang="en"> <head><meta charset="UTF-8"><title>a*</title> </head> <body> <canvas id="cv" width="1000px" height="1000px"></canvas> <script>/*** 輸入起始、目標 坐標，返回尋路結果。* 每個單元格都有代價值*///初始點let sx, sy;//目標點let es, ey;//網格數量let mx = 20, my = 20;//格子大小let cell_size = 40;//初始化網格數據let cells = [];//不可逾越代價let notAllowPrice = 10;//代價上限let priceLimit = 11;//節點對象function cell(x, y, price) {this.x = x;this.y = y;//關聯的之前單元this.prev = null;//關聯單元格坐標this.relation = new Array(8);this.relation[0] = y == 0 ? null : [x, y - 1];this.relation[1] = (y == 0 || x == mx - 1) ? null : [x + 1, y - 1];this.relation[2] = (x == mx - 1) ? null : [x + 1, y];this.relation[3] = (x == mx - 1 || y == my - 1) ? null : [x + 1, y + 1];this.relation[4] = (y == my - 1) ? null : [x, y + 1];this.relation[5] = (x == 0 || y == my - 1) ? null : [x - 1, y + 1];this.relation[6] = (x == 0) ? null : [x - 1, y];this.relation[7] = (x == 0 || y == 0) ? null : [x - 1, y - 1];//通行代價this.price = ~~(price);}//初始化畫布let el = document.getElementById('cv');let context = el.getContext("2d");let canvas_width = el.width;let canvas_height = el.height;//初始化單元數據function loadGridData() {cells = [];for (let i = 0; i < my; i++) {for (let j = 0; j < mx; j++) {cells.push(new cell(j, i, Math.random() * priceLimit))}}}//設置初始點，目標點function setStartAndEnd(x0, y0, x1, y1) {if (x0 != null && y0 != null && x1 != null && y1 != null) {sx = x0;sy = y0;ex = x1;ey = y1;} else {//設置初始點sx = ~~(Math.random() * mx);sy = ~~(Math.random() * my);// sx = 1;// sy = 17;//設置目標點ex = ~~(Math.random() * mx);ey = ~~(Math.random() * my);}let start = cells[sy * my + sx],end = cells[ey * my + ex];//確保起始點\終點是可通行start.price = 0;end.price = 0;start.f = 0;end.f = 0;start.g = 0;return {start: start, end: end}}//繪制畫布function paint() {//清空之前context.fillStyle = '#fff';context.fillRect(0,0,canvas_width,canvas_height);context.stokeStyle = `#999`;context.fillStyle = `#000`;for (let i = 0, cell; (cell = cells[i]) != null; i++) {if (cell.price < notAllowPrice) {context.rect(cell.x * cell_size, cell.y * cell_size, cell_size, cell_size)} else {context.fillRect(cell.x * cell_size, cell.y * cell_size, cell_size, cell_size)}}context.stroke();}//開始尋路async function start(x0,y0,x1,y1) {//初始單元數據loadGridData();//繪制畫板paint();//初始let {start, end} = setStartAndEnd(...arguments);//繪制起始點context.fillStyle = "green";context.fillRect(start.x * cell_size, start.y * cell_size, cell_size, cell_size);context.fillStyle = "red";context.fillRect(end.x * cell_size, end.y * cell_size, cell_size, cell_size);console.log('start:', start);console.log('end:', end);//尋路結果let result = [];//檢測列表let open_set = [];//關閉列表let close_set = [];//從起始點開始檢測open_set.push(start);let bestCell;while (open_set.length) {open_set.sort((a, b) => a.f - b.f);bestCell = open_set[0];if (bestCell == end) {while (bestCell.prev) {result.push(bestCell);bestCell = bestCell.prev;}console.log('result:', result);break;} else {close_set.push(open_set.shift());let relCell;for (let i = 0; i < bestCell.relation.length; i++) {relCell = bestCell.relation[i];if (relCell) {relCell = cells[relCell[1] * my + relCell[0]];//臨近點不可通過|臨近點已被關閉|臨界點為夾角點不可到達if (relCell.price >= notAllowPrice || close_set.includes(relCell) || !angleAllowCell(bestCell, relCell)) {continue;}if (open_set.includes(relCell)) {if (bestCell.f + cost(bestCell, relCell) < relCell.f) {relCell.prev = bestCell;relCell.g = ~~(relCell.prev.g+cost(relCell.prev,relCell));relCell.f = ~~(relCell.g + cost(relCell, end)+relCell.price);relCell.h = ~~cost(relCell,end);}continue}relCell.prev = bestCell;//g的計算方式為 前一個單元 的G + 當前單元與前一個單元的距離relCell.g = ~~(relCell.prev.g+cost(relCell.prev,relCell));relCell.f = ~~(relCell.g + cost(relCell, end)+relCell.price);relCell.h = ~~cost(relCell,end);open_set.push(relCell);//標記為檢測await delay(5).then(() => {context.fillStyle = "rgba(50,238,255,0.1)";context.fillRect(relCell.x * cell_size, relCell.y * cell_size, cell_size, cell_size);paintRelArrow(relCell, relCell.prev);paintCellText(relCell, relCell.f, 2, 10);//FpaintCellText(relCell,relCell.g,2,cell_size -2);//GpaintCellText(relCell,relCell.h,cell_size - 13,cell_size-2);//HpaintCellText(relCell,relCell.price,cell_size - 10,10);//price})}}}}if(result.length){//標記路線result.shift();//移出終點result.forEach(d => {context.fillStyle = "rgba(255,253,114,0.6)";context.fillRect(d.x * cell_size, d.y * cell_size, cell_size, cell_size);});}else{console.log('目標不可到達')}}/*================================utils=======================================*//*** 計算兩點間曼哈頓距離（可以換成歐拉）*/function cost(a, b) {return Math.abs(a.x - b.x) + Math.abs(a.y - b.y)}/*** 繪制先后關系指向箭頭，由后者指向前者并在后者中標注* @param child 子單元* @param parent*/function paintRelArrow(after, prev) {let directions = ['↑', '↗', '→', '↘', '↓', '↙', '←', '↖'];for (let i = 0; i < 8; i++) {if (after.relation[i] && after.relation[i][0] == prev.x && after.relation[i][1] == prev.y) {//←↑→↓↖↙↗↘?let text = directions[i];paintCellText(after, text, cell_size / 2 - 5, cell_size / 2 + 5);break}}}/*** tb 相對 fa 的方向t* @param fa cell* @param tb cell* @param isStrict 是否嚴格要求相鄰*/function directionType(fa, tb, isStrict) {if (isStrict) {for (let i = 0; i < 8; i++) {if (fa.relation[i] && fa.relation[i][0] == tb.x && fa.relation[i][1] == tb.y) {//←↑→↓↖↙↗↘?return i}}} else {let dx = tb.x - fa.x,dy = tb.y - fa.y;if (dx < 0) {return dy < 0 ? 7 : (dy == 0 ? 6 : 5)}if (dx == 0) {return dy < 0 ? 0 : (dy == 0 ? -1 : 4)}if (dx > 0) {return dy < 0 ? 1 : (dy == 0 ? 2 : 3)}}}/*** 根據x,y 坐標獲取實際的cell對象* @param x* @param y*/function getCellByXY(x, y) {return cells[y * my + x];}/*** 目標臨近點是否是當前節點的夾角點，判斷標準為臨近點為當前點的對角點且對角兩側為不可通過點*/function angleAllowCell(a, b) {let relation = a.relation;if (relation[1] && b == getCellByXY(...relation[1])) {return relation[0].price < notAllowPrice || relation[2].price < notAllowPrice}if (relation[3] && b == getCellByXY(...relation[3])) {return relation[2].price < notAllowPrice || relation[4].price < notAllowPrice}if (relation[5] && b == getCellByXY(...relation[5])) {return relation[4].price < notAllowPrice || relation[6].price < notAllowPrice}if (relation[7] && b == getCellByXY(...relation[7])) {return relation[6].price < notAllowPrice || relation[0].price < notAllowPrice}return true}/*** 給指定單元格的指定位置繪制文字* @param cell* @param text* @param x* @param y*/function paintCellText(cell, text, x, y) {context.font = '12px';context.fillStyle = '#000';context.fillText(text, cell.x * cell_size + x, cell.y * cell_size + y);}/*** 延時*/function delay(time) {time = time || 1000;return new Promise((res, rej) => {setTimeout(res, time)})}start();/*** 7 0 1* 6 * 2* 5 4 3*初始化open_set和close_set；* 將起點加入open_set中，并設置優先級為0（優先級最高）；* 如果open_set不為空，則從open_set中選取優先級最高的節點n：* 如果節點n為終點，則：* 從終點開始逐步追蹤parent節點，一直達到起點；* 返回找到的結果路徑，算法結束；* 如果節點n不是終點，則：* 將節點n從open_set中刪除，并加入close_set中；* 遍歷節點n所有的鄰近節點：* 如果鄰近節點m在close_set中，則：* 跳過，選取下一個鄰近節點* 如果鄰近節點m在open_set中，則：* 判斷節點n到節點m的 F(n) + cost[n,m] 值是否 < 節點m的 F(m) 。* 來嘗試更新該點，重新設置f值和父節點等數據* 如果鄰近節點m也不在open_set中，則：* 設置節點m的parent為節點n* 計算節點m的優先級* 將節點m加入open_set中**/ </script> </body> </html>總結
以上是生活随笔為你收集整理的A* 寻路 +寻路演示(js)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python小数补0,python用零填
- 下一篇： promise的三种状态_一.Promi