C# A*算法控制台Demo

using System;

namespace DemoAstart
{
using System;
using System.Collections.Generic;
class Node
{
    public int x, y;
    public int f, g, h;
    public bool wall;

    public Node parent;

    public Node(int x, int y, bool wall)
    {
        this.x = x;
        this.y = y;
        this.wall = wall;
    }

    public int CalculateF()
    {
        f = g + h;
        return f;
    }
}

class Program
{
    static void Main(string[] args)
    {
        int[,] maze = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 1, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };

        Node start = new Node(0, 0, false);
        Node end = new Node(4, 4, false);

        List<Node> openList = new List<Node>();
        List<Node> closedList = new List<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)
            {
                List<Node> path = new List<Node>();
                Node currentPathNode = currentNode;

                while (currentPathNode.parent != null)
                {
                    path.Add(currentPathNode);
                    currentPathNode = currentPathNode.parent;
                }

                path.Reverse();

                foreach (Node pathNode in path)
                {
                    Console.WriteLine("X: " + pathNode.x + " Y: " + pathNode.y);
                }

                return;
            }

            List<Node> neighbors = new List<Node>();

            if (currentNode.x > 0)
            {
                neighbors.Add(new Node(currentNode.x - 1, currentNode.y, maze[currentNode.x - 1, currentNode.y] == 1));
            }

            if (currentNode.y > 0)
            {
                neighbors.Add(new Node(currentNode.x, currentNode.y - 1, maze[currentNode.x, currentNode.y - 1] == 1));
            }

            if (currentNode.x < maze.GetLength(0) - 1)
            {
                neighbors.Add(new Node(currentNode.x + 1, currentNode.y, maze[currentNode.x + 1, currentNode.y] == 1));
            }

            if (currentNode.y < maze.GetLength(1) - 1)
            {
                neighbors.Add(new Node(currentNode.x, currentNode.y + 1, maze[currentNode.x, currentNode.y + 1] == 1));
            }

            foreach (Node neighbor in neighbors)
            {
                if (neighbor.wall || closedList.Contains(neighbor))
                {
                    continue;
                }

                int tentativeG = currentNode.g + 1;

                if (!openList.Contains(neighbor))
                {
                    openList.Add(neighbor);
                }
                else if (tentativeG >= neighbor.g)
                {
                    continue;
                }

                neighbor.parent = currentNode;
                neighbor.g = tentativeG;
                neighbor.h = CalculateDistance(neighbor, end);
                neighbor.CalculateF();
            }
        }

        Console.WriteLine("No path found.");
    }

    static int CalculateDistance(Node node1, Node node2)
    {
        return Math.Abs(node1.x - node2.x) + Math.Abs(node1.y - node2.y);
    }

}
}

A*算法是一种启发式搜索算法，用于在图或网格中找到最短路径。

该算法的基本思想是，在搜索过程中同时使用两个估价函数f(n)和g(n)，其中g(n)表示从起点到节点n的实际代价，f(n)表示从起点到节点n的代价估计值，即f(n) = g(n) + h(n)，其中h(n)是启发式函数，用于估计从节点n到目标节点的最短距离。

A*算法首先将起点加入开放列表(open list)中，然后重复以下步骤：

从开放列表中选取f值最小的节点n。
如果n是终点，则路径搜索完成。
否则，将n从开放列表中删除，并将其加入关闭列表(closed list)中。
遍历n的所有相邻节点，并对每个相邻节点执行以下操作：a. 如果该节点已经在关闭列表中，则忽略该节点。b. 如果该节点不在开放列表中，则将其加入开放列表，并计算该节点的f值、g值和h值，并将n设为该节点的父节点。c. 如果该节点已经在开放列表中，则检查从起点到该节点的新路径是否更优。如果更优，则更新该节点的父节点为n，并更新该节点的g值和f值。
重复步骤1-4，直到找到终点或开放列表为空。

当搜索完成时，从终点开始沿着每个节点的父节点向上遍历，即可找到从起点到终点的最短路径。

A*算法的优势在于它能够有效地避免不必要的扩展节点，并且在最优情况下只需要遍历目标节点的最短路径，因此速度相对较快。然而，它的性能也取决于启发式函数的质量，因此选择合适的启发式函数对算法的效率和准确性都有很大的影响。

C# A*算法控制台Demo

Comments | NOTHING

取消回复