A*算法的C#实现

     在游戏开发中，AI的最基本问题之一就是寻路算法或称路径规划算法，在三年前，我曾实现过基于“图算法”的最短路径规划算法，然而在游戏中，我们通常将地图抽象为有单元格构成的矩形，如：

          （本图源于这里）

     这个微型地图由3*3的单元格构成，当然，实际游戏中的地图通常比它大很多，这里只是给出一个示例。

     由于游戏地图通常由单元格构成，所以，基于“图算法”的路径规划便不再那么适用，我们需要采用基于单元格的路径规划算法。A*算法是如今游戏所采用的寻路算法中相当常用的一种算法，它可以保证在任何起点和任何终点之间找到最佳的路径（如果存在的话），而且，A*算法相当有效。

     关于A*算法的原理的详细介绍，可以参考这篇文章。当你明白A*算法的原理之后，在来看接下来的A*算法的实现就会比较容易了。

     现在，让我们转入正题，看看如何在C#中实现A*算法。

     首先，我们把地图划分为单元格，如此，一个地图就可以由（M行*N列）个单元格构成。我们使用AStarNode类来抽象单元格，表示一个节点，而节点的位置用Point表示，其X坐标表示Column Index，Y坐标表示Line Index。AStarNode的定义如下：

/// <summary>
    /// AStarNode 用于保存规划到当前节点时的各个Cost值以及父节点。
    /// zhuweisky 2008.10.18
    /// </summary>
    public class AStarNode
    {
        #region Ctor
        public AStarNode(Point loc, AStarNode previous, int _costG, int _costH)
        {
            this.location = loc;
            this.previousNode = previous;
            this.costG = _costG;
            this.costH = _costH;
        }
        #endregion

        #region Location
        private Point location = new Point(0, 0);
        /// <summary>
        /// Location 节点所在的位置，其X值代表ColumnIndex，Y值代表LineIndex
        /// </summary>
        public Point Location
        {
            get { return location; }
        } 
        #endregion       

        #region PreviousNode
        private AStarNode previousNode = null;
        /// <summary>
        /// PreviousNode 父节点，即是由哪个节点导航到当前节点的。
        /// </summary>
        public AStarNode PreviousNode
        {
            get { return previousNode; }
        }
        #endregion

        #region CostF
        /// <summary>
        /// CostF 从起点导航经过本节点然后再到目的节点的估算总代价。
        /// </summary>
        public int CostF
        {
            get
            {
                return this.costG + this.costH;
            }
        }
        #endregion

        #region CostG
        private int costG = 0;
        /// <summary>
        /// CostG 从起点导航到本节点的代价。
        /// </summary>
        public int CostG
        {
            get { return costG; }
        }
        #endregion

        #region CostH
        private int costH = 0;
        /// <summary>
        /// CostH 使用启发式方法估算的从本节点到目的节点的代价。
        /// </summary>
        public int CostH
        {
            get { return costH; }
        }
        #endregion

        #region ResetPreviousNode
        /// <summary>
        /// ResetPreviousNode 当从起点到达本节点有更优的路径时，调用该方法采用更优的路径。
        /// </summary>        
        public void ResetPreviousNode(AStarNode previous, int _costG)
        {
            this.previousNode = previous;
            this.costG = _costG;         
        }
        #endregion

        public override string ToString()
        {
            return this.location.ToString();
        }
    }

     如果，你看过上面提到的那篇参考文章，那么类中的各个属性的定义就不难理解了。

     我们假设，从某个节点出发，最多可以有8个方向移动，这8个方向定义为CompassDirections：

    public enum CompassDirections
    {
        NotSet = 0,
        North = 1, //UP
        NorthEast = 2, //UP Right
        East = 3,
        SouthEast = 4,
        South = 5,
        SouthWest = 6,
        West = 7,
        NorthWest = 8
    }

     CompassDirections遵守“左西右东，上北下南”的地图方位原则。

     而从某个节点出发，朝8个方向之中的某个方向移动是有代价（Cost）的，而且朝每个方向移动的代价可能是不相同的，而我们的寻路算法正是要找到起点和终点之间总代价最小的路径。我们使用一个接口ICostGetter来获取从某个节点开始朝8个方向移动的代价值。 

     /// <summary>
    /// ICostGetter 获取从当前节点向某个方向移动时的代价。
    /// </summary>
    public interface ICostGetter
    {
        int GetCost(Point currentNodeLoaction, CompassDirections moveDirection);
    }

     之所以将其定义为接口，是因为不同的游戏中的对移动代价赋值是不一样的。不同的游戏可以自己实现这个接口，以表明自己的代价赋值策略。

     尽管如此，我们还是给出一个最简单的ICostGetter实现以方便我们测试，这个实现表示从当前节点向上、下、左、右四个方向的移动的代价是一样的。 

 

    /// <summary>
    /// SimpleCostGetter ICostGetter接口的简化实现。直线代价为10， 斜线为14。
    /// </summary>
    public class SimpleCostGetter : ICostGetter
    {
        #region ICostGetter 成员

        public int GetCost(Point currentNodeLoaction, CompassDirections moveDirection)
        {
            if (moveDirection == CompassDirections.NotSet)
            {
                return 0;
            }

            if (moveDirection == CompassDirections.East || moveDirection == CompassDirections.West || moveDirection == CompassDirections.South || moveDirection == CompassDirections.North)
            {
                return 10;
            }

            return 14;
        }

        #endregion
    }

 

     我们知道，如果定义上、下、左、右的代价为1，那么斜线的代价应为根号2，为了提高计算效率，我们将根号2取近似值为1.4，并将单位放大10倍（计算机对整数的运算比对浮点数的运算要快很多）。

     我们还需要一个结构来保存在路径规划过程中的中间结果：

    /// <summary>
    /// RoutePlanData 用于封装一次路径规划过程中的规划信息。
    /// </summary>
    public class RoutePlanData
    {
        #region CellMap
        private Rectangle cellMap;
        /// <summary>
        /// CellMap 地图的矩形大小。经过单元格标准处理。
        /// </summary>
        public Rectangle CellMap
        {
            get { return cellMap; }
        } 
        #endregion

        #region ClosedList
        private IList<AStarNode> closedList = new List<AStarNode>();
        /// <summary>
        /// ClosedList 关闭列表，即存放已经遍历处理过的节点。
        /// </summary>
        public IList<AStarNode> ClosedList
        {
            get { return closedList; }
        } 
        #endregion

        #region OpenedList
        private IList<AStarNode> openedList = new List<AStarNode>();
        /// <summary>
        /// OpenedList 开放列表，即存放已经开发但是还未处理的节点。
        /// </summary>
        public IList<AStarNode> OpenedList
        {
            get { return openedList; }
        } 
        #endregion

        #region Destination
        private Point destination;
        /// <summary>
        /// Destination 目的节点的位置。
        /// </summary>
        public Point Destination
        {
            get { return destination; }           
        } 
        #endregion

        #region Ctor
        public RoutePlanData(Rectangle map, Point _destination)
        {
            this.cellMap = map;
            this.destination = _destination;
        } 
        #endregion
    }

     

     有了上述这些基础结构，我们便可以开始实现算法的核心功能了：   

 

 /// <summary>
    /// AStarRoutePlanner A*路径规划。每个单元格Cell的位置用Point表示
    /// F = G + H 。
    /// G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。
    /// H = 从网格上那个方格移动到终点B的预估移动耗费。使用曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。
    /// zhuweisky 2008.10.18
    /// </summary>
    public class AStarRoutePlanner
    {
        private int lineCount = 10;   //反映地图高度，对应Y坐标
        private int columnCount = 10; //反映地图宽度，对应X坐标
        private ICostGetter costGetter = new SimpleCostGetter();
        private bool[][] obstacles = null; //障碍物位置，维度：Column * Line         

        #region Ctor
        public AStarRoutePlanner() :this(10 ,10 ,new SimpleCostGetter())
        {           
        }
        public AStarRoutePlanner(int _lineCount, int _columnCount, ICostGetter _costGetter)
        {
            this.lineCount = _lineCount;
            this.columnCount = _columnCount;
            this.costGetter = _costGetter;

            this.InitializeObstacles();
        }

        /// <summary>
        /// InitializeObstacles 将所有位置均标记为无障碍物。
        /// </summary>
        private void InitializeObstacles()
        {
            this.obstacles = new bool[this.columnCount][];
            for (int i = 0; i < this.columnCount; i++)
            {
                this.obstacles[i] = new bool[this.lineCount];
            }

            for (int i = 0; i < this.columnCount; i++)
            {
                for (int j = 0; j < this.lineCount; j++)
                {
                    this.obstacles[i][j] = false;
                }
            }
        }
        #endregion

        #region Initialize
        /// <summary>
        /// Initialize 在路径规划之前先设置障碍物位置。
        /// </summary>        
        public void Initialize(IList<Point> obstaclePoints)
        {
            if (obstacles != null)
            {
                foreach (Point pt in obstaclePoints)
                {
                    this.obstacles[pt.X][pt.Y] = true;
                }
            }
        } 
        #endregion

        #region Plan
        public IList<Point> Plan(Point start, Point destination)
        {
            Rectangle map = new Rectangle(0, 0, this.columnCount, this.lineCount);
            if ((!map.Contains(start)) || (!map.Contains(destination)))
            {
                throw new Exception("StartPoint or Destination not in the current map!");
            }

            RoutePlanData routePlanData = new RoutePlanData(map, destination);

            AStarNode startNode = new AStarNode(start, null, 0, 0);
            routePlanData.OpenedList.Add(startNode);

            AStarNode currenNode = startNode;

            //从起始节点开始进行递归调用
            return DoPlan(routePlanData, currenNode);
        } 
        #endregion

        #region DoPlan
        private IList<Point> DoPlan(RoutePlanData routePlanData, AStarNode currenNode)
        {
            IList<CompassDirections> allCompassDirections = CompassDirectionsHelper.GetAllCompassDirections();
            foreach (CompassDirections direction in allCompassDirections)
            {
                Point nextCell = GeometryHelper.GetAdjacentPoint(currenNode.Location, direction);
                if (!routePlanData.CellMap.Contains(nextCell)) //相邻点已经在地图之外
                {
                    continue;
                }

                if (this.obstacles[nextCell.X][nextCell.Y]) //下一个Cell为障碍物
                {
                    continue;
                }

                int costG = this.costGetter.GetCost(currenNode.Location, direction);
                int costH = Math.Abs(nextCell.X - routePlanData.Destination.X) + Math.Abs(nextCell.Y - routePlanData.Destination.Y);
                if (costH == 0) //costH为0，表示相邻点就是目的点，规划完成，构造结果路径
                {
                    IList<Point> route = new List<Point>();
                    route.Add(routePlanData.Destination);
                    route.Insert(0, currenNode.Location);
                    AStarNode tempNode = currenNode;
                    while (tempNode.PreviousNode != null)
                    {
                        route.Insert(0, tempNode.PreviousNode.Location);
                        tempNode = tempNode.PreviousNode;
                    }

                    return route;
                }

                AStarNode existNode = this.GetNodeOnLocation(nextCell, routePlanData);
                if (existNode != null)
                {
                    if (existNode.CostG > costG)
                    {
                        //如果新的路径代价更小，则更新该位置上的节点的原始路径
                        existNode.ResetPreviousNode(currenNode, costG);
                    }
                }
                else
                {
                    AStarNode newNode = new AStarNode(nextCell, currenNode, costG, costH);
                    routePlanData.OpenedList.Add(newNode);
                }
            }

            //将已遍历过的节点从开放列表转移到关闭列表
            routePlanData.OpenedList.Remove(currenNode);
            routePlanData.ClosedList.Add(currenNode);

            AStarNode minCostNode = this.GetMinCostNode(routePlanData.OpenedList);
            if (minCostNode == null) //表明从起点到终点之间没有任何通路。
            {
                return null;
            }

            //对开放列表中的下一个代价最小的节点作递归调用
            return this.DoPlan(routePlanData, minCostNode);
        } 
        #endregion

        #region GetNodeOnLocation
        /// <summary>
        /// GetNodeOnLocation 目标位置location是否已存在于开放列表或关闭列表中
        /// </summary>       
        private AStarNode GetNodeOnLocation(Point location, RoutePlanData routePlanData)
        {
            foreach (AStarNode temp in routePlanData.OpenedList)
            {
                if (temp.Location == location)
                {
                    return temp;
                }
            }

            foreach (AStarNode temp in routePlanData.ClosedList)
            {
                if (temp.Location == location)
                {
                    return temp;
                }
            }

            return null;
        } 
        #endregion

        #region GetMinCostNode
        /// <summary>
        /// GetMinCostNode 从开放列表中获取代价F最小的节点，以启动下一次递归
        /// </summary>      
        private AStarNode GetMinCostNode(IList<AStarNode> openedList)
        {
            if (openedList.Count == 0)
            {
                return null;
            }

            AStarNode target = openedList[0];
            foreach (AStarNode temp in openedList)
            {
                if (temp.CostF < target.CostF)
                {
                    target = temp;
                }
            }

            return target;
        } 
        #endregion       
    }

  

     代码中已经加了详尽的注释，要注意的有以下几点：

