本文實例講述了JS實現(xiàn)的A*尋路算法。分享給大家供大家參考，具體如下：

這兩天在做百度前端技術學院的題目，其中有涉及到尋路相關的，于是就找來相關博客進行閱讀。

看了Create Chen寫的理解A*尋路算法具體過程之后，我很快就理解A*算法的原理。不得不說作者寫的很好，通熟易懂，圖片也做的很好，可見作者在這上面是花了心思的。如果讓我寫，我是寫不來這么好的。

唯一的不足就是，因為我學的是js，因此最后給我的源碼我是用不了的......因此才有自己寫一篇的打算，方面學習js人的學習。然而前面的描述我就借用他的了，因為如果然我的表達能力實在是太渣了。

簡易地圖

如圖所示簡易地圖, 其中綠色方塊的是起點 (用 A 表示), 中間藍色的是障礙物, 紅色的方塊 (用 B 表示) 是目的地. 為了可以用一個二維數(shù)組來表示地圖, 我們將地圖劃分成一個個的小方塊.

二維數(shù)組在游戲中的應用是很多的, 比如貪吃蛇和俄羅斯方塊基本原理就是移動方塊而已. 而大型游戲的地圖, 則是將各種"地貌"鋪在這樣的小方塊上.

尋路步驟

1. 從起點A開始, 把它作為待處理的方格存入一個"開啟列表", 開啟列表就是一個等待檢查方格的列表.
2. 尋找起點A周圍可以到達的方格, 將它們放入"開啟列表", 并設置它們的"父方格"為A.
3. 從"開啟列表"中刪除起點 A, 并將起點 A 加入"關閉列表", "關閉列表"中存放的都是不需要再次檢查的方格

圖中淺綠色描邊的方塊表示已經加入 "開啟列表" 等待檢查. 淡藍色描邊的起點 A 表示已經放入 "關閉列表" , 它不需要再執(zhí)行檢查.

從 "開啟列表" 中找出相對最靠譜的方塊, 什么是最靠譜? 它們通過公式 F=G+H 來計算.

F = G + H
    G 表示從起點 A 移動到網格上指定方格的移動耗費 (可沿斜方向移動).
    H 表示從指定的方格移動到終點 B 的預計耗費 (H 有很多計算方法, 這里我們設定只可以上下左右移動).

我們假設橫向移動一個格子的耗費為10, 為了便于計算, 沿斜方向移動一個格子耗費是14. 為了更直觀的展示如何運算 FGH, 圖中方塊的左上角數(shù)字表示 F, 左下角表示 G, 右下角表示 H. 看看是否跟你心里想的結果一樣?

從 "開啟列表" 中選擇 F 值最低的方格 C (綠色起始方塊 A 右邊的方塊), 然后對它進行如下處理:

4. 把它從 "開啟列表" 中刪除, 并放到 "關閉列表" 中.
5. 檢查它所有相鄰并且可以到達 (障礙物和 "關閉列表" 的方格都不考慮) 的方格. 如果這些方格還不在 "開啟列表" 里的話, 將它們加入 "開啟列表", 計算這些方格的 G, H 和 F 值各是多少, 并設置它們的 "父方格" 為 C.
6. 如果某個相鄰方格 D 已經在 "開啟列表" 里了, 檢查如果用新的路徑 (就是經過C 的路徑) 到達它的話, G值是否會更低一些, 如果新的G值更低, 那就把它的 "父方格" 改為目前選中的方格 C, 然后重新計算它的 F 值和 G 值 (H 值不需要重新計算, 因為對于每個方塊, H 值是不變的). 如果新的 G 值比較高, 就說明經過 C 再到達 D 不是一個明智的選擇, 因為它需要更遠的路, 這時我們什么也不做.

如圖, 我們選中了 C 因為它的 F 值最小, 我們把它從 "開啟列表" 中刪除, 并把它加入 "關閉列表". 它右邊上下三個都是墻, 所以不考慮它們. 它左邊是起始方塊, 已經加入到 "關閉列表" 了, 也不考慮. 所以它周圍的候選方塊就只剩下 4 個. 讓我們來看看 C 下面的那個格子, 它目前的 G 是14, 如果通過 C 到達它的話, G將會是 10 + 10, 這比 14 要大, 因此我們什么也不做.

然后我們繼續(xù)從 "開啟列表" 中找出 F 值最小的, 但我們發(fā)現(xiàn) C 上面的和下面的同時為 54, 這時怎么辦呢? 這時隨便取哪一個都行, 比如我們選擇了 C 下面的那個方塊 D.

D 右邊已經右上方的都是墻, 所以不考慮, 但為什么右下角的沒有被加進 "開啟列表" 呢? 因為如果 C 下面的那塊也不可以走, 想要到達 C 右下角的方塊就需要從 "方塊的角" 走了, 在程序中設置是否允許這樣走. (圖中的示例不允許這樣走)

就這樣, 我們從 "開啟列表" 找出 F 值最小的, 將它從 "開啟列表" 中移掉, 添加到 "關閉列表". 再繼續(xù)找出它周圍可以到達的方塊, 如此循環(huán)下去...

