# A星寻路 **Repository Path**: zhang-zhiyang/a-star-pathfinding ## Basic Information - **Project Name**: A星寻路 - **Description**: js实现一个A星寻路演示案例 - **Primary Language**: JavaScript - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-10-12 - **Last Updated**: 2024-10-12 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README 在 A 星寻路算法中,公式 F = G + H 是用来评估每个节点的优先级的。这个公式将节点的代价 G(即从起始节点到当前节点的实际代价)与启发式估算值 H(即从当前节点到目标节点的估算代价)相加,得到节点的总代价 F。这个总代价 F 越小,节点的优先级就越高,A\*算法会优先探索这些具有更低总代价的节点。 具体来说,这三个字母的含义如下: - G 代表从起始节点到当前节点的实际代价,也可以理解为已经走过的路径的长度。 - H 代表从当前节点到目标节点的估算代价,通常使用一种启发式算法(如曼哈顿距离或欧几里得距离)来估算。 - F 是节点的总代价,即 G 和 H 的和,用来评估节点的优先级。 通过使用这个公式,A 星算法可以在搜索过程中同时考虑已经走过的路径长度和目标节点的距离,从而找到一条最优的路径。 这三个字母在 A\*寻路算法中通常有对应的单词: G 代表"实际代价"(Actual cost),也可以称为"已经走过的路径长度"(Actual distance)。 H 代表"启发式估算值"(Heuristic estimation),也可以称为"预估代价"(Heuristic cost)。 F 代表"总代价"(Total cost)或"优先级"(Priority)。算法中的各个参数的含义和作用。G 表示已经走过的路径长度,H 是对目标节点的估算代价,F 是节点的总代价,同时也是节点的优先级。这些术语的使用有助于我们在解释和实现 A 参考网址:https://blog.csdn.net/nie2314550441/article/details/106733189 https://www.cnblogs.com/huansky/p/5572631.html js 实现 A\*寻路算法下面有一个简单的代码示例,来自上面的第二个链接 //其中的 MAP.arr 是二维数组 function searchRoad(start_x,start_y,end_x,end_y){ var openList=[], //开启列表 closeList=[], //关闭列表 result=[], //结果数组 result_index; //结果数组在开启列表中的序号 openList.push({x:start_x,y:start_y,G:0});//把当前点加入到开启列表中,并且G是0 do{ var currentPoint = openList.pop(); closeList.push(currentPoint); var surroundPoint=SurroundPoint(currentPoint); for(var i in surroundPoint) { var item = surroundPoint[i]; //获得周围的八个点 if ( item.x>=0 && //判断是否在地图上 item.y>=0 && item.x