A* JPS寻路算法的探讨

keyle

发布于 2024-11-01 12:23:27

1060

发布于 2024-11-01 12:23:27

文章被收录于专栏：礼拜八不工作

A*（A-star）寻路算法是一种基于启发式搜索的路径规划算法，常用于游戏开发和人工智能领域，JPS是A*算法的一个优化算法，咱们就先做一段简单的A*算法介绍，后续再进行JPS算法的进一步探讨。

A* 要素说明：
- 开启节点列表（OpenList）：存放待检测的节点。
- 关闭节点列表（ClosedList）：存放不会被检测的节点。
- G 值：从初始节点到任意节点的代价。
- H 值：从节点到目标点的启发式评估代价。
- F 值：G 值和 H 值之和。
- A* 算法通过在二维数组或网格中寻找两点之间的最短路径，结合启发式评估来快速确定路径，算法核心是选择 F 值最小的节点进行扩展，直到找到终点或遍历完所有节点。
实现步骤：
- 从 OpenList 中选择 F 值最小的节点（如果 F 相同，选取 H 最小的）。
- 遍历该节点周围的相邻节点：
- 如果没有找到终点，继续循环。
- 如果相邻节点不在 OpenList 中，计算其 G 值和 H 值，并设置父节点为当前节点，加入 OpenList。
- 如果相邻节点已在 OpenList 中，更新其 G 值为较小的值，重新设置父节点。
- 如果遍历到终点，回溯路径，找到最终路径。
- 创建一个节点类，包含节点是否可通过、世界坐标、网格坐标、G 值、H 值和父节点信息。
- 创建网格，初始化节点列表，设置节点是否可通过。
- 将起点放入 OpenList 中。
- 循环执行以上步骤可参考下面的C#代码案例：

public List<Node> FindPath(Node start, Node end)
{
    List<Node> openList = new List<Node>();
    HashSet<Node> closedList = new HashSet<Node>();

    openList.Add(start);

    while (openList.Count > 0)
    {
        Node currentNode = openList[0];

        for (int i = 1; i < openList.Count; i++)
        {
            if (openList[i].f < currentNode.f || (openList[i].f == currentNode.f && openList[i].h < currentNode.h))
            {
                currentNode = openList[i];
            }
        }

        openList.Remove(currentNode);
        closedList.Add(currentNode);

        if (currentNode.x == end.x && currentNode.y == end.y)
        {
            return GetPath(currentNode);
        }

        //List<Node> neighbors = GetNeighbors(currentNode, end);
        List<Node> neighbors = GetNeighbors8(currentNode);
        foreach (Node neighbor in neighbors)
        {
            if (closedList.Contains(neighbor) || map[neighbor.x, neighbor.y] == 1)
                continue;

            float newCost = currentNode.g + GetMoveCost(currentNode, neighbor); // 计算移动代价
            if (newCost < neighbor.g || !openList.Contains(neighbor))
            {
                neighbor.g = newCost;
                neighbor.h = Heuristic(neighbor, end);
                neighbor.parent = currentNode;

                if (!openList.Contains(neighbor))
                    openList.Add(neighbor);
            }
        }
    }

    return null;
}


private List<Node> GetNeighbors(Node node, Node end)
{
    List<Node> neighbors = new List<Node>();

    for (int dx = -1; dx <= 1; dx++)
    {
        for (int dy = -1; dy <= 1; dy++)
        {
            // 跳过当前节点
            if (dx == 0 && dy == 0)
                continue;

            // 如果当前节点是斜对角方向的邻居，检查其是否可行
            if (dx != 0 && dy != 0)
            {
                int nx = node.x + dx;
                int ny = node.y + dy;
                if (nx >= 0 && nx < width && ny >= 0 && ny < height && map[nx, ny] != 1)
                {
                    neighbors.Add(new Node(nx, ny));
                }
            }
            // 如果当前节点是水平或垂直方向的邻居，检查其是否可行
            else
            {
                int nx = node.x + dx;
                int ny = node.y + dy;
                if (nx >= 0 && nx < width && ny >= 0 && ny < height && map[nx, ny] != 1)
                {
                    neighbors.Add(new Node(nx, ny));
                }
            }
        }
    }

    return neighbors;
}


