当前位置：首页 > JavaScript

js实现寻路算法

2026-03-01 17:26:49JavaScript

广度优先搜索（BFS）寻路算法

BFS通过逐层遍历相邻节点寻找最短路径，适合无权图或网格地图。

function bfsFindPath(grid, start, end) {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[-1,0],[1,0],[0,-1],[0,1]];
  const queue = [[start[0], start[1]]];
  const visited = Array(rows).fill().map(() => Array(cols).fill(false));
  const prev = Array(rows).fill().map(() => Array(cols).fill(null));

  visited[start[0]][start[1]] = true;

  while (queue.length) {
    const [x, y] = queue.shift();
    if (x === end[0] && y === end[1]) break;

    for (const [dx, dy] of directions) {
      const nx = x + dx, ny = y + dy;
      if (nx >=0 && nx < rows && ny >=0 && ny < cols 
          && !grid[nx][ny] && !visited[nx][ny]) {
        visited[nx][ny] = true;
        prev[nx][ny] = [x, y];
        queue.push([nx, ny]);
      }
    }
  }

  // 回溯路径
  const path = [];
  let [x, y] = end;
  while (prev[x][y]) {
    path.unshift([x, y]);
    [x, y] = prev[x][y];
  }
  return path.length ? [start, ...path] : null;
}

A* 寻路算法

A*算法结合了Dijkstra和启发式函数，适合带权图或复杂地形。

class PriorityQueue {
  constructor() {
    this.elements = [];
  }
  enqueue(element, priority) {
    this.elements.push({element, priority});
    this.elements.sort((a,b) => a.priority - b.priority);
  }
  dequeue() {
    return this.elements.shift().element;
  }
  isEmpty() {
    return !this.elements.length;
  }
}

function aStarFindPath(grid, start, end) {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[-1,0],[1,0],[0,-1],[0,1]];
  const heuristic = (x,y) => Math.abs(x-end[0]) + Math.abs(y-end[1]);

  const openSet = new PriorityQueue();
  openSet.enqueue([start[0], start[1]], 0);

  const gScore = Array(rows).fill().map(() => Array(cols).fill(Infinity));
  gScore[start[0]][start[1]] = 0;

  const fScore = Array(rows).fill().map(() => Array(cols).fill(Infinity));
  fScore[start[0]][start[1]] = heuristic(start[0], start[1]);

  const cameFrom = Array(rows).fill().map(() => Array(cols).fill(null));

  while (!openSet.isEmpty()) {
    const [x, y] = openSet.dequeue();
    if (x === end[0] && y === end[1]) {
      // 回溯路径
      const path = [[x, y]];
      let current = cameFrom[x][y];
      while (current) {
        path.unshift(current);
        current = cameFrom[current[0]][current[1]];
      }
      return path;
    }

    for (const [dx, dy] of directions) {
      const nx = x + dx, ny = y + dy;
      if (nx >=0 && nx < rows && ny >=0 && ny < cols && !grid[nx][ny]) {
        const tentativeG = gScore[x][y] + 1;
        if (tentativeG < gScore[nx][ny]) {
          cameFrom[nx][ny] = [x, y];
          gScore[nx][ny] = tentativeG;
          fScore[nx][ny] = tentativeG + heuristic(nx, ny);
          if (!openSet.elements.some(e => e.element[0]===nx && e.element[1]===ny)) {
            openSet.enqueue([nx, ny], fScore[nx][ny]);
          }
        }
      }
    }
  }
  return null; // 未找到路径
}

使用示例

// 0表示可通行，1表示障碍物
const grid = [
  [0,0,0,0,0],
  [0,1,1,1,0],
  [0,1,0,0,0],
  [0,1,0,1,0],
  [0,0,0,1,0]
];

const start = [0,0];
const end = [4,4];

console.log(bfsFindPath(grid, start, end));
console.log(aStarFindPath(grid, start, end));