网页制作相关网站,艾奇视觉网站建设,邯郸匿豪网络科技有限公司,北京比较好的网站公司一、如何实现两点间路径导航
导航实现的通用步骤#xff0c;一般是#xff1a; 1、网格划分 将地图划分为网格#xff0c;即例如地图是一张图片#xff0c;其像素为1000*1000#xff0c;那我们将此图片划分为各个10*10的网格#xff0c;从而提高寻路算法的计算量。 2、标…一、如何实现两点间路径导航
导航实现的通用步骤一般是 1、网格划分 将地图划分为网格即例如地图是一张图片其像素为1000*1000那我们将此图片划分为各个10*10的网格从而提高寻路算法的计算量。 2、标记障碍物 把地图划分的网格用一个二位数组存储若此网格中有障碍物则标记为1若可通行则标记为0例如[[0],[1]]。 3、将网格简化为路径节点此步可省 之前是基于网格进行路径计算但为了减少A*算法的计算量可以将网格地图简化为“路标形式”这种方法通常通过提取关键节点并构建稀疏图代替密集的网格图来实现。 4、使用A*算法寻找最短路径
二、A*A-Star寻路算法 A*寻路算法是一种用于路径规划的经典算法广泛应用于游戏开发、机器人导航和地图路径计算等领域。它是一种基于图搜索的启发式算法可以高效地在网格或节点图中找到从起点到终点的最短路径或代价最低路径。 1、算法核心如何搜索最短路径
A*算法通过综合考虑两方面的代价来进行路径搜索
实际代价G从起点到当前节点的实际路径代价。估计代价H从当前节点到终点的启发式估计代价通常采用欧几里得距离、曼哈顿距离等方法。总代价FF G H即从起点经过当前节点到终点的总估计代价。 2、算法步骤 初始 将起点加入“打开列表”待处理的节点列表。“关闭列表”为空已处理的节点列表。 搜索 重复以下步骤直到找到终点或打开列表为空 从打开列表中选择 F 值最小的节点作为当前节点。如果当前节点是终点路径找到结束。否则将当前节点从打开列表移至关闭列表。对当前节点的所有邻居节点 如果邻居在关闭列表中跳过。如果邻居不可通行障碍物跳过。如果邻居不在打开列表中计算其 F 值设置父节点为当前节点并加入打开列表。如果邻居已在打开列表中检查是否可以通过当前节点降低 G 值若可以更新其 F 值和父节点。 路径回溯 如果找到终点通过父节点逐步回溯得到路径。 3、启发函数的选择
启发函数是 A* 的关键。常用的启发函数有
曼哈顿距离适合网格地图不能斜走时使用欧几里得距离适合允许对角线走法的地图对角线距离适合允许斜走但代价固定的地图
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);
