a星算法 订阅
A*搜寻算法俗称A星算法。A*算法是比较流行的启发式搜索算法之一,被广泛应用于路径优化领域[。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价该节点处于最短路线上的可能性的量度。 [1] 展开全文
A*搜寻算法俗称A星算法。A*算法是比较流行的启发式搜索算法之一,被广泛应用于路径优化领域[。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价该节点处于最短路线上的可能性的量度。 [1]
信息
外文名
A-star Algorithm
类    型
求出最低通过成本的算法
别    名
A星算法
中文名
A*搜寻算法
应用领域
图最优路径搜索/查找
A*搜寻算法算法描述
A*改变它自己行为的能力基于启发式代价函数,启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中,你并不真正需要得到最好的路径,仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么,或者运行游戏的机器有多快。 假设你的游戏有两种地形,平原和山地,在平原中的移动代价是1而在山地的是3,那么A星算法就会认为在平地上可以进行三倍于山地的距离进行等价搜寻。 这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较,这并不比把3和1比较差。然而,在山地上行动有时可能会优于绕过山脚下进行行动。所以花费更多时间寻找一个绕过山的算法并不经常是可靠的。 同样的,想要达成这样的目标,你可以通过减少在山脚下的搜索行为来打到提高A星算法的运行速率。若想如此可以将A星算法的山地行动耗费从3调整为2即可。这两种方法都会给出可靠地行动策略。用C语言实现A*最短路径搜索算法,作者 Tittup frog(跳跳蛙)。
收起全文
精华内容
下载资源
问答
  • A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法A星算法
  • A星算法

    千次阅读 2018-10-25 16:19:03
    花了1天时间,看了很多前辈的A星算法思路,终于完成A星算法。 完成A*算法,首先要理解A星算法的原理,A星算法擅长解决方块类路径的寻路问题,以起始点的方块为起点,向该方块周围的方块进行探测&计算,...

    花了1天时间,看了很多前辈的A星算法思路,终于完成A星算法。

    完成A*算法,首先要理解A星算法的原理,A星算法擅长解决方块类路径的寻路问题,以起始点的方块为起点,向该方块周围的方块进行探测&计算,以(为该起点周围需要探测的每个砖块赋予数据,并对数据进行比较,然后确认下一个可能移动的砖块,并以它作为下一个起始点,重复以上操作)为原理,直到找到路径终点为止,并通过路径之间的类似链表结构,从终点方块遍历到起点方块,并记录中途所有路径方块,然后让寻路者沿着记录的路径的所有方块逐一移动,直到终点为止。

    A星算法 要赋予每个地图砖块几个变量

    1.曼哈顿距离(A星算法曼哈顿比较容易入门)-------H
    https://baike.so.com/doc/2753904-2906430.html
    链接来源百科

       H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )
    

    通俗易懂的二维公式:d(i,j)=|X1-X2|+|Y1-Y2|

    (曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离,即D(I,J)=|XI-XJ|+|YI-YJ|。对于一个具有正南正北、正东正西方向规则布局的城镇街道,从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离因此曼哈顿距离又称为出租车距离,曼哈顿距离不是距离不变量,当坐标轴变动时,点间的距离就会不同——百度知道)

    1. 距离真正的起始点的移动的步数(按照多少个砖块来算)-----G
      起始点第一次周围的砖块的G值为1( 因为起始点是0 )如果找到第二个点作为新的起始点,那么这个点的周围不包括真正的起始点的砖块(点)的G值为2

    2. G+H的和 -------F
      用于比较各个砖块的F的值

    4.open列表 ------List<地图的砖块对象> open
    用于存储在不断的搜寻新起始点的过程中,收集到的起始点周围砖块的信息
    用于遍历Open列表中所有砖块F的值,来确定下一个起始点,也可以作为某一方向的寻路过程中,遇到墙壁后重新找新路时,遍历之前的所有可行的点,找F值最小的点来作为新的,下一个起始点,继续寻路

    5.close列表 ------List<地图的砖块对象> close
    用于存储在不断的搜寻新起始点的过程中,曾经当过起始点的所有砖块,避免在寻路过程中遭遇重复点(重复路径)

    里面还有很多关键点,代码都有注释,由于我也是第一次尝试,所以写下了也是怕自己忘记了

    在这里插入图片描述
    自动生成地图和角色立方体的代码

    这里需要2个放在Resources文件夹下的预制体 一个是生成地图用的 命名为Cube1,一个是生成主角的 命名为A

    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    
    //每个地图砖块赋予的属性
    public class OnePoint
    {
        public float F;
        public int G;
        public float H;
        public Vector3 curPoint = new Vector3(1000, 1000, 1000);
        public OnePoint father;//父级
        public OnePoint(Vector3 curPoint)
        {
            F = 99999;
            G = 99999;
            H = 99999;
            this.curPoint = curPoint;
        }
        public void Reset()
        {
            F = 99999;
            G = 99999;
            H = 99999;
            this.father = null;
        }
    }
    
    
    public class DiTu : MonoBehaviour
    {
    
        public GameObject cube;
    
        public List<OnePoint> pointList = new List<OnePoint>();
        public Dictionary<Vector3, OnePoint> dic = new Dictionary<Vector3, OnePoint>();
        public static DiTu instance;
        public int x;
        public int z;
        IEnumerator CreatePaths(int x = 1, int y = 1)
        {
            for (int i = 0; i < z; i++)
            {
                for (int j = 0; j < x; j++)
                {
                    GameObject go = Instantiate<GameObject>(Resources.Load<GameObject>("Cube1"), transform.position + new Vector3(j, 0, i), Quaternion.identity);
                    //GameObject go = CreateCubeGo(j, i, transform.position);
                    OnePoint temp = new OnePoint(go.transform.position + Vector3.up);
                    int num = Random.Range(0, 11);
    
                    if (num < 8 || (i == 0 && j == 0))
                    {
                        pointList.Add(temp);
                        dic.Add(go.transform.position + Vector3.up, temp);
                        go.tag = "ditu";
                    }
                    else
                    {
                        go.GetComponent<MeshRenderer>().materials[0].color = Color.black;
                    }
                }
            }
            yield return 0;
            //地图创建好后,创建主角
            GameObject player = Instantiate<GameObject>(Resources.Load<GameObject>("A"), transform.position, Quaternion.identity);
            player.name = "A";
            player.transform.position += Vector3.up;
            player.GetComponent<MeshRenderer>().materials[0].color = Color.yellow;
            //创建好主角后,给主角绑定摄像机
            Camera.main.transform.parent = player.transform;
        }
        private void Awake()
        {
            instance = this;
            StartCoroutine(CreatePaths(x, z));
        }
    
    }
    
    

    接下来是挂载在玩家 A 预制体上的脚本

    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    using System.Threading;
    
    
    public class AstarCacular : MonoBehaviour
    {
    
        //鼠标点击
        Ray ray;
        List<OnePoint> open = new List<OnePoint>();
        List<OnePoint> close = new List<OnePoint>();
        //是否找到
        bool isFind = false;
        //地图字典
        Dictionary<Vector3, OnePoint> dic;
        OnePoint curOnePoint;
        OnePoint targetPoint;
        List<Vector3> paths = new List<Vector3>();
        Vector3 target;
        int index = 0;
        // Use this for initialization
        private void Awake()
        {
            target = new Vector3(9, 1, 9);
        }
        void Start()
        {
            this.transform.position = new Vector3(0, 1, 0);
            dic = DiTu.instance.dic;
            curG = 0;
            int length = DiTu.instance.pointList.Count;
            List<OnePoint> temp = DiTu.instance.pointList;
            for (int i = 0; i < length; i++)
            {
                if (transform.position == temp[i].curPoint)
                {
                    curOnePoint = temp[i];
                    curOnePoint.curPoint = transform.position;
                    curOnePoint.father = null;
                    curOnePoint.G = 0;
                    //
                    open.Add(curOnePoint);
                    break;
                }
            }
        }
        bool checkFinish = false;
        bool canFind = true;
    
        float ti = 0;
        private void FixedUpdate()
        {
            if (!isFind)
            {
                ti ++;
            }
            else
            {
                Debug.Log("ti: " + ti);
            }
        }
        // Update is called once per frame
        void Update()
        {
            MouseButtonDown();
            if (canFind)
            {
                
                if (!isFind)
                {
                    ForeachOpenList(this.target);
                }
                else
                {
                    Debug.Log("!");
                    if (targetPoint != null)
                    {
                        while (targetPoint.father != null)//找到反向路径,并用paths记录
                        {
                            paths.Add(targetPoint.curPoint);
                            targetPoint = targetPoint.father;
                        }
                        if (targetPoint.father == null && checkFinish == false)//设置初始路径索引
                        {
                            checkFinish = true;
                            index = paths.Count - 1;
                        }
                        if (index < 0)
                        {
                            canFind = false;
                            return;
                        }
                        transform.position = Vector3.Lerp(transform.position, paths[index], 0.5f);
                        if (Vector3.Distance(transform.position, paths[index]) < 0.1f)
                        {
                            transform.position = paths[index];
                            index--;
                        }
                    }
                }
            }
        }
    void ForeachOpenList(Vector3 target)
        {
            if (open.Count <= 0)
            {
                Debug.Log("open列表为空");
                return;
            }
            var minF = open[0].F;
            var point = open[0];
            //找到最小F对应point
            for (int i = 0; i < open.Count; i++)
            {
                if (open[i].F < minF)
                {
                    point = open[i];
                }
            }
            //将该点添加进close列表中
            close.Add(point);
            //将该点从open列表中移除
            open.Remove(point);
            //分析该砖块周围的方格
            #region 闲置
            //List<OnePoint> points4 = new List<OnePoint>(4); 
            #endregion
    
            //对各方位的砖块做判断的变量
            short upNum = 0;//上
            short downNum = 0;//下
            short leftNum = 0;//左
            short rightNum = 0;//右
            //short ruNum = 0;//右上
            //short rdNum = 0;//右下
            //short luNum = 0;//左上
            //short ldNum = 0;//左下
    
            处理上下左右四个方向的点
    
            CaculateUpDir(upNum, point);
            CaculateDownDir(downNum, point);
            CaculateLeftDir(leftNum, point);
            CaculateRightDir(rightNum, point);
    
            if (isFind)
            {
                Debug.Log("找到目标");
            }
            if (open.Count <= 0 && isFind == false)//查找失败
            {
                Debug.Log("查找失败");
            }
        }//传统A*
        void MouseButtonDown()
        {
            if (Input.GetMouseButtonDown(0))
            {
                var x = Mathf.Ceil(transform.position.x);
                var y = Mathf.Ceil(transform.position.y);
                var z = Mathf.Ceil(transform.position.z);
                transform.position = new Vector3(x, y, z);
    
                ray = Camera.main.ScreenPointToRay(Input.mousePosition);
                RaycastHit hit;
                if (Physics.Raycast(ray, out hit))
                {
                    if (hit.collider.tag == "ditu")
                    {
                        //进行一次新的路径查找
                        //清除列表状态
                        open.Clear();
                        close.Clear();
                        paths.Clear();
                        //获取地图的点的数量
                        int length = DiTu.instance.pointList.Count;
                        List<OnePoint> temp = DiTu.instance.pointList;
                        //清除所有点的状态
                        for (int i = 0; i < length; i++)
                        {
                            temp[i].Reset();//恢复出厂设定
                        }
                        #region 找到当前点,重置当前初始点给新的空open,并对isFind/canFind/checkFinish/index/当前点curPoint的curPoint/fater/G进行重置
                        for (int i = 0; i < length; i++)
                        {
                            if (transform.position == temp[i].curPoint)
                            {
                                curOnePoint = temp[i];
                                curOnePoint.curPoint = transform.position;
                                curOnePoint.father = null;
                                curOnePoint.G = 0;
                                
                                open.Add(curOnePoint);
                                isFind = false;
                                canFind = true;
                                checkFinish = false;
                                index = 0;
                                //Debug.Log("curOnePoint.curPoint:" + transform.position);
                                //获取目标
                                this.target = hit.transform.position + Vector3.up;
                                //Debug.Log("target: " + target);
                                break;
                            }
                        }
                        #endregion
                    }
                }
            }
        }
    
    
        void CaculateUpDir(short upNum, OnePoint point)
        {
            #region 分析上面的方格
            //是否可抵达
            Vector3 up = point.curPoint + Vector3.forward;
            if (dic.ContainsKey(up))
            {
                //分析是不是终点
                if (up == target)
                {
                    dic[up].father = point;
                    open.Add(dic[up]);
                    targetPoint = dic[target];
                    isFind = true;
                }
                else//还不是终点
                {
                    //分析是否是close列表中的点
                    if (close.Count > 0)
                    {
                        for (int i = 0; i < close.Count; i++)
                        {
                            if (dic[up] == close[i])
                            {
                                upNum = -1;
                                break;
                            }
                        }
                    }
                    if (upNum < 0)
                    {
                        //该方向计算结束
                    }
                    else//该点可抵达并且不在close列表中
                    {
                        upNum = 1;
                        var temp = 1;
                        if (open.Count > 0)//判断该点是否在open列表中
                        {
                            for (int i = 0; i < open.Count; i++)
                            {
                                if (up == open[i].curPoint)
                                {
                                    temp = -1;
                                    break;
                                }
                            }
                        }
                        if (temp > 0)//如果不在,将该点添加到open中
                        {
                            dic[up].father = point;//该点的父级为之前的点
                            dic[up].G = dic[up].father.G + 1;//该点的G为父级的G加1
                                                             //曼哈顿算法
                            dic[up].H = Mathf.Abs(up.x - target.x) + Mathf.Abs(up.z - target.z);
                            //F求和
                            dic[up].F = dic[up].H + dic[up].G;
                            open.Add(dic[up]);
                        }
                        else if (temp < 0)//如果在open列表中
                        {
                            if (dic[up].G > dic[up].father.G + 1)
                            {
                                dic[up].father = point;//该点的父级为之前的点
                                dic[up].G = dic[up].father.G + 1;//该点的G为父级的G加1
                                                                 //F求和
                                dic[up].F = dic[up].H + dic[up].G;
                            }
                        }
                    }
                }
            }
            #endregion
        }
        void CaculateDownDir(short downNum, OnePoint point)
        {
            #region 分析下面的方格
            //是否可抵达
            Vector3 down = point.curPoint - Vector3.forward;
            if (dic.ContainsKey(down))
            {
                //分析是不是终点
                if (down == target)
                {
                    dic[down].father = point;
                    open.Add(dic[down]);
                    targetPoint = dic[target];
                    isFind = true;
                }
                else//还不是终点
                {
                    //分析是否是close列表中的点
                    if (close.Count > 0)
                    {
                        for (int i = 0; i < close.Count; i++)
                        {
                            if (dic[down] == close[i])
                            {
                                downNum = -1;
                                break;
                            }
                        }
                    }
                    if (downNum < 0)
                    {
                        //该方向计算结束
                    }
                    else//该点可抵达并且不在close列表中
                    {
                        downNum = 1;
                        var temp = 1;
                        if (open.Count > 0)//判断该点是否在open列表中
                        {
                            for (int i = 0; i < open.Count; i++)
                            {
                                if (down == open[i].curPoint)
                                {
                                    temp = -1;
                                    break;
                                }
                            }
                        }
                        if (temp > 0)//如果不在,将该点添加到open中
                        {
                            dic[down].father = point;//该点的父级为之前的点
                            dic[down].G = dic[down].father.G + 1;//该点的G为父级的G加1
                                                                 //曼哈顿算法
                            dic[down].H = Mathf.Abs(down.x - target.x) + Mathf.Abs(down.z - target.z);
                            //F求和
                            dic[down].F = dic[down].H + dic[down].G;
                            open.Add(dic[down]);
                        }
                        else if (temp < 0)//如果在open列表中
                        {
                            if (dic[down].G > dic[down].father.G + 1)
                            {
                                dic[down].father = point;//该点的父级为之前的点
                                dic[down].G = dic[down].father.G + 1;//该点的G为父级的G加1
                                                                     //F求和
                                dic[down].F = dic[down].H + dic[down].G;
                            }
                        }
                    }
                }
            }
            #endregion
        }
        void CaculateLeftDir(short leftNum, OnePoint point)
        {
            #region 分析左边的方格
            //是否可抵达
            Vector3 left = point.curPoint + Vector3.left;
            if (dic.ContainsKey(left))
            {
                //分析是不是终点
                if (left == target)
                {
                    dic[left].father = point;
                    open.Add(dic[left]);
                    targetPoint = dic[target];
                    isFind = true;
                }
                else//还没到终点
                {
                    //分析是否是close列表中的点
                    if (close.Count > 0)
                    {
                        for (int i = 0; i < close.Count; i++)
                        {
                            if (dic[left] == close[i])
                            {
                                leftNum = -1;
                                break;
                            }
                        }
                    }
                    if (leftNum < 0)
                    {
                        //该方向计算结束
                    }
                    else//该点可抵达并且不在close列表中
                    {
                        leftNum = 1;
                        var temp = 1;
                        if (open.Count > 0)//判断该点是否在open列表中
                        {
                            for (int i = 0; i < open.Count; i++)
                            {
                                if (left == open[i].curPoint)
                                {
                                    temp = -1;
                                    break;
                                }
                            }
                        }
                        if (temp > 0)//如果不在,将该点添加到open中
                        {
                            dic[left].father = point;//该点的父级为之前的点
                            dic[left].G = dic[left].father.G + 1;//该点的G为父级的G加1
                                                                 //曼哈顿算法
                            dic[left].H = Mathf.Abs(left.x - target.x) + Mathf.Abs(left.z - target.z);
                            //F求和
                            dic[left].F = dic[left].H + dic[left].G;
                            open.Add(dic[left]);
                        }
                        else if (temp < 0)//如果在open列表中
                        {
                            if (dic[left].G > dic[left].father.G + 1)
                            {
                                dic[left].father = point;//该点的父级为之前的点
                                dic[left].G = dic[left].father.G + 1;//该点的G为父级的G加1
                                                                     //F求和
                                dic[left].F = dic[left].H + dic[left].G;
                            }
                        }
                    }
                }
            }
            #endregion
        }
        void CaculateRightDir(short rightNum, OnePoint point)
        {
            #region 分析右边的方格
            //是否可抵达
            Vector3 right = point.curPoint + Vector3.right;
            if (dic.ContainsKey(right))
            {
                //分析是不是终点
                if (right == target)
                {
                    dic[right].father = point;
                    open.Add(dic[right]);
                    targetPoint = dic[target];
                    isFind = true;
                }
                else//还没到终点
                {
                    //分析是否是close列表中的点
                    if (close.Count > 0)
                    {
                        for (int i = 0; i < close.Count; i++)
                        {
                            if (dic[right] == close[i])
                            {
                                rightNum = -1;
                                break;
                            }
                        }
                    }
                    if (rightNum < 0)
                    {
                        //该方向计算结束
                    }
                    else//该点可抵达并且不在close列表中
                    {
                        rightNum = 1;
                        var temp = 1;
                        if (open.Count > 0)//判断该点是否在open列表中
                        {
                            for (int i = 0; i < open.Count; i++)
                            {
                                if (right == open[i].curPoint)
                                {
                                    temp = -1;
                                    break;
                                }
                            }
                        }
                        if (temp > 0)//如果不在,将该点添加到open中
                        {
                            dic[right].father = point;//该点的父级为之前的点
                            dic[right].G = dic[right].father.G + 1;//该点的G为父级的G加1
                                                                   //曼哈顿算法
                            dic[right].H = Mathf.Abs(right.x - target.x) + Mathf.Abs(right.z - target.z);
                            //F求和
                            dic[right].F = dic[right].H + dic[right].G;
                            open.Add(dic[right]);
                        }
                        else if (temp < 0)//如果在open列表中
                        {
                            if (dic[right].G > dic[right].father.G + 1)
                            {
                                dic[right].father = point;//该点的父级为之前的点
                                dic[right].G = dic[right].father.G + 1;//该点的G为父级的G加1
                                                                       //F求和
                                dic[right].F = dic[right].H + dic[right].G;
                            }
                        }
                    }
                }
            }
            #endregion
        }
    

    下面是脚本下载地址 共三个脚本
    https://pan.baidu.com/s/11hpbH5oMJ6h8krWg6ZCQkg

    运行须知:

    1. 创建Resources文件夹,里面放2个Cube预制体, 一个命名为 "Cube1"作为地图砖块 一个命名为"A"作为寻路体
    2. 添加tag ====> “ditu” , 把预制体 “Cube1” 的 tag 设置为"ditu"
    3. 预制体 “A” 挂载脚本 “AstarCacular”
    4. 游戏场景创建空物体 把脚本 “DiTu” 挂载上去 自己调整共有变量数值,来调整地图大小
    5. 摄像机随便写的代码,直接用的话,就把摄像机向上拖一段(把Y值变大些),把脚本 "CamLookAt"挂载上去,记住Main Camera 的tag 设置成自带的MainCamera
    展开全文
  • A* 寻路算法 原文地址:http://www.gamedev.net/reference/articles/article2003.asp 概述 虽然掌握了A*算法的人认为它容易,但是对于初学者来说,A*算法还是很复杂的。 搜索区域(The Search Area) 我们假设某人要...

    A* 寻路算法

    原文地址: http://www.gamedev.net/reference/articles/article2003.asp

    概述

    虽然掌握了 A* 算法的人认为它容易,但是对于初学者来说, A* 算法还是很复杂的。

    搜索区域(The Search Area)

    我们假设某人要从 A 点移动到 B 点,但是这两点之间被一堵墙隔开。如图 1 ,绿色是 A ,红色是 B ,中间蓝色是墙。

    image001.jpg

    图 1

    你应该注意到了,我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步,简化搜索区域,就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了 2 维数组。数组的每一项代表一个格子,它的状态就是可走 (walkalbe) 和不可走 (unwalkable) 。通过计算出从 A 到 B需要走过哪些方格,就找到了路径。一旦路径找到了,人物便从一个方格的中心移动到另一个方格的中心,直至到达目的地。

    方格的中心点我们成为“节点 (nodes) ”。如果你读过其他关于 A* 寻路算法的文章,你会发现人们常常都在讨论节点。为什么不直接描述为方格呢?因为我们有可能把搜索区域划为为其他多变形而不是正方形,例如可以是六边形,矩形,甚至可以是任意多变形。而节点可以放在任意多边形里面,可以放在多变形的中心,也可以放在多边形的边上。我们使用这个系统,因为它最简单。

    开始搜索(Starting the Search)

    一旦我们把搜寻区域简化为一组可以量化的节点后,就像上面做的一样,我们下一步要做的便是查找最短路径。在 A* 中,我们从起点开始,检查其相邻的方格,然后向四周扩展,直至找到目标。

    我们这样开始我们的寻路旅途:

    1.       从起点 A 开始,并把它就加入到一个由方格组成的 open list( 开放列表 ) 中。这个 open list 有点像是一个购物单。当然现在 open list 里只有一项,它就是起点 A ,后面会慢慢加入更多的项。 Open list 里的格子是路径可能会是沿途经过的,也有可能不经过。基本上 open list 是一个待检查的方格列表。

    2.       查看与起点 A 相邻的方格 ( 忽略其中墙壁所占领的方格,河流所占领的方格及其他非法地形占领的方格 ) ,把其中可走的 (walkable) 或可到达的 (reachable) 方格也加入到 open list 中。把起点 A 设置为这些方格的父亲 (parent node 或 parent square) 。当我们在追踪路径时,这些父节点的内容是很重要的。稍后解释。

    3.       把 A 从 open list 中移除,加入到 close list( 封闭列表 ) 中, close list 中的每个方格都是现在不需要再关注的。

    如下图所示,深绿色的方格为起点,它的外框是亮蓝色,表示该方格被加入到了 close list 。与它相邻的黑色方格是需要被检查的,他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点,这里是起点 A 。

    image002.jpg

    图 2 。

    下一步,我们需要从 open list 中选一个与起点 A 相邻的方格,按下面描述的一样或多或少的重复前面的步骤。但是到底选择哪个方格好呢?具有最小 F 值的那个。

     

    路径排序(Path Sorting)

    计算出组成路径的方格的关键是下面这个等式:

    F = G + H

    这里,

    G = 从起点 A 移动到指定方格的移动代价,沿着到达该方格而生成的路径。

    H = 从指定的方格移动到终点 B 的估算成本。这个通常被称为试探法,有点让人混淆。为什么这么叫呢,因为这是个猜测。直到我们找到了路径我们才会知道真正的距离,因为途中有各种各样的东西 ( 比如墙壁,水等 ) 。本教程将教你一种计算 H 的方法,你也可以在网上找到其他方法。

    我们的路径是这么产生的:反复遍历 open list ,选择 F 值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。

    如上所述, G 是从起点A移动到指定方格的移动代价。在本例中,横向和纵向的移动代价为 10 ,对角线的移动代价为 14 。之所以使用这些数据,是因为实际的对角移动距离是 2 的平方根,或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单起见。比例是对的,我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现,如果不使用这些技巧,寻路算法将很慢。

     

    既然我们是沿着到达指定方格的路径来计算 G 值,那么计算出该方格的 G 值的方法就是找出其父亲的 G 值,然后按父亲是直线方向还是斜线方向加上 10 或 14 。随着我们离开起点而得到更多的方格,这个方法会变得更加明朗。

     

    有很多方法可以估算 H 值。这里我们使用 Manhattan 方法,计算从当前方格横向或纵向移动到达目标所经过的方格数,忽略对角移动,然后把总数乘以 10 。之所以叫做 Manhattan 方法,是因为这很像统计从一个地点到另一个地点所穿过的街区数,而你不能斜向穿过街区。重要的是,计算 H 是,要忽略路径中的障碍物。这是对剩余距离的估算值,而不是实际值,因此才称为试探法。

     

    把 G 和 H 相加便得到 F 。我们第一步的结果如下图所示。每个方格都标上了 F , G , H 的值,就像起点右边的方格那样,左上角是 F ,左下角是 G ,右下角是 H 。

    image003.jpg

    图 3

    好,现在让我们看看其中的一些方格。在标有字母的方格, G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方,下方,左方的方格的 G 值都是 10 ,对角线的方格 G 值都是 14 。

     

    H 值通过估算起点于终点 ( 红色方格 ) 的 Manhattan 距离得到,仅作横向和纵向移动,并且忽略沿途的墙壁。使用这种方式,起点右边的方格到终点有 3 个方格的距离,因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ,因此 H = 40 。对于其他的方格,你可以用同样的方法知道 H 值是如何得来的。

     

    每个方格的 F 值,再说一次,直接把 G 值和 H 值相加就可以了。

     

    继续搜索(Continuing the Search)

    为了继续搜索,我们从 open list 中选择 F 值最小的 ( 方格 ) 节点,然后对所选择的方格作如下操作:

    4.       把它从 open list 里取出,放到 close list 中。

    5.       检查所有与它相邻的方格,忽略其中在 close list 中或是不可走 (unwalkable) 的方格 ( 比如墙,水,或是其他非法地形 ) ,如果方格不在open lsit 中,则把它们加入到 open list 中。

    把我们选定的方格设置为这些新加入的方格的父亲。

    6.       如果某个相邻的方格已经在 open list 中,则检查这条路径是否更优,也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。如果没有,不做任何操作。

    相反,如果 G 值更小,则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ,然后重新计算那个方格的 F 值和 G 值。如果你还是很混淆,请参考下图。

    image004.jpg

    图 4

    Ok ,让我们看看它是怎么工作的。在我们最初的 9 个方格中,还有 8 个在 open list 中,起点被放入了 close list 中。在这些方格中,起点右边的格子的 F 值 40 最小,因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。

     

    首先,我们把它从 open list 移到 close list 中 ( 这就是为什么用蓝线打亮的原因了 ) 。然后我们检查与它相邻的方格。它右边的方格是墙壁,我们忽略。它左边的方格是起点,在 close list 中,我们也忽略。其他 4 个相邻的方格均在 open list 中,我们需要检查经由这个方格到达那里的路径是否更好,使用 G 值来判定。让我们看看上面的方格。它现在的 G 值为 14 。如果我们经由当前方格到达那里, G 值将会为 20(其中 10 为到达当前方格的 G 值,此外还要加上从当前方格纵向移动到上面方格的 G 值 10) 。显然 20 比 14 大,因此这不是最优的路径。如果你看图你就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

     

    当把 4 个已经在 open list 中的相邻方格都检查后,没有发现经由当前方格的更好路径,因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格,并也对他们作了处理,是时候选择下一个待处理的方格了。

     

    因此再次遍历我们的 open list ,现在它只有 7 个方格了,我们需要选择 F 值最小的那个。有趣的是,这次有两个方格的 F 值都 54 ,选哪个呢?没什么关系。从速度上考虑,选择最后加入 open list 的方格更快。这导致了在寻路过程中,当靠近目标时,优先使用新找到的方格的偏好。但是这并不重要。 ( 对相同数据的不同对待,导致两中版本的 A* 找到等长的不同路径 ) 。

     

    我们选择起点右下方的方格,如下图所示。

    image005.jpg

    图 5

     

    这次,当我们检查相邻的方格时,我们发现它右边的方格是墙,忽略之。上面的也一样。

    我们把墙下面的一格也忽略掉。为什么?因为如果不穿越墙角的话,你不能直接从当前方格移动到那个方格。你需要先往下走,然后再移动到那个方格,这样来绕过墙角。 ( 注意:穿越墙角的规则是可选的,依赖于你的节点是怎么放置的 )

     

    这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入 open list ,所以把它们加入,同时把当前方格设为他们的父亲。在剩下的3 个方格中,有 2 个已经在 close list 中 ( 一个是起点,一个是当前方格上面的方格,外框被加亮的 ) ,我们忽略它们。最后一个方格,也就是当前方格左边的方格,我们检查经由当前方格到达那里是否具有更小的 G 值。没有。因此我们准备从 open list 中选择下一个待处理的方格。

     

    不断重复这个过程,直到把终点也加入到了 open list 中,此时如下图所示。

    image006.jpg

    图 6

     

    注意,在起点下面 2 格的方格的父亲已经与前面不同了。之前它的 G 值是 28 并且指向它右上方的方格。现在它的 G 值为 20 ,并且指向它正上方的方格。这在寻路过程中的某处发生,使用新路径时 G 值经过检查并且变得更低,因此父节点被重新设置, G 和 F 值被重新计算。尽管这一变化在本例中并不重要,但是在很多场合中,这种变化会导致寻路结果的巨大变化。

     

    那么我们怎么样去确定实际路径呢?很简单,从终点开始,按着箭头向父节点移动,这样你就被带回到了起点,这就是你的路径。如下图所示。从起点 A 移动到终点 B 就是简单从路径上的一个方格的中心移动到另一个方格的中心,直至目标。就是这么简单!

    image007.jpg

    图 7

     

    A*算法总结(Summary of the A* Method)

    Ok ,现在你已经看完了整个的介绍,现在我们把所有步骤放在一起:

    1.         把起点加入 open list 。

    2.         重复如下过程:

    a.         遍历 open list ,查找 F 值最小的节点,把它作为当前要处理的节点。

    b.         把这个节点移到 close list 。

    c.         对当前方格的 8 个相邻方格的每一个方格?

    ◆     如果它是不可抵达的或者它在 close list 中,忽略它。否则,做如下操作。

    ◆     如果它不在 open list 中,把它加入 open list ,并且把当前方格设置为它的父亲,记录该方格的 F , G 和 H 值。

    ◆     如果它已经在 open list 中,检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好,用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样,把它的父亲设置为当前方格,并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话,改变后你可能需要重新排序。

    d.         停止,当你

    ◆     把终点加入到了 open list 中,此时路径已经找到了,或者

    ◆     查找终点失败,并且 open list 是空的,此时没有路径。

    3.         保存路径。从终点开始,每个方格沿着父节点移动直至起点,这就是你的路径。

     

     

    题外话(Small Rant)

    请原谅我的离题,当你在网上或论坛上看到各种关于 A* 算法的讨论时,你偶尔会发现一些 A* 的代码,实际上他们不是。要使用 A* ,你必须包含上面讨论的所有元素 ---- 尤其是 open list , close list 和路径代价 G , H 和 F 。也有很多其他的寻路算法,这些算法并不是 A* 算法, A* 被认为是最好的。在本文末尾引用的一些文章中 Bryan Stout 讨论了他们的一部分,包括他们的优缺点。在某些时候你可以二中择一,但你必须明白自己在做什么。 Ok ,不废话了。回到文章。

     

    实现的注解(Notes on Implemetation)

    现在你已经明白了基本方法,这里是你在写自己的程序是需要考虑的一些额外的东西。下面的材料引用了一些我用 C++ 和 Basic 写的程序,但是对其他语言同样有效。

     

    1.    维护 Open List :这是 A* 中最重要的部分。每次你访问 Open list ,你都要找出具有最小    F 值的方格。有几种做法可以做到这个。你可以随意保存路径元素,当你需要找到具     有最小 F 值的方格时,遍历整个 open list 。这个很简单,但对于很长的路径会很慢。这个方法可以通过维护一个排好序的表来改进,每次当你需要找到具有最小 F 值的方格时,仅取出表的第一项即可。我写程序时,这是我用的第一个方法。

          

           对于小地图,这可以很好的工作,但这不是最快的方案。追求速度的 A* 程序员使用了叫做二叉堆的东西,我的程序里也用了这个。以我的经验,这种方法在多数场合下会快 2—3 倍,对于更长的路径速度成几何级数增长 (10 倍甚至更快 ) 。如果你想更多的了解二叉堆,请阅读Using Binary Heaps in A* Pathfinding 。

    2.       其他单位:如果你碰巧很仔细的看了我的程序,你会注意到我完全忽略了其他单位。我的寻路者实际上可以互相穿越。这取决于游戏,也许可以,也许不可以。如果你想考虑其他单位,并想使他们移动时绕过彼此,我建议你的寻路程序忽略它们,再写一些新的程序来判断两个单位是否会发生碰撞。如果发生碰撞,你可以产生一个新的路径,或者是使用一些标准的运动法则(比如永远向右移动,等等)直至障碍物不在途中,然后产生一个新的路径。为什么在计算初始路径是不包括其他单位呢?因为其他单位是可以动的,当你到达的时候它们可能不在自己的位置上。这可以产生一些怪异的结果,一个单位突然转向来避免和一个已不存在的单位碰撞,在它的路径计算出来后和穿越它路径的那些单位碰撞了。

    在寻路代码中忽略其他单位,意味着你必须写另一份代码来处理碰撞。这是游戏的细节,所以我把解决方案留给你。本文末尾引用的 Bryan Stout's 的文章中的几种解决方案非常值得了解。

    3.       一些速度方面的提示:如果你在开发自己的 A* 程序或者是改编我写的程序,最后你会发现寻路占用了大量的 CPU 时间,尤其是当你有相当多的寻路者和一块很大的地图时。如果你阅读过网上的资料,你会发现就算是开发星际争霸,帝国时代的专家也是这样。如果你发现事情由于寻路而变慢了,这里有些主意很不错:

    ◆     使用小地图或者更少的寻路者。

    ◆     千万不要同时给多个寻路者寻路。取而代之的是把它们放入队列中,分散到几个游戏周期中。如果你的游戏以每秒 40 周期的速度运行,没人能察觉到。但是如果同时有大量的寻路者在寻路的话,他们会马上就发现游戏慢下来了。

    ◆     考虑在地图中使用更大的方格。这减少了寻路时需要搜索的方格数量。如果你是有雄心的话,你可以设计多套寻路方案,根据路径的长度而使用在不同场合。这也是专业人士的做法,对长路径使用大方格,当你接近目标时使用小方格。如果你对这个有兴趣,请看 Two-Tiered A* Pathfinding 。

    ◆     对于很长的路径,考虑使用路径点系统,或者可以预先计算路径并加入游戏中。

    ◆     预先处理你的地图,指出哪些区域是不可到达的。这些区域称为“孤岛”。实际上,他们可以是岛屿,或者是被墙壁等包围而不可到达的任意区域。 A* 的下限是,你告诉他搜寻通往哪些区域的路径时,他会搜索整个地图,直到所有可以抵达的方格都通过 open list 或 close list 得到了处理。这会浪费大量的 CPU 时间。这可以通过预先设定不可到达的区域来解决。在某种数组中记录这些信息,在寻路前检查它。在我的 Blitz 版程序中,我写了个地图预处理程序来完成这个。它可以提前识别寻路算法会忽略的死路径,这又进一步提高了速度。

    4.    不同的地形损耗:在这个教程和我的程序中,地形只有 2 种:可抵达的和不可抵达        的。但是如果你有些可抵达的地形,移动代价会更高些,沼泽,山丘,地牢的楼梯

           等都是可抵达的地形,但是移动代价比平地就要高。类似的,道路的移动代价就比        它周围的地形低。

    在你计算给定方格的 G 值时加上地形的代价就很容易解决了这个问题。简单的给这些方格加上一些额外的代价就可以了。 A* 算法用来查找代价最低的路径,应该很容易处理这些。在我的简单例子中,地形只有可达和不可达两种, A* 会搜寻最短和最直接的路径。但是在有地形代价的环境中,代价最低的的路径可能会很长。

    就像沿着公路绕过沼泽而不是直接穿越它。

    另一个需要考虑的是专家所谓的“ influence Mapping ”,就像上面描述的可变成本地形一样,你可以创建一个额外的计分系统,把它应用到寻路的 AI 中。假设你有这样一张地图,地图上由个通道穿过山丘,有大批的寻路者要通过这个通道,电脑每次产生一个通过那个通道的路径都会变得很拥挤。如果需要,你可以产生一个 influence map ,它惩罚那些会发生大屠杀的方格。这会让电脑选择更安全的路径,也可以帮助它避免因为路径短(当然也更危险)而持续把队伍或寻路者送往某一特定路径。

    5.    维护未探测的区域:你玩 PC 游戏的时候是否发现电脑总是能精确的选择路径,甚至地图都未被探测。对于游戏来说,寻路过于精确反而不真实。幸运的是,这个问题很容易修正。答案就是为每个玩家和电脑(每个玩家,不是每个单位 --- 那会浪费很多内存)创建一个独立的 knownWalkability 数组。每个数组包含了玩家已经探测的区域的信息,和假设是可到达的其他区域,直到被证实。使用这种方法,单位会在路的死端徘徊,并会做出错误的选择,直到在它周围找到了路径。地图一旦被探测了,寻路又向平常一样工作。

    6.    平滑路径: A* 自动给你花费最小的,最短的路径,但它不会自动给你最平滑的路径。看看我们的例子所找到的路径(图 7 )。在这条路径上,第一步在起点的右下方,如果第一步在起点的正下方是不是路径会更平滑呢?

           有几个方法解决这个问题。在你计算路径时,你可以惩罚那些改变方向的方格,把它的 G 值增加一个额外的开销。另一种选择是,你可以遍历你生成的路径,查找那些用相邻的方格替代会使路径更平滑的地方。要了解更多,请看 Toward More Realistic Pathfinding 。

    7.    非方形搜索区域:在我们的例子中,我们使用都是 2D 的方形的区域。你可以使用不规则的区域。想想冒险游戏中的那些国家,你可以设计一个像那样的寻路关卡。你需要建立一张表格来保存国家相邻关系,以及从一个国家移动到另一个国家的 G 值。你还需要一个方法了估算 H 值。其他的都可以向上面的例子一样处理。当你向 open list 添加新项时,不是使用相邻的方格,而是查看表里相邻的国家。

    类似的,你可以为一张固定地形的地图的路径建立路径点系统。路径点通常是道路或地牢通道的转折点。作为游戏设计者,你可以预先设定路径点。如果两个路径点的连线没有障碍物的话它们被视为相邻的。在冒险游戏的例子中,你可以保存这些相邻信息在某种表中,当 open list 增加新项时使用。然后记录 G 值(可能用两个结点间的直线距离)和 H 值(可能使用从节点到目标的直线距离)。其它的都想往常一样处理。

    进一步阅读(Further Reading)

    Ok ,现在你已经对 A* 有了个基本的了解,同时也认识了一些高级的主题。我强烈建议你看看我的代码,压缩包里包含了 2 个版本的实现,一个是 C++ ,另一个是 Blitz Basic 。 2 个版本都有注释,你以该可以很容易就看懂。下面是链接:

    Sample Code: A* Pathfinder (2D) Version 1.71 。

     

    如果你不会使用 C++ 或是 BlitzBasic ,在 C++ 版本下你可以找到两个 exe 文件。 BlitzBasic 版本必须去网站 Blitz Basic 下载 BlitzBasic 3D 的免费 Demo 才能运行。 在这里 here 你可以看到一个 Ben O'Neill 的 A* 在线验证实例。

     

    你应该阅读下面这几个站点的文章。在你读完本教程后你可以更容易理解他们。

    Amit's A* Pages : Amit Patel 的这篇文章被广泛引用,但是如果你没有阅读本教程的话,你可能会感到很迷惑。尤其是你可以看到 Amit Patel自己的一些想法。

    Smart Moves: Intelligent Path Finding : Bryan Stout 的这篇需要去 Gamasutra.com 注册才能阅读。 Bryan 用 Delphi 写的程序帮助我学习了A* ,同时给了我一些我的程序中的一些灵感。他也阐述了 A* 的其他选择。

    Terrain Analysis : Dave Pottinger 一篇非常高阶的,有吸引力的文章。他是 Ensemble Studios 的一名专家。这个家伙调整了游戏帝国时代和王者时代。不要期望能够读懂这里的每一样东西,但是这是一篇能给你一些不错的主意的很有吸引力的文章。它讨论了包 mip-mapping ,

    influence mapping ,和其他高阶 AI 寻路主题。他的 flood filling 给了我在处理死路径 ”dead ends” 和孤岛 ”island” 时的灵感。这包含在我的 Blitz版本的程序里。

     

    下面的一些站点也值得去看看:

    ·                     aiGuru: Pathfinding

    ·                     Game AI Resource: Pathfinding

    ·                     GameDev.net: Pathfinding 


    谢谢。

    展开全文
  • a星算法

    2011-11-18 15:28:12
    A星算法。比如说现在有一个魔兽争霸的游戏,我拥有一个英雄MK,让他从我的基地到达对方的基地。那么他肯定会走最短的距离,这里就是A星算法的经典应用。 F值 F=G+H 类似于优先队列的一个衡量标准。每一次我么都是...
    A星算法。比如说现在有一个魔兽争霸的游戏,我拥有一个英雄MK,让他从我的基地到达对方的基地。那么他肯定会走最短的距离,这里就是A星算法的经典应用。
    
    F值
    F=G+H
    类似于优先队列的一个衡量标准。每一次我么都是选取F值最小的点加入到开启列表当中。
    
    G值
    从其实格到当前格的距离。这个值后期要更新,比如,如果我做1路公交车到起点,花G1块钱,坐2路公交到起点,花G2(G1>G2)块钱。那么当我知道以后我就坐2路公交车。因为便宜。
    
    H值
    这个值就是当前格到终点的估计距离。这个值是定性的,不一定完全准确。但是还是可以避免bfs的路径。
    
    
    算法过程
    1 把起始格添加到开启列表。
    2 重复下面的工作
    	2.1 寻找开启列表当中F值最小的格子,我们称它为当前格。
    	2.2 从当前格开始,bfs他周围的点,叫做嗅探点。
    	2.2.1 如果嗅探点不可经过(墙,水,火,妖怪),那么跳过。
    	2.2.2 如果嗅探点不在开启列表,那么加入到开启列表当中。把当前点作为嗅探点		 的父节点。
    	2.2.3 如果嗅探点在开启列表中,如果G值降低啦,把当前点作为嗅探点的父节点。		 更改嗅探点的G值和F值,但是H值不会改变。
    	2.2.4 
      			  a如果目标格都存入啦关闭列表。路径找到
    	  b如果目标格没有存入关闭列表,但是开启列表空拉。路径没有找到。
    3 从目标格开始,沿着父节点移动,回到起始点。这条路径就是要找到的路径。
    
    Dijkstra算法的本质就是A星算法。但是H值永远为0。


     

    展开全文
  • 分享一下A星算法及A星优化算法源码,提供大家学习使用!
  • A星算法工程

    2018-06-11 23:18:18
    A星算法工程A星算法工程A星算法工程A星算法工程A星算法工程
  • A星:A星算法-源码

    2021-02-21 02:40:00
    一个明星 A星算法
  • A 星算法

    2014-07-23 10:54:20
    /**  * \file  * \version $Id: zAStar.h $ ... * \brief A*寻路算法  */ #ifndef _zAStar_h_ #define _zAStar_h_ #include #include #include #include "zSceneEntry.h" /**

    /**
     * \file
     * \version  $Id: zAStar.h  $
     * \author 
     * \date
     * \brief A*寻路算法
     */


    #ifndef _zAStar_h_
    #define _zAStar_h_

    #include <list>
    #include <vector>
    #include <algorithm>

    #include "zSceneEntry.h"

    /**
     * \brief A*寻路算法模板
     * 其中step表示步长,radius表示搜索半径
     */
    template <int step = 1, int radius = 12>
    class zAStar
    {

     private:

      /**
       * \brief 路径坐标点
       */
      struct zPathPoint
      {
       /**
        * \brief 坐标
        */
       zPos pos;
       /**
        * \brief 当前距离
        */
       int cc;
       /**
        * \brief 路径上一个结点指针
        */
       zPathPoint *father;
      };

      /**
       * \brief 路径头
       */
      struct zPathQueue
      {
       /**
        * \brief 路径节点头指针
        */
       zPathPoint *node;
       /**
        * \brief 路径消耗距离
        */
       int cost;
       /**
        * \brief 构造函数
        * \param node 初始化的路径节点头指针
        * \param cost 当前消耗距离
        */
       zPathQueue(zPathPoint *node, int cost)
       {
        this->node = node;
        this->cost = cost;
       }
       /**
        * \brief 拷贝构造函数
        * \param queue 待拷贝的源数据
        */
       zPathQueue(const zPathQueue &queue)
       {
        node = queue.node;
        cost = queue.cost;
       }
       /**
        * \brief 赋值操作符号
        * \param queue 待赋值的源数据
        * \return 返回结构的引用
        */
       zPathQueue & operator= (const zPathQueue &queue)
       {
        node = queue.node;
        cost = queue.cost;
        return *this;
       }
      };

      /**
       * \brief 定义所有路径的链表
       */
    #ifdef _POOL_ALLOC_  
      typedef std::list<zPathQueue, __gnu_cxx::__pool_alloc<zPathQueue> > zPathQueueHead;
    #else
      typedef std::list<zPathQueue> zPathQueueHead;
    #endif

      typedef typename zPathQueueHead::iterator iterator;
      typedef typename zPathQueueHead::reference reference;

      /**
       * \brief 估价函数
       * \param midPos 中间临时坐标点
       * \param endPos 最终坐标点
       * \return 估算出的两点之间的距离
       */
      int judge(const zPos &midPos, const zPos &endPos)
      {
       int distance = abs(midPos.x - endPos.x) + abs(midPos.y - endPos.y);
       return distance;
      }

      /**
       * \brief 进入路径队列
       * \param queueHead 路径队列头
       * \param pPoint 把路径节点添加到路径中
       * \param currentCost 路径的估算距离
       */
      void enter_queue(zPathQueueHead &queueHead, zPathPoint *pPoint, int currentCost)
      {
       zPathQueue pNew(pPoint, currentCost);
       if (!queueHead.empty())
       {
        for(iterator it = queueHead.begin(); it != queueHead.end(); it++)
        {
         //队列按cost由小到大的顺序排列
         if ((*it).cost > currentCost)
         {
          queueHead.insert(it, pNew);
          return;
         }
        }
       }
       queueHead.push_back(pNew);
      }

      /**
       * \brief 从路径链表中弹出最近距离
       * \param queueHead 路径队列头
       * \return 弹出的最近路径
       */
      zPathPoint *exit_queue(zPathQueueHead &queueHead)
      {
       zPathPoint *ret = NULL;
       if (!queueHead.empty())
       {
        reference ref = queueHead.front();
        ret = ref.node;
        queueHead.pop_front();
       }
       return ret;
      }

     public:

      /**
       * \brief 寻路过程中判断中间点是否可达目的地
       *
       * return (scene->zPosShortRange(tempPos, destPos, radius)
       *   && (!scene->checkBlock(tempPos) //目标点可达,或者是最终目标点
       *    || tempPos == destPos));
       *
       * \param tempPos 寻路过程的中间点
       * \param destPos 目的点坐标
       * \param radius 寻路范围,超出范围的视为目的地不可达
       * \return 返回是否可到达目的地
       */
      virtual bool moveable(const zPos &tempPos, const zPos &destPos, const int radius = radius) = 0;
      /**
       * \brief 物件向某一个方向移动
       * \param direct 方向
       * \param step 表示步长
       * \return 移动是否成功
       */
      virtual bool move(const int direct, const int step = step) = 0;
      /**
       * \brief 使物件向某一个点移动
       * 带寻路算法的移动
       * \param srcPos 起点坐标
       * \param destPos 目的地坐标
       * \return 移动是否成功
       */
      bool gotoFindPath(const zPos &srcPos, const zPos &destPos);
      /**
       * \brief Npc向某一个点移动
       * \param srcPos 起点坐标
       * \param destPos 目的地坐标
       * \return 移动是否成功
       */
      bool goTo(const zPos &srcPos, const zPos &destPos);
      /**
       * \brief Npc随机向某一个方向移动
       * \param direct 随机方向
       * \return 移动是否成功
       */
      bool shiftMove(const int direct);

    };

    template<int step, int radius>
    bool zAStar<step, radius>::gotoFindPath(const zPos &srcPos, const zPos &destPos)
    {
     //DisMap是以destPos为中心的边长为2 * radius + 1 的正方形
     const int width = (2 * radius + 1);
     const int height = (2 * radius + 1);
     const int MaxNum = width * height;
     //把所有路径距离初始化为最大值
     std::vector<int, __gnu_cxx::__pool_alloc<int> > pDisMap(MaxNum, MaxNum);
     std::vector<zPathPoint, __gnu_cxx::__pool_alloc<zPathPoint> > stack(MaxNum * 8 + 1);//在堆栈中分配内存
     zPathQueueHead queueHead;

     //从开始坐标进行计算
     zPathPoint *root = &stack[MaxNum * 8];
     root->pos = srcPos;
     root->cc = 0;
     root->father = NULL;
     enter_queue(queueHead, root, root->cc + judge(root->pos, destPos));

     int Count = 0;
     //无论如何,循环超过MaxNum次则放弃
     while(Count < MaxNum)
     {
      root = exit_queue(queueHead);
      if (NULL == root)
      {
       //目标点不可达
       return false;
      }

      if (root->pos == destPos)
      {
       //找到到达目的地的路径
       break;
      }

      const zAdjust adjust[8] =
      {
       { 1 * step, 0 * step },
       { 0 * step, -1 * step },
       { 0 * step, 1 * step },
       { -1 * step, 0 * step },
       { 1 * step, -1 * step },
       { -1 * step, -1 * step },
       { -1 * step, 1 * step },
       { 1 * step, 1 * step }
      };
      for(int i = 0; i < 8; i++)
      {
       //分别对周围8个格点进行计算路径
       bool bCanWalk = true;
       zPos tempPos = root->pos;
       tempPos += adjust[i];

       if (moveable(tempPos, destPos))
       {
        //对路径进行回溯
        zPathPoint *p = root;
        while(p)
        {
         if(p->pos == tempPos)
         {
          //发现坐标点已经在回溯路径中,不能向前走
          bCanWalk = false;
          break;
         }
         p = p->father;
        }

        //如果路径回溯成功,表示这个点是可行走的
        if (bCanWalk)
        {
         int cost = root->cc + 1;
         int index = (tempPos.y - destPos.y + radius) * width + (tempPos.x - destPos.x + radius);
         if (index >= 0
           && index < MaxNum
           && cost < pDisMap[index])
         {
          //这条路径比上次计算的路径还要短,需要加入到最短路径队列中
          pDisMap[index] = cost;
          zPathPoint *pNewEntry = &stack[Count * 8 + i];
          pNewEntry->pos = tempPos;
          pNewEntry->cc = cost;
          pNewEntry->father = root;
          enter_queue(queueHead, pNewEntry, pNewEntry->cc + judge(pNewEntry->pos, destPos));
         }
        }
       }
      }

      Count++;
     }

     if (Count < MaxNum)
     {
      //最终路径在PointHead中,但只走一步
      while(root)
      {
       //倒数第二个节点
       if(root->father != NULL
         && root->father->father == NULL)
       {
        return move(srcPos.getDirect(root->pos));
       }

       root = root->father;
      }
     }

     return false;
    }

    template<int step, int radius>
    inline bool zAStar<step, radius>::goTo(const zPos &srcPos, const zPos &destPos)
    {
     int direct = srcPos.getDirect(destPos);

     if (!move(direct)) {
      int r = zMisc::randBetween(0, 1);
      int deep = 0;
      while(deep < 3) {
       switch(r) {
        case 0://顺时针
         direct++;
         break;
        case 1://逆时针
         direct += 7;
         break;
       }
       direct %= 8;
       if (move(direct))
        return true;
       deep++;
      }
     }

     return false;
    }

    template<int step, int radius>
    inline bool zAStar<step, radius>::shiftMove(const int direct)
    {
     return move(direct);
    }

    #endif

     

    展开全文
  • 易语言A星算法源码

    2020-07-22 04:02:52
    易语言A星算法源码,A星算法,A星,画路线,简单A星

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,605
精华内容 642
关键字:

a星算法