A*（A star）算法是一种广泛应用于路径规划的启发式搜索算法，兼具Dijkstra算法的优点与启发式估计的策略。在C#中，我们可以结合GDI+进行可视化以更好地理解算法的运作机制。

A* 算法的逻辑

A*算法通过维护一个开放列表和一个封闭列表来寻找路径：

1. 初始化：将起始点加入开放列表。
2. 循环过程： 从开放列表中选取估价函数（f = g + h）最小的节点作为当前节点。 若该节点是目标节点，则路径找到，算法结束。 否则，将该节点从开放列表移至封闭列表。 对当前节点的每个邻居（可通行节点）： 如果邻居在封闭列表中，忽略。 如果不在开放列表中，加入开放列表，设置当前节点为其父节点，并计算g（从起始点到该节点的实际代价）和h（从该节点到终点的估计代价）。 如果在开放列表中，检查新的路径是否更优。如果更优，更新该邻居的父节点和g值。

C# 中的 A* 实现

以下是一个简单的A*算法的C#实现示例。我们假设网格地图中，每个节点的代价为1（无障碍），h函数使用曼哈顿距离。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AppAStar
{
    //Node类 - 节点定义
    public class Node
    {
        public Point Position { get; set; }
        public int G { get; set; }
        public int H { get; set; }
        public int F => G + H;
        public Node Parent { get; set; }
        public NodeState State { get; set; }

        public Node(Point position)
        {
            Position = position;
            State = NodeState.Unvisited;
        }
    }

    //NodeState枚举 - 节点状态
    public enum NodeState
    {
        Unvisited,
        OpenList,
        ClosedList,
        Path,
        Wall,
        Start,
        End
    }

    public class AStarPathfinding
    {
        private const int GridSize = 20;
        private readonly Node[,] grid;
        private List<Node> openList;
        private HashSet<Node> closedList;
        private Node startNode;
        private Node endNode;
        private bool pathFound;
        private readonly Random random = new Random();

        public event Action<Node> OnNodeStateChanged;
        public event Action OnPathFound;

        public AStarPathfinding()
        {
            grid = new Node[GridSize, GridSize];
            InitializeGrid();
        }

        private void InitializeGrid()
        {
            // Create nodes  
            for (int x = 0; x < GridSize; x++)
            {
                for (int y = 0; y < GridSize; y++)
                {
                    grid[x, y] = new Node(new Point(x, y));

                    // Randomly place walls (20% chance)  
                    if (random.NextDouble() < 0.2)
                    {
                        grid[x, y].State = NodeState.Wall;
                    }
                }
            }

            // Set start and end points  
            startNode = grid[0, 0];
            endNode = grid[GridSize - 1, GridSize - 1];
            startNode.State = NodeState.Start;
            endNode.State = NodeState.End;
        }

        public async void StartPathfinding()
        {
            openList = new List<Node> { startNode };
            closedList = new HashSet<Node>();
            pathFound = false;

            while (openList.Count > 0 && !pathFound)
            {
                Node current = openList.OrderBy(n => n.F).First();

                if (current == endNode)
                {
                    pathFound = true;
                    ReconstructPath();
                    OnPathFound?.Invoke();
                    return;
                }

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

                if (current != startNode)
                {
                    current.State = NodeState.ClosedList;
                    OnNodeStateChanged?.Invoke(current);
                }

                foreach (Node neighbor in GetNeighbors(current))
                {
                    if (closedList.Contains(neighbor) || neighbor.State == NodeState.Wall)
                        continue;

                    int tentativeG = current.G + 1;

                    if (!openList.Contains(neighbor))
                    {
                        neighbor.Parent = current;
                        neighbor.G = tentativeG;
                        neighbor.H = CalculateHeuristic(neighbor, endNode);
                        openList.Add(neighbor);

                        if (neighbor != endNode)
                        {
                            neighbor.State = NodeState.OpenList;
                            OnNodeStateChanged?.Invoke(neighbor);
                        }
                    }
                    else if (tentativeG < neighbor.G)
                    {
                        neighbor.Parent = current;
                        neighbor.G = tentativeG;
                    }
                }

                await System.Threading.Tasks.Task.Delay(50); // Animation delay  
            }
        }

        private List<Node> GetNeighbors(Node node)
        {
            List<Node> neighbors = new List<Node>();
            Point[] directions = new Point[]
            {
            new Point(0, 1),  // right  
            new Point(1, 0),  // down  
            new Point(0, -1), // left  
            new Point(-1, 0), // up  
            };

            foreach (Point dir in directions)
            {
                int newX = node.Position.X + dir.X;
                int newY = node.Position.Y + dir.Y;

                if (newX >= 0 && newX < GridSize && newY >= 0 && newY < GridSize)
                {
                    neighbors.Add(grid[newX, newY]);
                }
            }

            return neighbors;
        }

        private int CalculateHeuristic(Node a, Node b)
        {
            return Math.Abs(a.Position.X - b.Position.X) + Math.Abs(a.Position.Y - b.Position.Y);
        }

        private void ReconstructPath()
        {
            Node current = endNode;
            while (current != startNode)
            {
                if (current != endNode)
                {
                    current.State = NodeState.Path;
                    OnNodeStateChanged?.Invoke(current);
                }
                current = current.Parent;
            }
        }
    }

}

