用JavaScript實現(xiàn)A*算法

??A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法对粪,注意——是最有效的直接搜索算法,之后涌現(xiàn)了很多預(yù)處理算法(如ALT箱靴,CH腺逛,HL等等),在線查詢效率是A*算法的數(shù)千甚至上萬倍衡怀。

核心思想
??公式: f(n) = g(n) + h(n)
??其中棍矛, f(n) 是從初始狀態(tài)經(jīng)由狀態(tài)n到目標狀態(tài)的代價估計安疗,g(n) 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實際代價,h(n) 是從狀態(tài)n到目標狀態(tài)的最佳路徑的估計代價够委,保證找到最短路徑(最優(yōu)解的)條件荐类,關(guān)鍵在于估價函數(shù)f(n)的選取(或者說h(n)的選茸旅薄)玉罐。

距離估計與實際值越接近,估價函數(shù)取得就越好
??例如對于幾何路網(wǎng)來說脐雪,可以取兩節(jié)點間曼哈頓距離做為距離估計厌小,即f=g(n) + (abs(dx - nx) + abs(dy - ny));這樣估價函數(shù)f(n)在g(n)一定的情況下战秋,會或多或少的受距離估計值h(n)的制約璧亚,節(jié)點距目標點近,h值小脂信,f值相對就小癣蟋,能保證最短路的搜索向終點的方向進行。

算法實現(xiàn)(路徑搜索)
??接下來狰闪,我們用上面的方法寫一個簡單的應(yīng)用例子疯搅,實現(xiàn)下圖的搜索功能。

??先建立網(wǎng)格的css

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<style>
  * {
    margin: 0;
    padding: 0;
  }
  li {
    list-style: none;
  }
  #ul {
    height: auto;
    overflow: hidden;
    margin: 20px auto;
    border: 1px #000 solid;
    border-bottom: none;
    border-right: none;
  }
  #ul li {
    border: 1px #000 solid;
    border-top: none;
    border-left: none;
    float: left;
  }
  #ul li.sty1 {
    background-color: red;
  }
  #ul li.sty2 {
    background-color: green;
  }
  #ul li.sty3 {
    background-color: blue;
  }
  #input {
    width: 100px;
    position: absolute;
    left: 50%;
    margin-left: -50px;
  }
</style>
<body>
<ul id="ul"></ul>
<input type="button" value="開始尋路" id="input">
</body>
</html>

??在script中寫入map埋泵,然后繪制網(wǎng)格

 let map  = [
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,
    0,0,0,1,0,0,0,0,3,3,3,3,3,3,3,0,0,0,0,0,
    0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,3,0,3,3,3,3,3,0,0,0,0,0,
    0,0,0,0,0,0,0,0,3,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,2,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
  ]
  let oUl = document.getElementById('ul')
  let aLi = oUl.getElementsByTagName('li')
  let oInput = document.getElementById('input')
  let beginLi = oUl.getElementsByClassName('sty1') // 開始點
  let endLi = oUl.getElementsByClassName('sty2') // 結(jié)束點
  let cols = Math.sqrt(map.length)  // 行數(shù)
  let sizeGird = 20 // 表格寬度
  function createMap() {
    oUl.style.width = cols * (sizeGird + 1) + 1 + 'px'
    for (let i = 0; i < map.length; i++) {
      let oLi = document.createElement('li')
      oLi.style.width = sizeGird + 'px'
      oLi.style.height = sizeGird + 'px'
      oUl.appendChild(oLi)
      if (map[i] === 1) {
        oLi.className = 'sty1'
      } else if (map[i] ===2) {
        oLi.className = 'sty2'
      } else if (map[i] ===3) {
        oLi.className = 'sty3'
      }
    }
  }
  createMap()

??編寫估價算法

function f(nodeLi) {
  return g(nodeLi) + h(nodeLi)
}
function g(nodeLi) {
  let a = beginLi[0].offsetLeft - nodeLi.offsetLeft
  let b = beginLi[0].offsetTop - nodeLi.offsetTop
  return Math.sqrt(a*a + b*b)
}
function h(nodeLi) {
    let a = endLi[0].offsetLeft - nodeLi.offsetLeft
    let b = endLi[0].offsetTop - nodeLi.offsetTop
    return Math.sqrt(a*a + b*b)
}

??做兩個數(shù)組幔欧,openArr儲存已選擇的路徑(下一步將不會走這些路徑)、closeArr 儲存不可選的路徑

let openArr = []
let closeArr = []

??初始的openArr就是圖上的紅方塊丽声,初始的closeArr是藍方塊礁蔗。可選擇的路徑result是當前路徑元素周邊的8個黃色的方塊雁社,查找過程用findLi函數(shù)實現(xiàn)浴井。