1.Initialize方法用于初始化障碍物的位置，所谓“障碍物”，是指导航时无法穿越的物体，比如，游戏中的墙、河流等。

2.标记为红色的ResetPreviousNode方法调用处，说明，到达当前节点的当前路径比已存在的路径代价更小，所以要选择更优的路径。

3.标记为黑体的 route.Insert(0, tempNode.PreviousNode.Location);方法调用，表示已经找到最优路径，此处便可通过反向迭代的方式整理出从起点到终点的最终路径。

4.CostH 的计算使用曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。

5.在该算法中，至少还有一个地方可以优化，那就是GetMinCostNode方法所实现的内容，如果在路径搜索的过程中，我们就将OpenList中的各个节点按照Cost从小到大进行排序，那么每次GetMinCostNode时，就只需要取出第一个节点即可，而不必在遍历OpenList中的每一个节点了。在地图很大的时候，此法可以大幅提升算法效率。 

     最后，给出一个例子，感受一下：

            AStarRoutePlanner aStarRoutePlanner = new AStarRoutePlanner();
            IList<Point> obstaclePoints = new List<Point>();
            obstaclePoints.Add(new Point(2, 4));
            obstaclePoints.Add(new Point(3, 4));
            obstaclePoints.Add(new Point(4, 4));
            obstaclePoints.Add(new Point(5, 4));
            obstaclePoints.Add(new Point(6, 4));
            aStarRoutePlanner.Initialize(obstaclePoints);

            IList<Point> route = aStarRoutePlanner.Plan(new Point(3, 3), new Point(4, 6));

 

     运行后，返回的route结果如下：

     {3,3},  {2,3},  {1,3},   {1,4},  {1,5},  {2,5},  {2,6},  {3,6},  {4,6} 

 

