美文网首页
用JavaScript实现A*算法

用JavaScript实现A*算法

作者: 小小的开发人员 | 来源:发表于2019-05-09 18:13 被阅读0次

  A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。

核心思想
  公式： f(n) = g(n) + h(n)
  其中， f(n) 是从初始状态经由状态n到目标状态的代价估计，g(n) 是在状态空间中从初始状态到状态n的实际代价，h(n) 是从状态n到目标状态的最佳路径的估计代价，保证找到最短路径(最优解的)条件，关键在于估价函数f(n)的选取（或者说h(n)的选取）。

距离估计与实际值越接近，估价函数取得就越好
  例如对于几何路网来说，可以取两节点间曼哈顿距离做为距离估计，即f=g(n) + (abs(dx - nx) + abs(dy - ny))；这样估价函数f(n)在g(n)一定的情况下，会或多或少的受距离估计值h(n)的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。

算法实现（路径搜索）
  接下来，我们用上面的方法写一个简单的应用例子，实现下图的搜索功能。

  先建立网格的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，然后绘制网格

 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') // 结束点
  let cols = Math.sqrt(map.length)  // 行数
  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)
}

  做两个数组，openArr储存已选择的路径（下一步将不会走这些路径）、closeArr 储存不可选的路径

let openArr = []
let closeArr = []

  初始的openArr就是图上的红方块，初始的closeArr是蓝方块。可选择的路径result是当前路径元素周边的8个黄色的方块，查找过程用findLi函数实现。

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])
        }
    }
}

  通过上面的方法，我们已经可以找到当前路径元素的下一步可选路径，共有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])
        }

  上面的方法，已经实现了路径的搜索，接下来我们再做一些操作，把搜索过程展示出来。
  该搜索过程的全部信息就存储在closeArr数组，就是上图中标出的不可选路径的第二部分。但由于障碍物蓝色方块的存在，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>

相关文章

网友评论

      本文标题：用JavaScript实现A*算法

      本文链接：https://www.haomeiwen.com/subject/idegoqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|用JavaScript实现A*算法|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！