A*算法主要作用是寻找两个节点之间的最短路径
首先，需要定义一个表示地图的二维数组，其中0表示可通过的空地，1表示障碍物：
const map = [
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0]
];
接着，定义节点类，包含节点的坐标和计算曼哈顿距离的方法：
class Node {
constructor(x, y) {
this.x = x;
this.y = y;
this.g = 0; // 起点到当前节点的成本：从起始节点到当前节点的移动距离（父节点的g + 1）
this.h = 0; // 当前节点到终点的预计成本：评估从此节点到目标节点成本最小路径，这里的预计成本使用曼哈顿距离（曼哈顿距离 = 两点的x轴距离 + 两点的y轴距离）
this.f = 0; // 预计总成本：总成本最小的为最优路径（g + h）
this.parent = null; // 当前节点的父节点，用于回溯最优路径
}
// 启发式函数：这里是计算当前节点到终点的曼哈顿距离
calcHeuristic(target) {
this.h = Math.abs(target.x - this.x) + Math.abs(target.y - this.y);
}
}
接下来，定义A*算法的实现函数：
算法框架：
1.初始化开启列表和关闭列表。开始时，将起始节点添加到开启列表。
2.进入循环，直到开启列表为空或找到目标节点：
选取开启列表中的节点，该节点是根据启发式函数计算的最佳候选节点。
将选定的节点从开启列表中移除，并将它添加到关闭列表中。
3.对于当前节点的所有可行相邻节点，计算它们的启发式函数值和代价函数值：
如果相邻节点已经在关闭列表中，则忽略它并继续下一个节点。
如果相邻节点不在开启列表中，则将它添加到开启列表，并计算它的启发式函数值和代价函数值。 然后，将当前节点设置为该相邻节点的父节点。
4.如果相邻节点已经在开启列表中，比较当前路径代价和新计算的代价：
如果新计算的代价更小，则更新相邻节点的父节点为当前节点，并重新计算启发式函数值和代价函数值。
如果新计算的代价更大，则保持相邻节点的父节点不变。
5.在循环结束后，如果找到了目标节点，则从目标节点回溯到起始节点，即可获得找到的最佳路径。
function aStar(start, target) {
const openList = []; // 待探索的节点列表
const closedList = []; // 已探索的节点列表
openList.push(start);
while (openList.length > 0) {
// 在openList中选择评估值最小的节点
let current = openList[0];
let currentIndex = 0;
for (let i = 1; i < openList.length; i++) {
if (openList[i].f < current.f) {
current = openList[i];
currentIndex = i;
}
}
// 如果当前节点是目标节点，说明路径已找到，进行回溯
if (current.x === target.x && current.y === target.y) {
let path = [];
let temp = current;
while (temp !== null) {
path.push({
x: temp.x, y: temp.y });
temp = temp.parent;
}
return path.reverse();
}
// 将当前节点从openList中移除，并加入closedList中
openList.splice(currentIndex, 1);
closedList.push(current);
// 寻找当前节点的相邻节点
const neighbors = [
{
x: current.x - 1, y: current.y },
{
x: current.x + 1, y: current.y },
{
x: current.x, y: current.y - 1 },
{
x: current.x, y: current.y + 1 }
];
for (let neighbor of neighbors) {
// 排除超出地图范围和障碍物的节点
if (
neighbor.x < 0 ||
neighbor.x >= map.length ||
neighbor.y < 0 ||
neighbor.y >= map[0].length ||
map[neighbor.x][neighbor.y] === 1
) {
continue;
}
// 如果相邻节点已在closedList中，则跳过
if (closedList.some(node => node.x === neighbor.x && node.y === neighbor.y)) {
continue;
}
let newG = current.g + 1; // 相邻节点的实际成本
let neighborNode = openList.find(node => node.x === neighbor.x && node.y === neighbor.y);
if (!neighborNode || newG < neighborNode.g) {
// 如果相邻节点不在openList中或新的路径成本更低
if (!neighborNode) {
neighborNode = new Node(neighbor.x, neighbor.y);
openList.push(neighborNode);
}
neighborNode.g = newG;
neighborNode.calcHeuristic(target);
neighborNode.f = neighborNode.g + neighborNode.h;
neighborNode.parent = current;
}
}
}
return null; // 如果无法找到路径，返回null
}
最后，我们可以使用上述函数来查找起点(0, 0)到目标点(4, 4)的最短路径：
const startNode = new Node(0, 0);
const targetNode = new Node(3, 4);
startNode.calcHeuristic(targetNode);
const path = aStar(startNode, targetNode);
console.log(path); // 输出最短路径
