js实现寻路算法

广度优先搜索（BFS）算法实现

BFS通过队列逐层扩展搜索，适合无权图的最短路径查找。以下为基于网格的BFS实现：

function bfs(grid, start, end) {
  const queue = [[start]];
  const visited = new Set([start.toString()]);
  const directions = [[-1,0], [1,0], [0,-1], [0,1]]; // 上下左右

  while (queue.length) {
    const path = queue.shift();
    const [x, y] = path[path.length-1];

    if (x === end[0] && y === end[1]) return path;

    for (const [dx, dy] of directions) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && ny >= 0 && 
          nx < grid.length && ny < grid[0].length &&
          !grid[nx][ny] && !visited.has([nx,ny].toString())) {
        visited.add([nx,ny].toString());
        queue.push([...path, [nx, ny]]);
      }
    }
  }
  return null; // 无路径
}

A* 算法实现

A*算法结合启发式函数和实际代价，适合带权图的优化搜索：

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 aStar(grid, start, end) {
  const openSet = new PriorityQueue();
  openSet.enqueue(start, 0);
  const cameFrom = {};
  const gScore = {[start]: 0};
  const fScore = {[start]: heuristic(start, end)};

  while (!openSet.isEmpty()) {
    const current = openSet.dequeue();
    if (current[0] === end[0] && current[1] === end[1]) 
      return reconstructPath(cameFrom, current);

    for (const [dx, dy] of [[-1,0], [1,0], [0,-1], [0,1]]) {
      const neighbor = [current[0]+dx, current[1]+dy];
      if (!isValid(grid, neighbor)) continue;

      const tentativeG = gScore[current] + 1;
      if (!(neighbor in gScore) || tentativeG < gScore[neighbor]) {
        cameFrom[neighbor] = current;
        gScore[neighbor] = tentativeG;
        fScore[neighbor] = tentativeG + heuristic(neighbor, end);
        openSet.enqueue(neighbor, fScore[neighbor]);
      }
    }
  }
  return null;
}

function heuristic(a, b) {
  return Math.abs(a[0]-b[0]) + Math.abs(a[1]-b[1]); // 曼哈顿距离
}

可视化实现建议

结合HTML5 Canvas实现路径可视化：

function drawPath(ctx, grid, path, cellSize = 20) {
  // 绘制网格
  grid.forEach((row, x) => {
    row.forEach((cell, y) => {
      ctx.fillStyle = cell ? '#000' : '#fff';
      ctx.fillRect(y*cellSize, x*cellSize, cellSize, cellSize);
    });
  });

  // 绘制路径
  ctx.strokeStyle = 'red';
  ctx.lineWidth = 2;
  ctx.beginPath();
  path.forEach(([x,y], i) => {
    if (i === 0) ctx.moveTo(y*cellSize+cellSize/2, x*cellSize+cellSize/2);
    else ctx.lineTo(y*cellSize+cellSize/2, x*cellSize+cellSize/2);
  });
  ctx.stroke();
}

性能优化技巧

使用TypedArray替代普通数组存储网格数据可提升性能。对于大规模地图，可采用分层路径查找（HPA*）或跳点搜索（JPS）等优化算法。

// 使用Uint8Array表示网格
const grid = new Uint8Array(rows * cols); 
grid[y * cols + x] = 1; // 设置障碍物

动态障碍物处理

实现动态障碍物需要引入重新规划机制：

function dynamicReplan(path, newObstacles) {
  const affected = path.some(([x,y]) => newObstacles.has(`${x},${y}`));
  if (affected) {
    const remainingPath = path.slice(0, path.findIndex(
      ([x,y]) => newObstacles.has(`${x},${y}`)));
    return aStar(grid, remainingPath[remainingPath.length-1], end);
  }
  return path;
}