2008-10-13：附上CompassDirectionsHelper和GeometryHelper源码。

    public static class CompassDirectionsHelper
    {
        private static IList<CompassDirections> AllCompassDirections = new List<CompassDirections>();

        #region Static Ctor
        static CompassDirectionsHelper()
        {
            CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.East);
            CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.West);
            CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.South);
            CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.North);

            CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.SouthEast);
            CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.SouthWest);
            CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.NorthEast);
            CompassDirectionsHelper.AllCompassDirections.Add(CompassDirections.NorthWest);
        } 
        #endregion

        #region GetAllCompassDirections
        public static IList<CompassDirections> GetAllCompassDirections()
        {
            return CompassDirectionsHelper.AllCompassDirections;
        }
        #endregion
    }

 

    public static class GeometryHelper
    {
        #region GetAdjacentPoint
        /// <summary>
        /// GetAdjacentPoint 获取某个方向上的相邻点
        /// </summary>       
        public static Point GetAdjacentPoint(Point current, CompassDirections direction)
        {
            switch (direction)
            {
                case CompassDirections.North:
                    {
                        return new Point(current.X, current.Y - 1);
                    }
                case CompassDirections.South:
                    {
                        return new Point(current.X, current.Y + 1);
                    }
                case CompassDirections.East:
                    {
                        return new Point(current.X + 1, current.Y);
                    }
                case CompassDirections.West:
                    {
                        return new Point(current.X - 1, current.Y);
                    }
                case CompassDirections.NorthEast:
                    {
                        return new Point(current.X + 1, current.Y - 1);
                    }
                case CompassDirections.NorthWest:
                    {
                        return new Point(current.X - 1, current.Y - 1);
                    }
                case CompassDirections.SouthEast:
                    {
                        return new Point(current.X + 1, current.Y + 1);
                    }
                case CompassDirections.SouthWest:
                    {
                        return new Point(current.X - 1, current.Y + 1);
                    }
                default:
                    {
                        return current;
                    }
            }
        }
        #endregion     
    }

 