function findLi(nowLi) {
    let result = []
    for (let i = 0; i < aLi.length; i++) {
        if (filter(aLi[i])) {
            result.push(aLi[i])
        }
    }
    function filter(li) {
      for (let i = 0; i < closeArr.length; i++) {
          if (closeArr[i] == li) {
              return false
          }
      }
      for (let i = 0; i < openArr.length; i++) {
          if (openArr[i] == li) {
              return false
          }
      }
      return true
    }
    for (let i = 0; i < result.length; i++) {
        if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= (sizeGird + 1)) && (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 1)) {
            openArr.push(result[i])
        }
    }
}

??通過上面的方法,我們已經(jīng)可以找到當前路徑元素的下一步可選路徑霉撵,共有8種選擇磺浙,接下來就是如何從這8種選擇選下步?這里我們選擇估價最小為下一路徑元素徒坡。

function openFn() {
    let nowLi = openArr.shift()
    if (nowLi == endLi[0]) {
        return ;
    }
    closeFn(nowLi)
    findLi(nowLi)
    openArr.sort(function(li1, li2) {
      return li1.num - li2.num
    })
    openFn()
}

??這里我們用排序的方式找到估價最小的路徑元素撕氧,需要把計算的估價掛載到該路徑元素上,對findLi方法進行改造喇完,

 if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= (sizeGird + 1)) && (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 1)) {
            result[i].num = f(result[i])
            openArr.push(result[i])
        }

??上面的方法呵曹,已經(jīng)實現(xiàn)了路徑的搜索,接下來我們再做一些操作,把搜索過程展示出來奄喂。
??該搜索過程的全部信息就存儲在closeArr數(shù)組铐殃,就是上圖中標出的不可選路徑的第二部分。但由于障礙物藍色方塊的存在跨新,closeArr的路徑可能會很長富腊,想要清晰的展示出搜索過程,展示closeArr不是好方法域帐。
??我們可以利用回溯赘被,closeArr的最后一位是目標點,由目標點回溯到上一步路徑元素肖揣,然后由該路徑元素回溯到它的上一步路徑元素民假,直到回溯到起始點,該回溯過程就可以表示搜索過程龙优。
??我們再次對findLi方法進行改造羊异,掛載回溯用的的上一步路徑元素。

if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= (sizeGird + 1)) && (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 1)) {
            result[i].num = f(result[i])
            result[i].parent = nowLi
            openArr.push(result[i])
        }

??最后寫一個showLine方法彤断,用于展示該回溯過程野舶。

function showLine() {
    let result =  []
    let lastLi = closeArr.pop()
    let isNow = 0
    findParent(lastLi)
    function findParent(li) {
        result.unshift(li)
        if (li.parent == beginLi[0]) {
            return ;
        }
        findParent(li.parent)
    }
    let timer = setInterval(function() {
      result[isNow].style.background = 'red'
      isNow++
      if(isNow == result.length) {
          clearInterval(timer)
      }
    }, 500)
}

??好的,這樣我們就完成整個搜索過程宰衙。

完整代碼如下:

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<style>
* {
margin: 0;
padding: 0;
}
li {
list-style: none;
}
#ul {
height: auto;
overflow: hidden;
margin: 20px auto;
border: 1px #000 solid;
border-bottom: none;
border-right: none;
}
#ul li {
border: 1px #000 solid;
border-top: none;
border-left: none;
float: left;
}
#ul li.sty1 {
background-color: red;
}
#ul li.sty2 {
background-color: green;
}
#ul li.sty3 {
background-color: blue;
}
#input {
width: 100px;
position: absolute;
left: 50%;
margin-left: -50px;
}
</style>
<body>
<ul id="ul"></ul>
<input type="button" value="開始尋路" id="input">
</body>
<script >
let oUl = document.getElementById('ul')
let aLi = oUl.getElementsByTagName('li')
let oInput = document.getElementById('input')
let beginLi = oUl.getElementsByClassName('sty1')
let endLi = oUl.getElementsByClassName('sty2')

let map  = [
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,3,3,3,3,3,3,3,3,0,0,0,0,0,
    0,0,0,0,0,0,0,3,3,3,3,3,3,3,3,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,
    0,0,0,1,0,0,0,0,3,3,3,3,3,3,3,0,0,0,0,0,
    0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,3,0,3,3,3,3,3,0,0,0,0,0,
    0,0,0,0,0,0,0,0,3,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,2,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
]

let cols = Math.sqrt(map.length)
let sizeGird = 20
let openArr = []
let closeArr = []

init ()
function init() {
  createMap()
  oInput.onclick = function() {
    openFn()
  }
}

function createMap() {
    oUl.style.width = cols * ( sizeGird + 1 ) + 1 + 'px'
  for (let i = 0; i < map.length; i++) {
      let oLi = document.createElement('li')
      oLi.style.width = sizeGird + 'px'
      oLi.style.height = sizeGird + 'px'
      oUl.appendChild(oLi)
      if (map[i] === 1) {
          oLi.className = 'sty1'
          openArr.push(oLi)
      } else if (map[i] ===2) {
          oLi.className = 'sty2'
      } else if (map[i] ===3) {
          oLi.className = 'sty3'
          closeArr.push(oLi)
      }
 }
}

