利用a*启发式搜索解决迷宫寻路问题

前言

一、a+启发式搜索是什么？

 运用公式:f=g+h

二、js代码全解，详细说明

1、迷宫：#表示墙，.表示可走,a表示起点，b表示终点，自己随便标起点a终点b

2、输出所有最短路径

3、代码

---

前言

利用a+启发式搜索解决迷宫寻路问题

体验迷宫动态生成网站:迷宫寻路-a*算法

---

一、a+启发式搜索是什么？

见另一博主博文:

A星算法详解(个人认为最详细,最通俗易懂的一个版本)_Colin丶的博客-CSDN博客_a星算法A* 寻路算法原文地址：http://www.gamedev.net/reference/articles/article2003.asp概述虽然掌握了A*算法的人认为它容易，但是对于初学者来说，A*算法还是很复杂的。搜索区域(The Search Area)我们假设某人要从A点移动到B点，但是这两点之间被一堵墙隔开。如图1，绿色是A，红色是Bhttps://blog.csdn.net/hitwhylz/article/details/23089415

运用公式:f=g+h

f：从起点到当前节点的总花费价值，越小越好，数值为g+h

g：从起点到当前节点的实际花费价值，越小越好，一般设置权重，上下左右每走一次+10

h：当前节点到终点的预搜索花费价值，不考虑遮挡物的存在，一般用曼哈顿距离表示法
      计算两点之间水平竖直的距离和，比如：当前(0,0),终点(4,4)，则h=4+4=8

二、js代码全解，详细说明

1、迷宫：#表示墙，.表示可走,a表示起点，b表示终点，自己随便标起点a终点b

a . . . . # . . . 
. . . # . . b . .
. . # # . . # # .

2、输出所有最短路径(走斜角最短，也会输出不走斜角的最短情况)

3、代码

//设置迷宫

let maze = `
a . . . . # . . . 
. . . # . . b . .
. . # # . . # # .
`.slice(1, -1).split('\n').map(e => e.split(' '))
let [n, m] = [maze.length, maze[0].length]

//初始化
let openlist = [];//待搜索队列
let closelist = [];//已搜索及墙队列
let start;//起始位置,以[x，y，父节点，g,h,f]表示,迷宫中的a处
let end;//结束位置，迷宫中的b处

//初始化将墙加入closelist队列
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (maze[i][j] === '#') {
      closelist.push(node(i, j, null, 0, 0));
    }
    if (maze[i][j] === 'a') {
      start = [i, j, 0, 0, 0, 0]
    }
    if (maze[i][j] === 'b') {
      end = [i, j, 0, 0, 0, 0]
    }
  }
}



//生成节点函数，核心计算：f=g+h
function node(x, y, p, g, h) {
  let f = g + h;
  return [x, y, p, g, h, f];
}