private float GetMoveCost(Node fromNode, Node toNode)
{
    // 如果两个节点在水平、垂直或对角线方向上相邻，则返回固定的代价值
    if (Math.Abs(fromNode.x - toNode.x) + Math.Abs(fromNode.y - toNode.y) == 1) // 水平或垂直移动
    {
        return 1f;
    }
    else // 对角线移动
    {
        return 1.414f; // 对角线移动的代价通常是水平或垂直移动的 sqrt(2) 倍
    }
}

咱们看完了A*的原理，回到主题再来讨论下JPS算法，下面这段介绍来自维基百科:

Jump Point Search (JPS) 是对 A* 搜索算法在均匀代价网格上的一种优化。它通过图剪枝来减少搜索过程中的对称性，从而消除了网格中某些节点，前提是满足与网格相关的某些条件。因此，该算法可以考虑沿着网格的直线（水平、垂直和对角线）进行较长的“跳跃”，而不是普通 A* 考虑的从一个网格位置到下一个网格位置的小步。JPS 保持了 A* 的最优性，同时可能将其运行时间缩短一个数量级。

下面的参考图（直跳a和斜跳b）来自 Harabor, Daniel; Grastien, Alban. "Improving Jump Point Search" (PDF). Australian National University College of Engineering and Computer Science. Association for the Advancement of Artificial Intelligence (www.aaai.org). Retrieved 11 July 2015.

A* 算法回顾：
- A* 算法是一种启发式搜索算法，用于在图或网格上寻找最短路径。
- 它通过估计每个节点到目标的代价（通常使用启发式函数）来选择下一个节点进行扩展。
- A* 算法维护一个开放列表（Open List）和一个关闭列表（Closed List），其中存储了待扩展的节点和已经处理过的节点。
JPS 算法的优化：
- 只关注所谓的“跳跃点”，而不是所有邻居点，在每个搜索步骤中，通过跳过中间的空白节点，直接跳到可能是最优解的位置（Jump Point）。这样可以减少搜索空间，提高搜索效率。
- 在每个节点处进行跳跃，以确定是否存在“强制邻居”（forced neighbors）。如果存在强制邻居，则在这些强制邻居之间不需要再次搜索，可以直接跳到下一个强制邻居，从而减少搜索量。

private List<Node> GetNeighbors(Node node, Node end)
{
    // 初始化一个空的邻居节点列表
    List<Node> neighbors = new List<Node>();

    // 计算当前节点与终点的相对位置
    int dx = Math.Sign(end.x - node.x);
    int dy = Math.Sign(end.y - node.y);
    // Math.Sign(x)函数接受一个参数x，并返回以下值之一：
    // 如果x为正数，则返回+1。
    // 如果x为零，则返回0。
    // 如果x为负数，则返回-1。
    
     // 如果 dx 和 dy 同时为0，表示当前节点与终点重合，直接返回空列表
    if (dx == 0 && dy == 0)
        return neighbors;

    // 如果 dx 和 dy 其中一个为0，表示当前节点沿着水平或垂直方向移动
    if (dx == 0 || dy == 0)
    {
        // 检查水平方向上的邻居
        if (dx != 0)
        {
            int nx = node.x + dx;
            int ny = node.y;

            // 检查节点是否越界，并且是否是强制邻居
            if (nx >= 0 && nx < width && map[nx, ny] != 1)
            {
                neighbors.Add(new Node(nx, ny));
            }
        }
        // 检查垂直方向上的邻居
        else
        {
            int nx = node.x;
            int ny = node.y + dy;

            // 检查节点是否越界，并且是否是强制邻居
            if (ny >= 0 && ny < height && map[nx, ny] != 1)
            {
                neighbors.Add(new Node(nx, ny));
            }
        }
    }
    // 如果 dx 和 dy 同时不为0，表示当前节点沿着斜对角方向移动
    else
    {
        int nx = node.x + dx;
        int ny = node.y + dy;

        // 检查节点是否越界，并且是否是强制邻居
        if (nx >= 0 && nx < width && ny >= 0 && ny < height && map[nx, ny] != 1)
        {
            neighbors.Add(new Node(nx, ny));
        }

        // 检查斜对角方向上的强制邻居
        if (map[node.x, ny] != 1)
        {
            neighbors.Add(new Node(node.x, ny));
        }
        if (map[nx, node.y] != 1)
        {
            neighbors.Add(new Node(nx, node.y));
        }
    }

    // 返回邻居节点列表
    return neighbors;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-05-09，如有侵权请联系 cloudcommunity@tencent.com 删除

优化