时间： 2024-09-27 19:45:02

A*算法的C#实现的相关文章

python实现马耳可夫链算法实例分析

  本文实例讲述了python实现马耳可夫链算法的方法.分享给大家供大家参考.具体分析如下: 在<程序设计实践>(英文名<The Practice of Programming>)的书中,第三章分别用C语言,C++,AWK和Perl分别实现了马耳可夫链算法,来通过输入的文本,"随机"的生成一些有用的文本. 说明: 1. 程序使用了字典,字典和散列可不是一个东西,字典是键值对的集合,而散列是一种能够常数阶插入,删除,不过可以用散列来实现字典. 2. 字典的setd

php-perl哈希算法实现

 php-perl哈希实现算法–DJBX33A(Daniel J. Bernstein, Times 33 with Addition)APR哈希默认算法  代码如下: APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key,                                                       apr_ssize_t *klen) {     unsigned i

openssl使用DSA算法生成签名

  命令: openssl> dgst -dss1 -sign C.pri -out signature.bin s.txt 解释 C.pri是DSA算法生成的私钥文件 s.txt是制作签名的原文 signature.bin是生成的签名文件 php中可以使用下面的方法察看签名内容  代码如下   <?php echo bin2hex(file_get_contents('signature.bin')); ?> 参考内容 消息摘要算法 支持的算法包括:MD2, MD4, MD5, MDC

求按百分比抽取数据算法

问题描述 求按百分比抽取数据算法 我有个需求 要求用百分比抽取数据以达到数据审阅的目的 我做了一个简单的程序但达不到要求 <?php header('Content-Type: text/html; charset=utf-8'); //抽取算法 for($kou=1;$kou<=100;$kou++){ $kou_count=0; for($i=1;$i<=100;$i++){ $key=($i)%(100/$kou); if( intval( $key ) == 0){ //echo

请教各位算法大神，acm一道题：赋权无向图的最小权值遍历用什么算法（存在负权值）？

问题描述 请教各位算法大神,acm一道题:赋权无向图的最小权值遍历用什么算法(存在负权值)? 1C 如题,问题是这样的:有一赋权无向连通图,可以从任意一结点出发,求遍历所有结点的最小权值路线.结束点也是任意的,每个节点也没有访问次数的限制,但必须每个节点都要被访问到.,想问一下用什么算法呢? 解决方案 可以参考djstera算法,求最短路径~借鉴其中的标记功能,只不过结束状态标志是所有节点均已遍历. 解决方案二: 可以参考djstera算法,求最短路径~借鉴其中的标记功能,只不过结束状态标志是所

RSA算法介绍

2.1.1     算法实现 首先, 找出三个数, p, q, r,其中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数.p, q, r 这三个数便是 private key 接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1) 这个 m 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了 再来, 计算 n = pq m, n 这两个数便是 public key 编码过程是, 若资料为 a, 将其看成是一个大整数, 假设 a