窗体

using Timer = System.Windows.Forms.Timer;

namespace AppAStar
{
    public partial class Form1 : Form
    {
        private const int GridSize = 20;
        private const int CellSize = 30;
        private readonly Node[,] grid;
        private List<Node> openList;
        private HashSet<Node> closedList;
        private Node startNode;
        private Node endNode;
        private readonly Random random = new Random();
        private bool isRunning = false;

        private readonly Dictionary<NodeState, Color> nodeColors = new Dictionary<NodeState, Color>
        {
            { NodeState.Unvisited, Color.White },    // 未访问节点为白色  
            { NodeState.OpenList, Color.LightGreen }, // 开放列表节点为浅绿色  
            { NodeState.ClosedList, Color.LightGray }, // 关闭列表节点为浅灰色  
            { NodeState.Path, Color.Yellow },         // 最终路径为黄色  
            { NodeState.Wall, Color.Black },          // 障碍物为黑色  
            { NodeState.Start, Color.Green },         // 起点为绿色  
            { NodeState.End, Color.Red }              // 终点为红色  
        };

        public Form1()
        {
            InitializeComponent();

            ClientSize = new Size(CellSize * GridSize, CellSize * GridSize + 40);
            grid = new Node[GridSize, GridSize];
            InitializeGrid();

            Button startButton = new Button
            {
                Text = "开始搜索",
                Location = new Point(10, ClientSize.Height - 35),
                Width = 120
            };
            startButton.Click += btnStart_Click;
            Controls.Add(startButton);

            SetStyle(ControlStyles.AllPaintingInWmPaint |
                    ControlStyles.UserPaint |
                    ControlStyles.DoubleBuffer, true);
        }

        private void InitializeGrid()
        {
            // 创建节点
            for (int x = 0; x < GridSize; x++)
            {
                for (int y = 0; y < GridSize; y++)
                {
                    grid[x, y] = new Node(new Point(x, y));

                    if (random.NextDouble() < 0.2)
                    {
                        grid[x, y].State = NodeState.Wall;
                    }
                }
            }

            // 设置开始与结束节点 
            startNode = grid[0, 0];
            endNode = grid[GridSize - 1, GridSize - 1];
            startNode.State = NodeState.Start;
            endNode.State = NodeState.End;

            grid[0, 0].State = NodeState.Start;
            grid[GridSize - 1, GridSize - 1].State = NodeState.End;
        }

