JS实现高效导航——A*寻路算法+导航图简化法

一、如何实现两点间路径导航

导航实现的通用步骤，一般是：

        1、网格划分

        将地图划分为网格，即例如地图是一张图片，其像素为1000*1000，那我们将此图片划分为各个10*10的网格，从而提高寻路算法的计算量。

         2、标记障碍物

        把地图划分的网格用一个二位数组存储，若此网格中有障碍物则标记为1，若可通行则标记为0，例如[[0],[1]]。

       3、将网格简化为路径节点（此步可省）

       之前是基于网格进行路径计算，但为了减少A*算法的计算量，可以将网格地图简化为“路标形式”，这种方法通常通过提取关键节点并构建稀疏图代替密集的网格图来实现。

       4、使用A*算法寻找最短路径       

二、A*（A-Star）寻路算法

        A*寻路算法是一种用于路径规划的经典算法，广泛应用于游戏开发、机器人导航和地图路径计算等领域。它是一种基于图搜索的启发式算法，可以高效地在网格或节点图中找到从起点到终点的最短路径（或代价最低路径）。

---

1、算法核心：如何搜索最短路径

A*算法通过综合考虑两方面的代价来进行路径搜索：

1. 实际代价（G）：从起点到当前节点的实际路径代价。
2. 估计代价（H）：从当前节点到终点的启发式估计代价，通常采用欧几里得距离、曼哈顿距离等方法。
3. 总代价（F）：F = G + H，即从起点经过当前节点，到终点的总估计代价。

2、算法步骤

1. 初始

   • 将起点加入“打开列表”（待处理的节点列表）。
   • “关闭列表”为空（已处理的节点列表）。

2. 搜索
   重复以下步骤，直到找到终点或打开列表为空：

   • 从打开列表中选择 F 值最小的节点作为当前节点。
   • 如果当前节点是终点，路径找到，结束。
   • 否则，将当前节点从打开列表移至关闭列表。
   • 对当前节点的所有邻居节点：
     • 如果邻居在关闭列表中，跳过。
     • 如果邻居不可通行（障碍物），跳过。
     • 如果邻居不在打开列表中，计算其 F 值，设置父节点为当前节点，并加入打开列表。
     • 如果邻居已在打开列表中，检查是否可以通过当前节点降低 G 值；若可以，更新其 F 值和父节点。

3. 路径回溯
   如果找到终点，通过父节点逐步回溯，得到路径。

3、启发函数的选择

启发函数是 A* 的关键。常用的启发函数有：

1. 曼哈顿距离（适合网格地图，不能斜走时使用）
2. 欧几里得距离（适合允许对角线走法的地图）
3. 对角线距离（适合允许斜走但代价固定的地图）

4、JS实现A*算法

        以下是js实现A*算法的实例代码，其中启发函数选用的是曼哈顿距离（计算最快），可根据自己的需求改为其他启发函数。