PHP 四种基本排序算法的代码实现(1)

许多人都说算法是程序的核心,算法的好坏决定了程序的质量.作为一个初级phper,虽然很少接触到算法方面的东西.但是对于基本的排序算法还是应该掌握的,它是程序开发的必备工具.这里介绍冒泡排序,插入排序,选择排序,快速排序四种基本算法,分析一下算法的思路. 前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序. $arr(1,43,54,62,21,66,32,78,36,76,39); 1. 冒泡排序 思路分析:在要排序的一组数中,对当前还未排好的序

二叉树遍历算法之一：前序遍历

递归实现前序遍历 二叉树的前序遍历是指从根节点出发,按照先根节点,再左子树,后右子树的方法遍历二叉树中的所有节点,使得每个节点都被访问一次. 当调用遍历算法的时候前序遍历的具体过程如下: 首先访问根节点,如果根节点不为空,执行输出语句,打印根节点的值. 如果左子树不为空,则访问根节点的左孩子,并输出根节点做孩子的值 继续访问根节点的左孩子的左孩子,如果不为空则继续输出该左孩子的值: 如果这时左孩子为空,说明该节点是叶子节点,则按照先左孩子后右孩子的访问方式访问其左右孩子,如果不为空就打印输出 左

图的生成树（森林）（克鲁斯卡尔Kruskal算法和普里姆Prim算法）、以及并查集的使用

图的连通性问题:无向图的连通分量和生成树,所有顶点均由边连接在一起,但不存在回路的图. 设图 G=(V, E) 是个连通图,当从图任一顶点出发遍历图G 时,将边集 E(G) 分成两个集合 T(G) 和 B(G).其中 T(G)是遍历图时所经过的边的集合,B(G) 是遍历图时未经过的边的集合.显然,G1(V, T) 是图 G 的极小连通子图,即子图G1 是连通图 G 的生成树. 深度优先生成森林   右边的是深度优先生成森林: 连通图的生成树不一定是唯一的,不同的遍历图的方法得到不同的生成树;从不

不用递归实现论坛树型结构的算法

递归|树型结构|算法 <jsp:useBean id="mybbs" scope="session" class="netzero.mydb" /> <%@ page contentType="text/html;charset=gb2312" %> <%@ page import="java.io.*" %> <%@ page import="java.