那么什么時候停止呢? —— 當我們發(fā)現(xiàn) "開始列表" 里出現(xiàn)了目標終點方塊的時候, 說明路徑已經被找到.

如何找回路徑

如上圖所示, 除了起始方塊, 每一個曾經或者現(xiàn)在還在 "開啟列表" 里的方塊, 它都有一個 "父方塊", 通過 "父方塊" 可以索引到最初的 "起始方塊", 這就是路徑.

將整個過程抽象

把起始格添加到 "開啟列表"

do
{
       尋找開啟列表中F值最低的格子, 我們稱它為當前格.
       把它切換到關閉列表.
       對當前格相鄰的8格中的每一個
          if (它不可通過 || 已經在 "關閉列表" 中)
          {
                什么也不做.
           }
          if (它不在開啟列表中)
          {
                把它添加進 "開啟列表", 把當前格作為這一格的父節(jié)點, 計算這一格的 FGH
          if (它已經在開啟列表中)
          {
                if (用G值為參考檢查新的路徑是否更好, 更低的G值意味著更好的路徑)
                    {
                            把這一格的父節(jié)點改成當前格, 并且重新計算這一格的 GF 值.
                    }
} while( 目標格已經在 "開啟列表", 這時候路徑被找到)

如果開啟列表已經空了, 說明路徑不存在.

最后從目標格開始, 沿著每一格的父節(jié)點移動直到回到起始格, 這就是路徑.

js代碼：

//其中的MAP.arr是二維數(shù)組
function searchRoad(start_x,start_y,end_x,end_y){
  var openList=[],  //開啟列表
    closeList=[],  //關閉列表
    result=[],   //結果數(shù)組
    result_index;  //結果數(shù)組在開啟列表中的序號
  openList.push({x:start_x,y:start_y,G:0});//把當前點加入到開啟列表中，并且G是0
  do{
    var currentPoint = openList.pop();
    closeList.push(currentPoint);
    var surroundPoint=SurroundPoint(currentPoint);
    for(var i in surroundPoint) {
      var item = surroundPoint[i];        //獲得周圍的八個點
      if (
        item.x>=0 &&              //判斷是否在地圖上
        item.y>=0 &&
        item.x<MAP.rows &&
        item.y<MAP.cols &&
        MAP.arr[item.x][item.y] != 1 &&     //判斷是否是障礙物
        !existList(item, closeList) &&     //判斷是否在關閉列表中
        MAP.arr[item.x][currentPoint.y]!=1 &&  //判斷之間是否有障礙物，如果有障礙物是過不去的
        MAP.arr[currentPoint.x][item.y]!=1) {
        //g 到父節(jié)點的位置
        //如果是上下左右位置的則g等于10，斜對角的就是14
        var g = currentPoint.G + ((currentPoint.x - item.x) * (currentPoint.y - item.y) == 0 ? 10 : 14);
        if (!existList(item, openList)) {    //如果不在開啟列表中
          //計算H，通過水平和垂直距離進行確定
          item['H'] = Math.abs(end_x - item.x) * 10 + Math.abs(end_y - item.y) * 10;
          item['G'] = g;
          item['F'] = item.H + item.G;
          item['parent'] = currentPoint;
          openList.push(item);
        }
        else {                 //存在在開啟列表中，比較目前的g值和之前的g的大小
          var index = existList(item, openList);
          //如果當前點的g更小
          if (g < openList[index].G) {
            openList[index].parent = currentPoint;
            openList[index].G = g;
            openList[index].F=g+openList[index].H;
          }
        }
      }
    }
    //如果開啟列表空了，沒有通路，結果為空
    if(openList.length==0) {
      break;
    }
    openList.sort(sortF);//這一步是為了循環(huán)回去的時候，找出 F 值最小的, 將它從 "開啟列表" 中移掉
  }while(!(result_index=existList({x:end_x,y:end_y},openList)));
  //判斷結果列表是否為空
  if(!result_index) {
    result=[];
  }
  else {
    var currentObj=openList[result_index];
    do{
      //把路勁節(jié)點添加到result當中
      result.unshift({
        x:currentObj.x,
        y:currentObj.y
      });
      currentObj=currentObj.parent;
    }while (currentObj.x!=start_x || currentObj.y!=start_y);
  }
  return result;
}
//用F值對數(shù)組排序
function sortF(a,b){
  return b.F- a.F;
}
//獲取周圍八個點的值
function SurroundPoint(curPoint){
  var x=curPoint.x,y=curPoint.y;
  return [
    {x:x-1,y:y-1},
    {x:x,y:y-1},
    {x:x+1,y:y-1},
    {x:x+1,y:y},
    {x:x+1,y:y+1},
    {x:x,y:y+1},
    {x:x-1,y:y+1},
    {x:x-1,y:y}
  ]
}
//判斷點是否存在在列表中，是的話返回的是序列號
function existList(point,list) {
  for(var i in list) {
    if(point.x==list[i].x && point.y==list[i].y) {
      return i;
    }
  }
  return false;
}

更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數(shù)學運算用法總結》、《JavaScript數(shù)據(jù)結構與算法技巧總結》、《JavaScript數(shù)組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》

希望本文所述對大家JavaScript程序設計有所幫助。

最新評論