function aStar(grid, start, end) {// 初始化打开列表和关闭列表let openList = [];let closedList = [];// 将起点加入打开列表openList.push(start);while (openList.length > 0) {// 找到 F 值最小的节点let current = openList.reduce((a, b) => (a.f < b.f ? a : b));// 如果当前节点是终点，回溯路径if (current.x === end.x && current.y === end.y) {let path = [];while (current) {path.push([current.x, current.y]);current = current.parent;}return path.reverse();}// 从打开列表中移除当前节点，加入关闭列表openList = openList.filter((node) => node !== current);closedList.push(current);// 遍历当前节点的邻居for (let neighbor of getNeighbors(grid, current)) {if (closedList.includes(neighbor) || !neighbor.walkable) continue;let tentativeG = current.g + 1;if (!openList.includes(neighbor) || tentativeG < neighbor.g) {neighbor.g = tentativeG;neighbor.h = heuristic(neighbor, end);neighbor.f = neighbor.g + neighbor.h;neighbor.parent = current;if (!openList.includes(neighbor)) openList.push(neighbor);}}}// 如果没有找到路径，返回空数组return [];
}// 获取邻居节点
function getNeighbors(grid, node) {const directions = [[0, -1], // 上[0, 1],  // 下[-1, 0], // 左[1, 0],  // 右];const neighbors = [];for (let [dx, dy] of directions) {let x = node.x + dx;let y = node.y + dy;if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {neighbors.push(grid[x][y]);}}return neighbors;
}// 启发函数（曼哈顿距离），可根据需要更换为其他函数
function heuristic(nodeA, nodeB) {return Math.abs(nodeA.x - nodeB.x) + Math.abs(nodeA.y - nodeB.y);
}

三、导航图简化法

        在路径规划问题中，将网格地图简化为“路标形式”是为了减少计算量，提高效率。这种方法通常通过提取关键节点并构建稀疏图代替密集的网格图来实现。以下是一些常见的简化方法和步骤：

1. 路标节点的选取原则

路标节点是网格地图上的关键点，用于有效表示地图的主要拓扑结构。以下是一些常见的选取原则：

• 交叉点：所有道路的交汇点，如十字路口或转角点。
• 障碍物的拐点：障碍物形状的关键点，确保路径规划能绕过障碍物。
• 终点和起点：直接包括起点和终点作为路标节点。
• 显著转弯点：路径上角度变化较大的点。

2. 网格地图到路标形式的转换方法

（1）稀疏图抽取

使用算法从网格地图中提取关键点并构建稀疏图：

• 人工标记法：手动标记地图上的关键点，用于简单地图。
• 自动生成法：
  • 凸壳算法：提取地图边界和障碍物轮廓上的拐点。
  • 关键点检测：利用角点检测算法（如Harris角点检测）自动提取转角和交汇点。

（2）可行通路的简化

在路标节点之间构建直接的可行通路，忽略网格之间的冗余信息：

• 连通性检测：检查两节点之间是否存在无障碍直线路径。
• 启发式距离：以欧几里得距离或其他度量方式标记路标之间的边权重。

（3）使用稀疏图代替网格图

构建的稀疏图通常存储为节点和边的列表形式：

• 节点：路标节点的集合。
• 边：表示两个路标节点之间的直达路径及其权重。

3. 路标简化的优点

• 计算效率更高：减少了需要遍历的节点数，尤其在大地图中效果显著。
• 内存占用减少：稀疏图比密集网格占用的存储空间更小。
• 直观性增强：路标形式便于可视化和理解。

4、JS代码

    将稀疏图作为A*算法的输入，替代网格。

//稀疏图
function simplifyToSparseGraph(grid) {const rows = grid.length;const cols = grid[0].length;// 辅助函数：判断是否为关键点function isKeyPoint(x, y) {if (grid[x][y] === 0) return false; // 障碍物不是关键点// 获取邻居点状态const neighbors = [grid[x - 1]?.[y], // 上grid[x + 1]?.[y], // 下grid[x]?.[y - 1], // 左grid[x]?.[y + 1], // 右];const walkableCount = neighbors.filter((n) => n === 1).length;// 判断是否为交叉点、拐角或终端点return walkableCount !== 2;}// 提取关键点const keyPoints = [];for (let x = 0; x < rows; x++) {for (let y = 0; y < cols; y++) {if (isKeyPoint(x, y)) {keyPoints.push({ x, y });}}}// 构建稀疏图：连通关键点const sparseGraph = {};for (let { x: x1, y: y1 } of keyPoints) {sparseGraph[`${x1},${y1}`] = [];for (let { x: x2, y: y2 } of keyPoints) {if (x1 === x2 && y1 === y2) continue; // 跳过自身if (isDirectlyConnected(grid, x1, y1, x2, y2)) {const distance = Math.abs(x1 - x2) + Math.abs(y1 - y2);sparseGraph[`${x1},${y1}`].push({ x: x2, y: y2, distance });}}}return { keyPoints, sparseGraph };
}// 判断两个点是否直接连通
function isDirectlyConnected(grid, x1, y1, x2, y2) {if (x1 !== x2 && y1 !== y2) return false; // 只考虑直线连通const [start, end] = x1 === x2 ? [y1, y2] : [x1, x2];const fixed = x1 === x2 ? x1 : y1;for (let i = Math.min(start, end) + 1; i < Math.max(start, end); i++) {const value = x1 === x2 ? grid[fixed][i] : grid[i][fixed];if (value !== 1) return false; // 遇到障碍物则不连通}return true;
}//对应修订后的A*算法
function aStarOnSparseGraph(sparseGraph, start, end) {const openList = [];const closedList = new Set();const gCosts = {};const fCosts = {};const parents = {};// 转换点为字符串键const startKey = `${start.x},${start.y}`;const endKey = `${end.x},${end.y}`;// 初始化起点gCosts[startKey] = 0;fCosts[startKey] = heuristic(start, end);openList.push({ key: startKey, fCost: fCosts[startKey] });while (openList.length > 0) {// 按 F 值排序，选取 F 值最小的节点openList.sort((a, b) => a.fCost - b.fCost);const current = openList.shift();const currentKey = current.key;// 如果当前节点是终点，回溯路径if (currentKey === endKey) {return reconstructPath(parents, startKey, endKey);}closedList.add(currentKey);// 遍历当前节点的邻居for (const neighbor of sparseGraph[currentKey]) {const neighborKey = `${neighbor.x},${neighbor.y}`;if (closedList.has(neighborKey)) continue;// 计算临时 G 值const tentativeG = gCosts[currentKey] + neighbor.distance;if (gCosts[neighborKey] === undefined || tentativeG < gCosts[neighborKey]) {// 更新 G 值和 F 值gCosts[neighborKey] = tentativeG;fCosts[neighborKey] = tentativeG + heuristic({ x: neighbor.x, y: neighbor.y }, end);parents[neighborKey] = currentKey;// 如果邻居不在 openList 中，加入 openListif (!openList.find((node) => node.key === neighborKey)) {openList.push({ key: neighborKey, fCost: fCosts[neighborKey] });}}}}// 如果找不到路径，返回空数组return [];
}// 启发函数：曼哈顿距离
function heuristic(nodeA, nodeB) {return Math.abs(nodeA.x - nodeB.x) + Math.abs(nodeA.y - nodeB.y);
}// 回溯路径
function reconstructPath(parents, startKey, endKey) {const path = [];let currentKey = endKey;while (currentKey !== startKey) {const [x, y] = currentKey.split(",").map(Number);path.push({ x, y });currentKey = parents[currentKey];}const [startX, startY] = startKey.split(",").map(Number);path.push({ x: startX, y: startY });return path.reverse();
}// 示例：网格地图
const grid = [[1, 1, 1, 0, 1],[1, 0, 1, 0, 1],[1, 1, 1, 1, 1],[0, 0, 1, 0, 1],[1, 1, 1, 0, 1],
];// 调用函数
const { keyPoints, sparseGraph } = simplifyToSparseGraph(grid);console.log("关键点:", keyPoints);
console.log("稀疏图:", sparseGraph);