龙空技术网

C# 实现AStar寻路算法 的简单例子

凡人兔子张 154

前言:

此时姐妹们对“a算法算法”可能比较重视,小伙伴们都需要了解一些“a算法算法”的相关知识。那么小编在网摘上收集了一些关于“a算法算法””的相关内容,希望咱们能喜欢,大家一起来学习一下吧!

以下是一个简单的C#实现A*寻路算法的示例:

using System;using System.Collections.Generic;public class AStarNode{    public int X { get; set; }    public int Y { get; set; }    public bool IsWall { get; set; }    public int G { get; set; }    public int H { get; set; }    public int F { get { return G + H; } }    public AStarNode Parent { get; set; }    public AStarNode(int x, int y, bool isWall)    {        X = x;        Y = y;        IsWall = isWall;    }}public class AStar{    private int[,] grid;    private int width;    private int height;    private List<AStarNode> openList;    private List<AStarNode> closedList;    public AStar(int[,] grid)    {        this.grid = grid;        width = grid.GetLength(0);        height = grid.GetLength(1);        openList = new List<AStarNode>();        closedList = new List<AStarNode>();    }    public List<AStarNode> FindPath(AStarNode startNode, AStarNode endNode)    {        openList.Clear();        closedList.Clear();        openList.Add(startNode);        while (openList.Count > 0)        {            AStarNode currentNode = GetLowestFScoreNode(openList);            if (currentNode == endNode)            {                return GeneratePath(currentNode);            }            openList.Remove(currentNode);            closedList.Add(currentNode);            List<AStarNode> neighbors = GetNeighbors(currentNode);            foreach (AStarNode neighbor in neighbors)            {                if (closedList.Contains(neighbor) || neighbor.IsWall)                {                    continue;                }                int tentativeGScore = currentNode.G + 1;                if (!openList.Contains(neighbor) || tentativeGScore < neighbor.G)                {                    neighbor.Parent = currentNode;                    neighbor.G = tentativeGScore;                    neighbor.H = CalculateHScore(neighbor, endNode);                    if (!openList.Contains(neighbor))                    {                        openList.Add(neighbor);                    }                }            }        }        return null;    }    private AStarNode GetLowestFScoreNode(List<AStarNode> nodeList)    {        AStarNode lowestFScoreNode = nodeList[0];        for (int i = 1; i < nodeList.Count; i++)        {            if (nodeList[i].F < lowestFScoreNode.F)            {                lowestFScoreNode = nodeList[i];            }        }        return lowestFScoreNode;    }    private List<AStarNode> GetNeighbors(AStarNode node)    {        List<AStarNode> neighbors = new List<AStarNode>();        int[] dx = { -1, 0, 1, 0 };        int[] dy = { 0, 1, 0, -1 };        for (int i = 0; i < 4; i++)        {            int neighborX = node.X + dx[i];            int neighborY = node.Y + dy[i];            if (neighborX >= 0 && neighborX < width && neighborY >= 0 && neighborY < height)            {                AStarNode neighborNode = new AStarNode(neighborX, neighborY, grid[neighborX, neighborY] == 1);                neighbors.Add(neighborNode);            }        }        return neighbors;    }    private int CalculateHScore(AStarNode node, AStarNode endNode)    {        return Math.Abs(node.X - endNode.X) + Math.Abs(node.Y - endNode.Y);    }    private List<AStarNode> GeneratePath(AStarNode endNode)    {        List<AStarNode> path = new List<AStarNode>();        AStarNode currentNode = endNode;        while (currentNode != null)        {            path.Insert(0, currentNode);            currentNode = currentNode.Parent;        }        return path;    }}public class Program{    public static void Main(string[] args)    {        int[,] grid = {            { 0, 0, 0, 0, 0 },            { 0, 1, 1, 0, 0 },            { 0, 0, 0, 0, 0 },            { 0, 1, 1, 1, 0 },            { 0, 0, 0, 0, 0 }        };        AStarNode startNode = new AStarNode(0, 0, false);        AStarNode endNode = new AStarNode(4, 4, false);        AStar astar = new AStar(grid);        List<AStarNode> path = astar.FindPath(startNode, endNode);        if (path != null)        {            foreach (AStarNode node in path)            {                Console.WriteLine("({0}, {1})", node.X, node.Y);            }        }        else        {            Console.WriteLine("No path found.");        }    }}

在这个示例中,我们首先定义了一个AStarNode类来表示A算法中的节点。

每个节点都有一个X和Y坐标,一个布尔值来表示是否为墙,以及G、H和F值用于计算路径的成本。

我们还定义了一个AStar类来实现A算法的逻辑。

AStar类中,我们使用开放列表和关闭列表来跟踪已经访问过的节点和待访问的节点。

FindPath()方法使用A*算法来查找从起始节点到目标节点的最短路径。

我们使用GetLowestFScoreNode()方法来获取开放列表中F值最低的节点,

使用GetNeighbors()方法来获取一个节点的邻居节点,

使用CalculateHScore()方法来计算一个节点到目标节点的启发式估计值H,

使用GeneratePath()方法来生成最终的路径。

Main()方法中,我们创建一个网格表示迷宫,其中0表示可通过的路径,1表示墙。

然后我们创建一个AStar对象,

并使用FindPath()方法来查找从起始节点到目标节点的最短路径。

如果找到了路径,我们将打印出路径上的节点坐标。

否则,我们将打印出"No path found."。

这只是一个简单的示例,实际的A*算法实现可能需要更复杂的逻辑和数据结构来处理

标签: #a算法算法 #astar算法简单 #a star寻路 #最优路径c语言实现方法 #最优路径c语言实现方法有哪些