Astar算法基础使用——寻路-一一网

技术栈

html
javascript
css
astar.js

准备工作

文件目录结构

第一步先用js循环绘制出 10*10的方格

// 初始化地图
let w = h = 40
function createMap () {
  const mapDom = document.querySelector("#map")
  for (let i = 0; i < 10; i++) {
    var ul = document.createElement('ul');
    mapDom.appendChild(ul)
    for (let j = 0; j < 10; j++) {
      var li = document.createElement('li');
      ul.appendChild(li)
      li.innerHTML = i + ',' + j
      li.style.left = i * w + 'px'
      li.style.top = j * h + 'px'
    }
  }
}
createMap()
复制代码

设置随机可行走点

每一个方格都有自己的坐标点，既然要做一个寻路的功能，那就需要一下几个元素，1.起点，2.终点，3.可行走的点，起点可以标注为(0,0)，终点可以标注为(9,9)，中间随机分布一些可行走的点，那么将上面的循环改造一下，要得出一个二维数组，由0，1组成，1为可行走的位置，0为不可行走的位置，用不同的颜色标注，每一个1对应猛男色的方块，每个0对应空白方块，万丈深渊

(后补的一张图)

这时候循环被改造为这样

// 初始化地图
let w = h = 40
const mapArr = []
function createMap () {
  // 获取地图容器
  const mapDom = document.querySelector("#map")
  // 第一层循环
  for (let i = 0; i < 10; i++) {
    let arr = []
    // 将第一层循环的数组加入到map数组中
    mapArr.push(arr)
    // 创建ul
    var ul = document.createElement('ul');
    ul.style.display = 'flex'
    mapDom.appendChild(ul)
    // 第二层循环
    for (let j = 0; j < 10; j++) {
      var li = document.createElement('li');
      const num = getRandom(1, 6)
      if (num > 2) {
        arr.push(1)
        li.style.background = '#ffd9cd'
      } else {
        arr.push(0)
      }
      // 起点和终点始终为可行走
      if(i===0&&j===0 || i===9&&j===9) {
        mapArr[i][j] = 1
        li.style.background = '#ffd9cd'
      }
      ul.appendChild(li)
      li.style.left = j * w + 'px'
      li.style.top = i * h + 'px'
      // 设置一个坐标属性，方便之后查找
      li.setAttribute('coordinate', i + ',' + j)
    }
  }
}
// 生成两个整数之间的随机整数
function getRandom (max, min) {
  return Math.floor(Math.random() * (max - min + 1) + min);
}
createMap()
复制代码

如果手动标记可行走路线，将粉色方块用线连起来

具体案例迷宫游戏的充值VIP

现在我们有了一个二维数组，里面有一堆可行走的点，还有一个起点(0,0)，终点(9,9)，那现在要做的就是引入astar 算法

<script src="./js/astar.js"></script>
复制代码

使用算法工具

稍微看一下astar源码

gridIn字段为二维数组字段，diagonal选项确定是否可走对角线 this.diagonal = !!options.diagonal; 不填为false

先调用一下Graph方法

// 计算路径 astar算法
function astarCreate (star, end, graph) {
  var maps = new Graph(graph);
  console.log(maps)
}
复制代码

astarCreate([0,0], [9,9], mapArr)
复制代码

打印出来的maps：

grid输出的是二维GridNode节点，nodes输出的是平铺的节点

接下来用到search方法

通过起点终点和刚才new graph返回的gridnode节点，计算出可行走路线，如果指定没返回，则没有从起点到终点的路径

// 计算路径 astar算法
function astarCreate (star, end, graph) {
  var maps = new Graph(graph);
  var starPosition = maps.grid[star[0]][star[1]];
  var endPosition = maps.grid[end[0]][end[1]];
  var result = astar.search(maps, starPosition, endPosition);
  console.log('result', result)
}
复制代码

这是没有可到路线的情况

因为对角线的属性没设置为true

result有值说明有可行走路线，画的可能不是返回的值

将可行走点标记出来

targDom(result)

function targDom(result){
  for(let i=0; i<result.length; i++) {
    const x = result[i].x
    const y = result[i].y
    const coordinate = x + ',' + y
    console.log(coordinate)
  }
}

复制代码

让元素动起来

function targDom (result) {
  for (let i = 0; i < result.length - 1; i++) {
    const x = result[i].x
    const y = result[i].y
    const coordinate = x + ',' + y
    // 通过之前设置的coordinate属性寻找具体的dom
    const dom = document.querySelector(`[coordinate^='${coordinate}']`)
    if (dom) {
      dom.style.background = '#FFEB3B' // 修改dom节点的背景色
      setTimeout(() => {
        moveImg(x, y, i === result.length - 2)
      }, 200 * i)
    }
  }
}

// 让图片动起来
function moveImg (t, l, last) {
  const img = document.querySelector('#first-li')
  if (img) {
    img.style.left = l * w + 'px'
    img.style.top = t * h + 'px'
    // 判断是否为最后一个，最后一个要滑到终点去
    if (last) {
      setTimeout(() => {
        img.style.left = 9 * w + 'px'
        img.style.top = 9 * h + 'px'
      }, 300)
    }
  }
}
复制代码