//曼哈顿距离计算法，即计算两点之间水平竖直的距离和，不考虑墙，是估计距离
function mhd(x1, y1, x2, y2) {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

//扩散搜索函数【各方向价值计算判断，上下左右权重为10，加入待搜索队列】
function ks(arr = [0, 0, 0, 0, 0, 0]) {
  let [x, y, p, g, h, f] = arr;
  //将当前节点设置为父节点
  let pp = arr;

  //向下走，如果存在就g+10，加入待搜索队列
  if (
    x + 1 < n &&
    !ph([x + 1, y], closelist)
  ) {
    openlist.push(node(x + 1, y, pp, g + 10, mhd(x + 1, y, ...end)));
  }
  //向上走，如果存在就g+10，加入待搜索队列
  if (
    x - 1 >= 0 &&
    !ph([x - 1, y], closelist)
  ) {
    openlist.push(node(x - 1, y, pp, g + 10, mhd(x - 1, y, ...end)));
  }
  //向右走，如果存在就g+10，加入待搜索队列
  if (
    y + 1 < m &&
    !ph([x, y + 1], closelist)
  ) {
    openlist.push(node(x, y + 1, pp, g + 10, mhd(x, y + 1, ...end)));
  }
  //向左走，如果存在就g+10，加入待搜索队列
  if (
    y - 1 >= 0 &&
    !ph([x, y - 1], closelist)
  ) {
    openlist.push(node(x, y - 1, pp, g + 10, mhd(x, y - 1, ...end)));
  }


  //向左上角走，如果存在就g+14，加入待搜索队列,因为是斜角，勾股定理根号2约等于
  if (
    y - 1 >= 0 && x - 1 >= 0 &&
    !ph([x - 1, y - 1], closelist)
  ) {
    openlist.push(node(x - 1, y - 1, pp, g + 14, mhd(x - 1, y - 1, ...end)));
  }

  //向左下角走，如果存在就g+14，加入待搜索队列
  if (
    y - 1 >= 0 && x + 1 < n &&
    !ph([x + 1, y - 1], closelist)
  ) {
    openlist.push(node(x + 1, y - 1, pp, g + 14, mhd(x + 1, y - 1, ...end)));
  }

  //向右下角走，如果存在就g+14，加入待搜索队列
  if (
    y + 1 < m && x + 1 < n &&
    !ph([x + 1, y + 1], closelist)
  ) {
    openlist.push(node(x + 1, y + 1, pp, g + 14, mhd(x + 1, y + 1, ...end)));
  }
  //向右上角走，如果存在就g+14，加入待搜索队列
  if (
    y + 1 < m && x - 1 >= 0 &&
    !ph([x - 1, y + 1], closelist)
  ) {
    openlist.push(node(x - 1, y + 1, pp, g + 14, mhd(x - 1, y + 1, ...end)));
  }


  //如果超出迷宫范围，表示此路不通，加入待搜索队列进行识别回溯
  if (x + 1 > n || y + 1 > m) {
    openlist.push([-1, -1, -1, -1, -1, -1]);
  }

}

//判断当前节点在不在closelist队列中，如果在就跳过
function ph(arr1, arr2) {
  let fg = false;
  for (let x of arr2) {
    if (arr1[0] === x[0] && arr1[1] === x[1]) {
      fg = true;
      break;
    }
  }
  return fg;
}




//每次收集除了当前最小的f的节点之外是所有其他不用的节点
let stk = [start]
//路径集合
let path = [];
//开始搜索
try {
  while (stk.length > 0) {
    //将起点加入待搜索队列
    openlist.push(stk.shift());
    while (1) {
      //待搜索队列按f值大小排序
      openlist.sort((a, b) => a[5] - b[5]);
      //拿出当前openlist中排除f相同的最小的节点
      let cur = openlist.shift();
      //收集除了当前最小的f的节点之外的所有其他不用的节点，按f值排序,以便道路不通时重新寻路
      stk = [...new Set([...stk, ...openlist].sort((a, b) => a[5] - b[5]))];

      //判断最后能不能走通，如果当前节点返回-1，则走不通，拿出stk的最小值重新搜索
      //console.log(cur)
      if (cur[0] === -1) {
        if (stk.length === 0) break
        cur = stk.shift()
        //重置搜索结果，过滤比当前cur的f大的节点，重新寻路
        closelist = closelist.filter(e => e[5] < cur[5])
        continue
      }

      //如果是普通节点，把当前节点放入已搜索队列
      closelist.push(cur);

      //判断当前节点是不是终点，如果不是重点就用扩散搜索函数扩散openlist
      if (cur[0] === end[0] && cur[1] === end[1]) break;
      ks(cur);
    }
    //把最后一次到重点的节点拿出来，因为每个节点都包含父节点(上一个节点，循环取父节点直至父节点为0)
    //初始节点父节点设置成了0以便判断
    let res = closelist.slice(-1)[0];
    path.push([])
    while (true) {
      path[path.length - 1].push([res[0], res[1]]);
      if (!res[2]) break;
      res = res[2];
    }
  }

  if (path.length > 0) {
    console.log('最短路径：' + path[0].length + '步')
    //因为节点是从终点开始回推找到起点的，所以要翻转一下路径顺序
    path.map(e => e.reverse()).forEach((e, i) => {
      console.log('路径' + (i + 1) + ':' + e.map(e => `(${e[0]},${e[1]})`).join('->'))
    })
  } else {
    console.log('寻路失败请检查！')
  }

} catch (err) {

  if (path.length > 0) {
    console.log('最短路径：' + path[0].length + '步')
    //因为节点是从终点开始回推找到起点的，所以要翻转一下路径顺序
    path.map(e => e.reverse()).forEach((e, i) => {
      console.log('路径' + (i + 1) + ':' + e.map(e => `(${e[0]},${e[1]})`).join('->'))
    })
  } else {
    console.log('寻路失败请检查！')
  }
}