JavaScript A*算法

A* 算法是一种广泛应用于路径查找和图遍历的启发式搜索算法。它的设计目的是为了解决寻路问题，并且能够有效地找到从起点到终点的最短路径。本章将详细介绍如何使用 JavaScript 实现 A* 算法。

A* 算法简介

A* 算法是 Dijkstra 算法的一种改进版本，通过引入一个启发函数（heuristic function），使得算法能够更快地找到最短路径。这个启发函数通常用来估计从当前节点到目标节点的距离，从而帮助算法优先探索那些更有可能到达目标节点的路径。

启发式函数

在 A* 算法中，启发式函数用于评估从当前节点到目标节点的成本。常用的启发式函数包括：

• 曼哈顿距离：适用于网格地图，计算两点之间水平和垂直方向的距离之和。
• 欧几里得距离：计算两点之间的直线距离。
• 切比雪夫距离：计算两点之间最大水平或垂直距离。

在实现 A* 算法时，选择合适的启发式函数对算法性能至关重要。

数据结构与变量定义

为了实现 A* 算法，我们需要定义一些基本的数据结构和变量：

// www.javascriptcn.com code example
class Node {
    constructor(x, y, parent = null) {
        this.x = x;
        this.y = y;
        this.parent = parent;
        this.g = 0; // 起点到当前节点的实际代价
        this.h = 0; // 当前节点到目标节点的估计代价
        this.f = 0; // f = g + h
    }
}

const heuristic = (a, b) => Math.abs(a.x - b.x) + Math.abs(a.y - b.y); // 曼哈顿距离

查找邻居节点

在 A* 算法中，需要查找当前节点的所有可移动邻居节点。这里我们假设地图是一个二维数组，其中值为 0 表示可通过，值为 1 表示障碍物。

// www.javascriptcn.com code example
function getNeighbors(node, grid) {
    const neighbors = [];
    const directions = [
        { dx: -1, dy: 0 },
        { dx: 1, dy: 0 },
        { dx: 0, dy: -1 },
        { dx: 0, dy: 1 }
    ];

    for (const dir of directions) {
        const neighborX = node.x + dir.dx;
        const neighborY = node.y + dir.dy;

        if (neighborX >= 0 && neighborX < grid[0].length &&
            neighborY >= 0 && neighborY < grid.length &&
            grid[neighborY][neighborX] === 0) {
            neighbors.push(new Node(neighborX, neighborY, node));
        }
    }

    return neighbors;
}

A* 算法主逻辑

A* 算法的核心在于维护两个列表：一个用于存储待检查的节点（openList），另一个用于存储已检查的节点（closedList）。每次迭代中，我们选择 openList 中 f 值最小的节点作为当前节点进行扩展。

// www.javascriptcn.com code example
function aStar(start, end, grid) {
    let openList = [start];
    let closedList = [];

    while (openList.length > 0) {
        // 找到 openList 中 f 值最小的节点
        let currentNode = openList.reduce((minNode, node) => node.f < minNode.f ? node : minNode);

        // 将当前节点移出 openList 并加入 closedList
        openList = openList.filter(node => node !== currentNode);
        closedList.push(currentNode);

        // 检查是否到达目标节点
        if (currentNode.x === end.x && currentNode.y === end.y) {
            return reconstructPath(currentNode);
        }

        // 扩展当前节点
        const neighbors = getNeighbors(currentNode, grid);
        for (const neighbor of neighbors) {
            if (closedList.some(node => node.x === neighbor.x && node.y === neighbor.y)) {
                continue; // 避免重复处理
            }

            neighbor.g = currentNode.g + 1;
            neighbor.h = heuristic(neighbor, end);
            neighbor.f = neighbor.g + neighbor.h;

            // 如果邻居节点已经在 openList 中，检查是否有更优路径
            const existingNode = openList.find(node => node.x === neighbor.x && node.y === neighbor.y);
            if (existingNode) {
                if (neighbor.g < existingNode.g) {
                    existingNode.g = neighbor.g;
                    existingNode.f = neighbor.f;
                    existingNode.parent = neighbor.parent;
                }
            } else {
                openList.push(neighbor);
            }
        }
    }

    return []; // 没有找到路径
}

function reconstructPath(node) {
    const path = [];
    while (node) {
        path.unshift({ x: node.x, y: node.y });
        node = node.parent;
    }
    return path;
}

测试与验证

为了验证 A* 算法的正确性和效率，我们可以创建一个简单的测试场景：

// www.javascriptcn.com code example
const start = new Node(0, 0);
const end = new Node(9, 9);
const grid = Array.from({ length: 10 }, () => Array(10).fill(0));

// 在地图上设置障碍物
grid[5][5] = 1;
grid[5][6] = 1;
grid[5][7] = 1;

const path = aStar(start, end, grid);
console.log(path); // 输出找到的路径

以上代码实现了从起点到终点的 A* 寻路算法，并且可以处理简单的障碍物场景。你可以根据实际需求调整启发式函数和邻域搜索方式来优化算法性能。