        private async void btnStart_Click(object sender, EventArgs e)
        {
            if (isRunning) return;
            isRunning = true;

            openList = new List<Node> { startNode };    // 初始化开放列表，将起点加入  
            closedList = new HashSet<Node>();           // 初始化关闭列表  

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

                // 判断是否到达终点  
                if (current == endNode)
                {
                    await ReconstructPath();            // 重建路径  
                    MessageBox.Show("找到路径!");
                    isRunning = false;
                    return;
                }

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

                // 更新节点状态和显示  
                if (current != startNode)
                {
                    current.State = NodeState.ClosedList;
                    Invalidate();
                    await System.Threading.Tasks.Task.Delay(50);  // 动画延迟  
                }

                // 处理相邻节点  
                foreach (Node neighbor in GetNeighbors(current))
                {
                    // 跳过已关闭或是墙壁的节点  
                    if (closedList.Contains(neighbor) || neighbor.State == NodeState.Wall)
                        continue;

                    // 计算从起点经过当前节点到相邻节点的代价  
                    int tentativeG = current.G + 1;

                    // 如果是新节点或找到更好的路径  
                    if (!openList.Contains(neighbor))
                    {
                        neighbor.Parent = current;       // 设置父节点  
                        neighbor.G = tentativeG;         // 设置G值  
                        neighbor.H = CalculateHeuristic(neighbor, endNode);  // 计算H值  
                        openList.Add(neighbor);          // 加入开放列表  

                        // 更新显示  
                        if (neighbor != endNode)
                        {
                            neighbor.State = NodeState.OpenList;
                            Invalidate();
                            await System.Threading.Tasks.Task.Delay(50);
                        }
                    }
                    else if (tentativeG < neighbor.G)   // 找到更短的路径  
                    {
                        neighbor.Parent = current;
                        neighbor.G = tentativeG;
                    }
                }
            }
        }

        private List<Node> GetNeighbors(Node node)
        {
            List<Node> neighbors = new List<Node>();
            // 定义四个方向：右、下、左、上  
            Point[] directions = new Point[]
            {
                new Point(0, 1),   // 右  
                new Point(1, 0),   // 下  
                new Point(0, -1),  // 左  
                new Point(-1, 0),  // 上  
            };

            // 检查每个方向的相邻节点  
            foreach (Point dir in directions)
            {
                int newX = node.Position.X + dir.X;
                int newY = node.Position.Y + dir.Y;

                // 确保节点在网格范围内  
                if (newX >= 0 && newX < GridSize && newY >= 0 && newY < GridSize)
                {
                    neighbors.Add(grid[newX, newY]);
                }
            }
            return neighbors;
        }

        private int CalculateHeuristic(Node a, Node b)
        {
            // 使用曼哈顿距离作为启发式函数  
            return Math.Abs(a.Position.X - b.Position.X) + Math.Abs(a.Position.Y - b.Position.Y);
        }

        private async Task ReconstructPath()
        {
            Node current = endNode;
            // 从终点往回追踪到起点  
            while (current != startNode)
            {
                if (current != endNode)
                {
                    current.State = NodeState.Path;  // 标记路径  
                    Invalidate();
                    await System.Threading.Tasks.Task.Delay(50);
                }
                current = current.Parent;  // 沿着父节点指针往回走  
            }
        }

        protected override void OnPaint(PaintEventArgs e)
        {
            base.OnPaint(e);
            Graphics g = e.Graphics;

            for (int x = 0; x < GridSize; x++)
            {
                for (int y = 0; y < GridSize; y++)
                {
                    Node node = grid[x, y];
                    Rectangle rect = new Rectangle(x * CellSize, y * CellSize, CellSize, CellSize);
                    g.FillRectangle(new SolidBrush(nodeColors[node.State]), rect);
                    g.DrawRectangle(Pens.Gray, rect);
                }
            }
        }
    }
}

观察算法执行过程：

• 浅绿色：当前正在考虑的节点（开放列表）
• 灰色：已经访问过的节点（关闭列表）
• 黄色：最终找到的路径

代码说明

• 数据结构：使用List<Node>来表示开放列表，HashSet<Node>表示封闭列表。
• 算法过程：以起点为初始节点，不断扩展节点直至找到终点或开放列表为空。
• GUI 部分：使用Windows Forms和GDI+进行简单的图形显示。红色方块表示找到的路径。

A算法由于其高效的计算特性，已被广泛应用于游戏AI、机器人导航及其他需要路径规划的领域。希望通过以上C#示例能帮助您理解和应用A算法。