C#如何实现A Star算法？C#中A*寻路算法的完整实现步骤是什么

A*寻路算法结合了Dijkstra算法的广度优先特性和贪心算法的最优性，通过评估函数f(n)=g(n)+h(n)选择最优路径节点，其中g(n)是从起点到当前节点的实际代价，h(n)是当前节点到终点的预估代价，在C#中实现该算法需要按照固定流程处理节点和路径逻辑。

A*算法核心概念

实现前需要先明确几个核心概念，避免逻辑混淆：

• 节点（Node）：地图中的最小单元，通常对应网格的一个格子，包含位置、代价、父节点等属性
• 开放列表（Open List）：存储待检查的节点，每次从中选取f值最小的节点进行扩展
• 关闭列表（Close List）：存储已经检查过的节点，避免重复处理
• 启发函数（Heuristic Function）：计算h(n)的函数，常用曼哈顿距离、欧几里得距离等

基础节点类定义

首先需要定义节点类，存储节点的核心属性，代码如下：

// 定义网格节点类
public class PathNode
{
    // 节点在网格中的x坐标
    public int X { get; set; }
    // 节点在网格中的y坐标
    public int Y { get; set; }
    // 从起点到当前节点的实际代价g
    public int G { get; set; }
    // 当前节点到终点的预估代价h
    public int H { get; set; }
    // 总代价f = g + h
    public int F => G + H;
    // 父节点，用于回溯路径
    public PathNode Parent { get; set; }
    // 节点是否可通行
    public bool IsWalkable { get; set; }

    public PathNode(int x, int y, bool isWalkable = true)
    {
        X = x;
        Y = y;
        IsWalkable = isWalkable;
        G = 0;
        H = 0;
        Parent = null;
    }
}

启发函数实现

这里使用曼哈顿距离作为启发函数，适合网格只能上下左右移动的寻路场景，代码如下：

// 计算两个节点之间的曼哈顿距离作为启发值h
public static int CalculateManhattanDistance(PathNode a, PathNode b)
{
    return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
}

A*算法核心实现

核心逻辑包含初始化列表、选取最小f节点、扩展相邻节点、更新代价、回溯路径几个步骤，完整实现如下：

using System;
using System.Collections.Generic;
using System.Linq;

public class AStarPathfinding
{
    // 网格地图，二维数组表示，true为可通行
    private PathNode[,] grid;
    // 网格行数
    private int rows;
    // 网格列数
    private int cols;

    public AStarPathfinding(PathNode[,] mapGrid)
    {
        grid = mapGrid;
        rows = grid.GetLength(0);
        cols = grid.GetLength(1);
    }

    // 寻路主方法，返回路径节点列表，无路径返回空列表
    public List<PathNode> FindPath(PathNode start, PathNode end)
    {
        // 开放列表，存储待检查的节点
        List<PathNode> openList = new List<PathNode>();
        // 关闭列表，存储已检查的节点
        HashSet<PathNode> closeSet = new HashSet<PathNode>();

        // 初始化起点
        start.G = 0;
        start.H = CalculateManhattanDistance(start, end);
        openList.Add(start);

        while (openList.Count > 0)
        {
            // 从开放列表中找到f值最小的节点
            PathNode current = openList.OrderBy(n => n.F).First();

            // 如果当前节点是终点，回溯路径
            if (current.X == end.X && current.Y == end.Y)
            {
                return RetracePath(start, end);
            }

            // 将当前节点从开放列表移到关闭列表
            openList.Remove(current);
            closeSet.Add(current);

            // 获取当前节点的所有相邻可通行节点
            List<PathNode> neighbors = GetNeighbors(current);

            foreach (var neighbor in neighbors)
            {
                // 如果邻居不可通行或者在关闭列表中，跳过
                if (!neighbor.IsWalkable || closeSet.Contains(neighbor))
                {
                    continue;
                }

                // 计算从起点经过当前节点到邻居的g值
                int newG = current.G + 1;

                // 如果邻居不在开放列表中，或者新的g值更小，更新邻居属性
                if (!openList.Contains(neighbor) || newG < neighbor.G)
                {
                    neighbor.G = newG;
                    neighbor.H = CalculateManhattanDistance(neighbor, end);
                    neighbor.Parent = current;

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

        // 开放列表为空仍未找到终点，返回空路径
        return new List<PathNode>();
    }

    // 获取当前节点的相邻节点（上下左右四个方向）
    private List<PathNode> GetNeighbors(PathNode node)
    {
        List<PathNode> neighbors = new List<PathNode>();

        // 上
        if (node.Y > 0)
        {
            neighbors.Add(grid[node.Y - 1, node.X]);
        }
        // 下
        if (node.Y < rows - 1)
        {
            neighbors.Add(grid[node.Y + 1, node.X]);
        }
        // 左
        if (node.X > 0)
        {
            neighbors.Add(grid[node.Y, node.X - 1]);
        }
        // 右
        if (node.X < cols - 1)
        {
            neighbors.Add(grid[node.Y, node.X + 1]);
        }

        return neighbors;
    }

    // 回溯路径，从终点反向找到起点
    private List<PathNode> RetracePath(PathNode start, PathNode end)
    {
        List<PathNode> path = new List<PathNode>();
        PathNode current = end;

        while (current != start)
        {
            path.Add(current);
            current = current.Parent;
        }
        path.Add(start);
        // 反转路径，从起点到终点
        path.Reverse();

        return path;
    }
}

使用示例

下面演示如何初始化地图并调用寻路方法，代码如下：

class Program
{
    static void Main(string[] args)
    {
        // 初始化5x5的网格地图，true表示可通行
        PathNode[,] grid = new PathNode[5, 5];
        for (int y = 0; y < 5; y++)
        {
            for (int x = 0; x < 5; x++)
            {
                // 这里可以设置部分节点不可通行，比如(2,2)位置为障碍物
                bool isWalkable = (x == 2 && y == 2) ? false : true;
                grid[y, x] = new PathNode(x, y, isWalkable);
            }
        }

        // 定义起点(0,0)和终点(4,4)
        PathNode startNode = grid[0, 0];
        PathNode endNode = grid[4, 4];

        // 创建A*寻路实例
        AStarPathfinding astar = new AStarPathfinding(grid);
        // 执行寻路
        List<PathNode> path = astar.FindPath(startNode, endNode);

        // 输出路径结果
        if (path.Count > 0)
        {
            Console.WriteLine("寻路成功，路径节点坐标：");
            foreach (var node in path)
            {
                Console.WriteLine($"({node.X}, {node.Y})");
            }
        }
        else
        {
            Console.WriteLine("未找到可达路径");
        }
    }
}

注意事项

实际使用中可以根据需求调整以下部分：

• 如果需要支持斜向移动，修改GetNeighbors方法添加四个斜向相邻节点，同时调整g值计算，斜向移动的g值通常设为√2取整或者1.4
• 启发函数可以根据场景替换，比如允许斜向移动时可以使用欧几里得距离
• 开放列表的排序操作如果地图较大，建议使用优先队列（PriorityQueue）优化性能，避免每次遍历查找最小f节点
• 网格地图可以根据实际需求替换为其他地图结构，只需要调整节点的相邻节点获取逻辑即可

C#A_Star_algorithmpathfindinggrid_map修改时间：2026-07-13 07:33:32