Using a* heuristic search to solve maze routing problem

Preface

One 、a+ What is heuristic search ？

  Use the formula :f=g+h

Two 、js Code complete solution , Detailed instructions

1、 maze ：# Represents a wall ,. I can go ,a The starting point ,b End point , Mark the starting point by yourself a End b

2、 Output all shortest paths

3、 Code

---

Preface

utilize a+ Heuristic search solves the maze problem

Experience the maze and dynamically generate websites : Maze to find the way -a* Algorithm

---

One 、a+ What is heuristic search ？

See another blogger's blog :

A Detailed explanation of star algorithm ( Personally, I think it is the most detailed , The most accessible version )_Colin My blog -CSDN Blog _a Star algorithm A* The original address of the pathfinding algorithm ：http://www.gamedev.net/reference/articles/article2003.asp Although I have mastered the overview A* The algorithmists think it's easy , But for beginners ,A* The algorithm is still very complicated . Search area (The Search Area) Let's assume that someone is going to start from A Point to move to B spot , But the two points are separated by a wall . Pictured 1, Green is A, Red is Bhttps://blog.csdn.net/hitwhylz/article/details/23089415

Use the formula :f=g+h

f： The total cost value from the starting point to the current node , The smaller the better. , Values for g+h

g： The actual cost value from the starting point to the current node , The smaller the better. , Generally, set the weight , Go up, down, left and right every time +10

h： The pre search cost value from the current node to the destination , Do not consider the existence of obstructions , Manhattan distance is generally used
       Calculate the horizontal and vertical distance between two points and , such as ： At present (0,0), End (4,4), be h=4+4=8

Two 、js Code complete solution , Detailed instructions

1、 maze ：# Represents a wall ,. I can go ,a The starting point ,b End point , Mark the starting point by yourself a End b

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

2、 Output all shortest paths ( The walking angle is the shortest , It will also output the shortest case of no skew angle )

3、 Code

// Set up a maze 

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

// initialization 
let openlist = [];// Queue to be searched 
let closelist = [];// Searched and wall queue 
let start;// The starting position , With [x,y, Parent node ,g,h,f] Express , In the maze a It's about 
let end;// End position , In the maze b It's about 

// Initialize adding walls closelist queue 
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]
    }
  }
}



// Generate node functions , Core computing ：f=g+h
function node(x, y, p, g, h) {
  let f = g + h;
  return [x, y, p, g, h, f];
}

// Manhattan distance calculation , That is to calculate the sum of the horizontal and vertical distance between two points , Do not consider walls , Is to estimate the distance 
function mhd(x1, y1, x2, y2) {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

// Diffusion search function 【 Value calculation and judgment in all directions , The weight of up, down, left and right is 10, Join the queue to be searched 】
function ks(arr = [0, 0, 0, 0, 0, 0]) {
  let [x, y, p, g, h, f] = arr;
  // Set the current node as the parent node 
  let pp = arr;

  // Go down , If it exists, it will g+10, Join the queue to be searched 
  if (
    x + 1 < n &&
    !ph([x + 1, y], closelist)
  ) {
    openlist.push(node(x + 1, y, pp, g + 10, mhd(x + 1, y, ...end)));
  }
  // Go up , If it exists, it will g+10, Join the queue to be searched 
  if (
    x - 1 >= 0 &&
    !ph([x - 1, y], closelist)
  ) {
    openlist.push(node(x - 1, y, pp, g + 10, mhd(x - 1, y, ...end)));
  }
  // turn right , If it exists, it will g+10, Join the queue to be searched 
  if (
    y + 1 < m &&
    !ph([x, y + 1], closelist)
  ) {
    openlist.push(node(x, y + 1, pp, g + 10, mhd(x, y + 1, ...end)));
  }
  // turn left , If it exists, it will g+10, Join the queue to be searched 
  if (
    y - 1 >= 0 &&
    !ph([x, y - 1], closelist)
  ) {
    openlist.push(node(x, y - 1, pp, g + 10, mhd(x, y - 1, ...end)));
  }


  // Go to the upper left corner , If it exists, it will g+14, Join the queue to be searched , Because it's an oblique angle , Pythagorean theorem root 2 About equal to 
  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)));
  }

  // Go to the lower left corner , If it exists, it will g+14, Join the queue to be searched 
  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)));
  }

  // Go down the right corner , If it exists, it will g+14, Join the queue to be searched 
  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)));
  }
  // Go to the upper right corner , If it exists, it will g+14, Join the queue to be searched 
  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 beyond the scope of the maze , It means that the road is blocked , Join the queue to be searched for identification and backtracking 
  if (x + 1 > n || y + 1 > m) {
    openlist.push([-1, -1, -1, -1, -1, -1]);
  }

}

// Judge whether the current node is closelist In line , If yes, skip 
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;
}




// Every collection except the current smallest f There are all other unused nodes besides the nodes of 
let stk = [start]
// Path set 
let path = [];
// Begin your search 
try {
  while (stk.length > 0) {
    // Add the starting point to the queue to be searched 
    openlist.push(stk.shift());
    while (1) {
      // To search the queue, press f Value size sort 
      openlist.sort((a, b) => a[5] - b[5]);
      // Take out the current openlist Exclude from f The same smallest node 
      let cur = openlist.shift();
      // Collect the smallest f All other unused nodes except the node of , Press f sorted , In order to find the way again when the road is blocked 
      stk = [...new Set([...stk, ...openlist].sort((a, b) => a[5] - b[5]))];

      // Judge whether it can get through in the end , If the current node returns -1, It doesn't work , take out stk Search again for the minimum value of 
      //console.log(cur)
      if (cur[0] === -1) {
        if (stk.length === 0) break
        cur = stk.shift()
        // Reset search results , Filtering is better than current cur Of f Big nodes , Find a new way 
        closelist = closelist.filter(e => e[5] < cur[5])
        continue
      }

      // If it's a normal node , Put the current node into the searched queue 
      closelist.push(cur);

      // Judge whether the current node is the destination , If it's not the key point, use the diffusion search function to spread openlist
      if (cur[0] === end[0] && cur[1] === end[1]) break;
      ks(cur);
    }
    // Take out the last key node , Because every node contains a parent node ( Last node , Cycle through the parent node until the parent node is 0)
    // The parent node of the initial node is set to 0 In order to judge 
    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(' Shortest path ：' + path[0].length + ' Step ')
    // Because the node is pushed back from the end to find the starting point , So flip the path order 
    path.map(e => e.reverse()).forEach((e, i) => {
      console.log(' route ' + (i + 1) + ':' + e.map(e => `(${e[0]},${e[1]})`).join('->'))
    })
  } else {
    console.log(' Pathfinding failed, please check ！')
  }

} catch (err) {

  if (path.length > 0) {
    console.log(' Shortest path ：' + path[0].length + ' Step ')
    // Because the node is pushed back from the end to find the starting point , So flip the path order 
    path.map(e => e.reverse()).forEach((e, i) => {
      console.log(' route ' + (i + 1) + ':' + e.map(e => `(${e[0]},${e[1]})`).join('->'))
    })
  } else {
    console.log(' Pathfinding failed, please check ！')
  }
}