function f(nodeLi) {
    return g(nodeLi) + h(nodeLi)
}
function g(nodeLi) {
    let a = beginLi[0].offsetLeft - nodeLi.offsetLeft
    let b = beginLi[0].offsetTop - nodeLi.offsetTop
    return Math.sqrt(a*a + b*b)
}
function h(nodeLi) {
    let a = endLi[0].offsetLeft - nodeLi.offsetLeft
    let b = endLi[0].offsetTop - nodeLi.offsetTop
    return Math.sqrt(a*a + b*b)
}

function openFn() {
    let nowLi = openArr.shift()
    if (nowLi == endLi[0]) {
        showLine()
        return ;
    }
    closeFn(nowLi)
    findLi(nowLi)
    openArr.sort(function(li1, li2) {
      return li1.num - li2.num
    })
    openFn()
}
function closeFn(nowLi) {
  closeArr.push(nowLi)
}
function findLi(nowLi) {
    let result = []
    for (let i = 0; i < aLi.length; i++) {
        if (filter(aLi[i])) {
            result.push(aLi[i])
        }
    }
          function filter(li) {
              for (let i = 0; i < closeArr.length; i++) {
                  if (closeArr[i] == li) {
                      return false
                  }
      }
      for (let i = 0; i < openArr.length; i++) {
          if (openArr[i] == li) {
              return false
          }
      }
      return true
    }
    for (let i = 0; i < result.length; i++) {
        if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= (sizeGird + 1)) && (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 1)) {
            result[i].num = f(result[i])
            result[i].parent = nowLi
            openArr.push(result[i])
        }
    }
}

function showLine() {
    let result =  []
    let lastLi = closeArr.pop()
    console.log(lastLi)
    let isNow = 0
    findParent(lastLi)
    function findParent(li) {
        result.unshift(li)
        if (li.parent == beginLi[0]) {
            return ;
        }
        findParent(li.parent)
    }
    let timer = setInterval(function() {
      result[isNow].style.background = 'red'
      isNow++
      if(isNow == result.length) {
          clearInterval(timer)
      }
    }, 500)
}
</script>
</html>
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末平道,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子供炼,更是在濱河造成了極大的恐慌一屋,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,042評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件袋哼,死亡現(xiàn)場離奇詭異冀墨,居然都是意外死亡,警方通過查閱死者的電腦和手機先嬉,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,996評論 2 384
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來楚堤,“玉大人疫蔓,你說我怎么就攤上這事∩矶” “怎么了衅胀?”我有些...
    開封第一講書人閱讀 156,674評論 0 345
  • 文/不壞的土叔 我叫張陵,是天一觀的道長酥筝。 經(jīng)常有香客問我滚躯,道長,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,340評論 1 283
  • 正文 為了忘掉前任掸掏,我火速辦了婚禮茁影,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘丧凤。我一直安慰自己募闲,他們只是感情好,可當我...
    茶點故事閱讀 65,404評論 5 384
  • 文/花漫 我一把揭開白布愿待。 她就那樣靜靜地躺著浩螺,像睡著了一般。 火紅的嫁衣襯著肌膚如雪仍侥。 梳的紋絲不亂的頭發(fā)上要出,一...
    開封第一講書人閱讀 49,749評論 1 289
  • 那天,我揣著相機與錄音农渊,去河邊找鬼患蹂。 笑死,一個胖子當著我的面吹牛腿时,可吹牛的內(nèi)容都是我干的况脆。 我是一名探鬼主播,決...
    沈念sama閱讀 38,902評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼批糟,長吁一口氣:“原來是場噩夢啊……” “哼格了!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起徽鼎,我...
    開封第一講書人閱讀 37,662評論 0 266
  • 序言:老撾萬榮一對情侶失蹤盛末,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后否淤,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體悄但,經(jīng)...
    沈念sama閱讀 44,110評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,451評論 2 325
  • 正文 我和宋清朗相戀三年石抡,在試婚紗的時候發(fā)現(xiàn)自己被綠了檐嚣。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,577評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡啰扛,死狀恐怖嚎京,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情隐解,我是刑警寧澤鞍帝,帶...
    沈念sama閱讀 34,258評論 4 328
  • 正文 年R本政府宣布,位于F島的核電站煞茫,受9級特大地震影響帕涌,放射性物質(zhì)發(fā)生泄漏摄凡。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,848評論 3 312
  • 文/蒙蒙 一蚓曼、第九天 我趴在偏房一處隱蔽的房頂上張望亲澡。 院中可真熱鬧,春花似錦辟躏、人聲如沸谷扣。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,726評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽会涎。三九已至,卻和暖如春瑞凑,著一層夾襖步出監(jiān)牢的瞬間末秃,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,952評論 1 264
  • 我被黑心中介騙來泰國打工籽御, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留练慕,地道東北人。 一個月前我還...
    沈念sama閱讀 46,271評論 2 360
  • 正文 我出身青樓技掏,卻偏偏與公主長得像铃将,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子哑梳,可洞房花燭夜當晚...
    茶點故事閱讀 43,452評論 2 348

推薦閱讀更多精彩內(nèi)容