精华内容
下载资源
问答
  • 如果角色可以360度走,要怎么使路径平滑呢???? ???????????????????????????????????
  • A星算法代码

    热门讨论 2015-10-07 00:02:34
    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星算法 c语言实现 a*算法

    热门讨论 2009-02-11 20:28:15
    A星算法 用c语言实现 用到了队列 a*算法 A星算法 用c语言实现 用到了队列 a*算法
  • A星算法自动寻路(C++源代码

    热门讨论 2010-06-20 13:46:40
    A星算法自动寻路(C++源代码),供大家学习使用
  • A星算法matlab实现

    2015-08-25 18:31:01
    matlab实现的A星算法,有个性界面,直接运行就可以
  • A* A星 算法 C语言 实现代码

    千次阅读 2016-12-12 17:25:44
     A*算法是很经典的只能启发式搜索算法,关于只能搜索算法和一般的搜索算法(例如DFS,BFS之类),在语言描述上的区别,我觉得用《代码大全》中的一句话描述的非常好:“驾驶汽车达到某人家,写成算法是:沿167号高速...

    关于A*算法,很早就想写点什么,可是貌似天天在忙活着什么,可事实又没有做什么,真是浮躁啊!所以今晚还是来写一下总结吧!

            A*算法是很经典的只能启发式搜索算法,关于只能搜索算法和一般的搜索算法(例如DFS,BFS之类),在语言描述上的区别,我觉得用《代码大全》中的一句话描述的非常好:“驾驶汽车达到某人家,写成算法是:沿167号高速往南行至Puyallup,从XX出口后往山上开4.5英里,在一个杂货店旁边的红绿灯右转,接着在第一个路口左转,从左边的褐色大房子的车道进去就是;而启发式是:找出上一次我们给你寄的信,照着信上地址开车到这个镇,到了那里你问一下我们房子在那里,这里的每一个人都认识我们,肯定会有人愿意帮助你,如果你找不到人,就找一个电话亭打电话给我们,我们出来接你”。听上去还是有点抽象。那么下面我们具体看看A*算法!

    注:本文的图形以及一些思想借助于http://www.policyalmanac.org/games/aStarTutorial.htm,非常感谢经典文   章!

                                                        


    我们要想从绿色的点到红色的点,需要启发式得去找一条路径,到底怎么去找呢,开始没有办法,只能从开始点慢慢尝试!我们需要定义一个OPEN表,OPEN表中放的是什么呢?就是当前考虑的点,及其周边的点需要添加进来,作为可能的路径上的点。这样说可能有点抽象,那么先看下面:

                                                                      

    我们从起始点开始搜索:

       1:从点A开始,并且把它作为待处理点存入一个OPEN表。你的路径可能会通过它包含的方格,也可能不会。基本上,这是一个待检查方格的列表。
       2:寻找起点周围(邻居)所有可到达或者可通过的方格,如果有障碍物方格。那么就不需要考虑他们,对于其他的吕剧节点也把他们加入OPEN表。这些邻居节点认当前点为父节点。(父节点的保存是必须的!因为当我们找到最后一个点的时候,需要通过父节点回溯,找到所有点直到开始节点!那么就是一个完整的路径!)
       3:从开启列表中删除点A,把它加入到一个CLOSE列表,列表中保存所有不需要再次检查的方格。

    在这一点,你应该形成如图的结构。在图中,暗绿色方格是你起始方格的中心。它被用浅蓝色描边,以表示它被加入到关闭列表中了。所有的相邻格现在都在开启列表中,它们被用浅绿色描边。每个方格都有一个灰色指针反指他们的父方格,也就是开始的方格。

                                                                        


    结下来我们应该选择哪一个点继续考虑呢!我想大家应该知道所谓的启发函数,所谓权值之类(此处所谓的权值就是路劲的长度)。YES,我们需要OPEN表中权值F最小的那个点!为什么呢,当然是权值越小,越靠近目标点咯!

    对于权值我们设为F,那么F怎么计算到的!我们有两个项!G和H, 

    G = 从起点A,沿着产生的路径,移动到网格上指定方格的路径耗费。
    H = 从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的。这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长度。(但是我们需要知道:虽然只是猜测,但是只要是基于一个统一的标准,相对远近的趋势是不变的!这一点是很重要的! )

    例如:H值的估计采用“曼哈顿”法,也就是当前的点,到目标点,横向和纵向的格子数相加,就是H值!

               ( 注意:对于障碍物我们是不考虑是否跳过的问题!即,障碍物也当做正常的一个格子!这也是H值仅仅是预测的而已的原因!即所谓启发式! )

    那么对于第一幅图,起始点离终点的H值是:横向相差4个格子,纵向相差0个格子,那么H=4+0=4;

    当然也有其他的办法,例如使用直线距离,sqrt( pow( des.x - src.x ) + pow( des.y - src.y ) )也是可以的~


    对于G值!在这个例子,令水平或者垂直移动的耗费为10,对角线方向耗费为14。我们取这些值是因为沿对角线的距离是沿水平或垂直移动耗费的的根号21.414倍。为了简化,我们用1014近似。有时候简化是很重要的~

    ( 其实距离只要反应了基本的倍数关系就可以了! )

    对于起始点以及周围点的G值,H值和F值,下图可以很清晰的看到!( 左上角是F,左下角是G,右下角是H )

                                              

    对于G值,只要是横向和竖向的邻居,设为+10,斜向的邻居+14就可以了~计算真的很easy吧~呵呵~

    对于H值,就是数格子就是咯~

    F = G + H

    注意上面的邻居节点都加入OPEN表了哦~~~   起点从OPEN中删除,加入CLOSE中~

    接着计算:

    然后从OPEN表中选择一个F值最小的然后考虑其周围邻居,再循环处理!直到终点加入CLOSE中,寻路结束!或者OPEN空了,没找到路径!

    ( 至于我们怎么选出最小的那个点呢!?我们使用堆排序处理的,对于选出最小值是很快的~ )

    可以看到,F最小的是起始点右边的那个点,下面框框表示的~

                                      

    然后再考虑其邻居:

    此时对于其邻居有几种可能性

    1:邻居已经在CLOSE表中了,那么不需要考虑了~

    2:邻居是障碍物,不需要考虑了e

    3:邻居不在OPEN表中,那么将邻居加入OPEN,并将次邻居的父节点赋值为当前节点

    4:邻居在OPEN中,那么需要看看此邻居点的G值与当前点的(G值+当前点到邻居点的距离(10或者14))的大小,如果从此点走更近(即G值更小),那么将此点的父节点换成当前点!(注意:对于同一个点,G值下,那么F必须小!因为H是相同的!)

    下面是进一步的图示: 

                                                 

    那么我们按照上面的思路,知道终点加入CLOSE表!( 终极图示如下 )

                                                      

    最终我们可以得到路径:( 之前我们说过,由父节点往前回溯就很easy的得到路径了~ )

                                        

    说了这么多,也不知道说的行不行,还是需要总结一下!

    总结:

    1:将起始点加入OPEN表中

    2:循环直到OPEN为空或者终点加入CLOSE表中

    否则:找到OPEN表中F值最小的节点(使用堆排序得到小值点),将此点从OPEN删除,加入CLOSE!

      (此时最小点已经取出,那么需要从新排序OPEN表,是的第一个点是最小F的点!)

       对8个邻居进行处理:

    若:1:邻居已经在CLOSE表中了,那么不需要考虑了~

    2:邻居是障碍物,不需要考虑了e

    3:邻居不在OPEN表中,那么将邻居加入OPEN,并将次邻居的父节点赋值为当前节点

    4:邻居在OPEN中,那么需要看看此邻居点的G值与当前点的(G值+当前点到邻居点的距

         离 (10或者14))的大小,如果从此点走更近(即G值更小),那么将此点的父节点换成当前           点!  (注意:对于同一个点,G值下,那么F必须小!因为H是相同的!)

         注意:当父节点改变后,OPEN表中的最小点可能会变化,那么需要再次排序得到最

            小点!

    3:结束,根据退出循环的条件可以知道到底有没有找到路径!所以下面的工作就easy了~


          基本的原理就是这样的~

    下面给一个简单的C语言的演示代码,只是为了演示原理,没有注重其他问题,所以大家莫怪啊~

    注意:数组中1代表起点,2代表终点,0代表可以通过,3代表障碍物

    1. #include <stdio.h>  
    2. #include <stdlib.h>  
    3.   
    4. #define STARTNODE   1  
    5. #define ENDNODE     2  
    6. #define BARRIER     3  
    7.   
    8. typedef struct AStarNode  
    9. {  
    10.     int s_x;    // 坐标(最终输出路径需要)  
    11.     int s_y;  
    12.     int s_g;    // 起点到此点的距离( 由g和h可以得到f,此处f省略,f=g+h )  
    13.     int s_h;    // 启发函数预测的此点到终点的距离  
    14.     int s_style;// 结点类型:起始点,终点,障碍物  
    15.     struct AStarNode * s_parent;    // 父节点  
    16.     int s_is_in_closetable;     // 是否在close表中  
    17.     int s_is_in_opentable;      // 是否在open表中  
    18. }AStarNode, *pAStarNode;  
    19.   
    20. AStarNode  map_maze[10][10];        // 结点数组  
    21. pAStarNode open_table[100];     // open表  
    22. pAStarNode close_table[100];        // close表  
    23. int<span style="white-space:pre">   </span>   open_node_count;  <span style="white-space:pre">  </span>// open表中节点数量  
    24. int    close_node_count;    <span style="white-space:pre">  </span>// close表中结点数量  
    25. pAStarNode path_stack[100];     // 保存路径的栈  
    26. int        top = -1;            // 栈顶  
    27.   
    28.   
    29. // 交换两个元素  
    30. //   
    31. void swap( int idx1, int idx2 )    
    32. {    
    33.     pAStarNode tmp = open_table[idx1];  
    34.     open_table[idx1] = open_table[idx2];  
    35.     open_table[idx2] = tmp;  
    36. }    
    37.   
    38. // 堆调整  
    39. //   
    40. void adjust_heap( int /*i*/nIndex )      
    41. {     
    42.     int curr = nIndex;  
    43.     int child = curr * 2 + 1;   // 得到左孩子idx( 下标从0开始,所有做孩子是curr*2+1 )  
    44.     int parent = ( curr - 1 ) / 2;  // 得到双亲idx  
    45.   
    46.     if (nIndex < 0 || nIndex >= open_node_count)  
    47.     {  
    48.         return;  
    49.     }  
    50.       
    51.     // 往下调整( 要比较左右孩子和cuur parent )  
    52.     //   
    53.     while ( child < open_node_count )  
    54.     {  
    55.         // 小根堆是双亲值小于孩子值  
    56.         //   
    57.         if ( child + 1 < open_node_count && open_table[child]->s_g + open_table[child]->s_h  > open_table[child+1]->s_g + open_table[child+1]->s_h )  
    58.         {  
    59.             ++child;<span style="white-space:pre">              </span>// 判断左右孩子大小  
    60.         }  
    61.           
    62.         if (open_table[curr]->s_g + open_table[curr]->s_h <= open_table[child]->s_g + open_table[child]->s_h)  
    63.         {  
    64.             break;  
    65.         }  
    66.         else  
    67.         {  
    68.             swap( child, curr );            // 交换节点  
    69.             curr = child;               // 再判断当前孩子节点  
    70.             child = curr * 2 + 1;           // 再判断左孩子  
    71.         }  
    72.     }  
    73.       
    74.     if (curr != nIndex)  
    75.     {  
    76.         return;  
    77.     }  
    78.   
    79.     // 往上调整( 只需要比较cuur child和parent )  
    80.     //   
    81.     while (curr != 0)  
    82.     {  
    83.         if (open_table[curr]->s_g + open_table[curr]->s_h >= open_table[parent]->s_g + open_table[parent]->s_h)  
    84.         {  
    85.             break;  
    86.         }  
    87.         else  
    88.         {  
    89.             swap( curr, parent );  
    90.             curr = parent;  
    91.             parent = (curr-1)/2;  
    92.         }  
    93.     }  
    94. }    
    95.   
    96. // 判断邻居点是否可以进入open表  
    97. //   
    98. void insert_to_opentable( int x, int y, pAStarNode curr_node, pAStarNode end_node, int w )  
    99. {  
    100.     int i;  
    101.   
    102.     if ( map_maze[x][y].s_style != BARRIER )        // 不是障碍物  
    103.     {  
    104.         if ( !map_maze[x][y].s_is_in_closetable )   // 不在闭表中  
    105.         {  
    106.             if ( map_maze[x][y].s_is_in_opentable ) // 在open表中  
    107.             {  
    108.                 // 需要判断是否是一条更优化的路径  
    109.                 //   
    110.                 if ( map_maze[x][y].s_g > curr_node->s_g + w )    // 如果更优化  
    111.                 {  
    112.                     map_maze[x][y].s_g = curr_node->s_g + w;  
    113.                     map_maze[x][y].s_parent = curr_node;  
    114.   
    115.                     for ( i = 0; i < open_node_count; ++i )  
    116.                     {  
    117.                         if ( open_table[i]->s_x == map_maze[x][y].s_x && open_table[i]->s_y == map_maze[x][y].s_y )  
    118.                         {  
    119.                             break;  
    120.                         }  
    121.                     }  
    122.   
    123.                     adjust_heap( i );                   // 下面调整点  
    124.                 }  
    125.             }  
    126.             else                                    // 不在open中  
    127.             {  
    128.                 map_maze[x][y].s_g = curr_node->s_g + w;  
    129.                 map_maze[x][y].s_h = abs(end_node->s_x - x ) + abs(end_node->s_y - y);  
    130.                 map_maze[x][y].s_parent = curr_node;  
    131.                 map_maze[x][y].s_is_in_opentable = 1;  
    132.                 open_table[open_node_count++] = &(map_maze[x][y]);  
    133.             }  
    134.         }  
    135.     }  
    136. }  
    137.   
    138. // 查找邻居  
    139. // 对上下左右8个邻居进行查找  
    140. //    
    141. void get_neighbors( pAStarNode curr_node, pAStarNode end_node )  
    142. {  
    143.     int x = curr_node->s_x;  
    144.     int y = curr_node->s_y;  
    145.   
    146.     // 下面对于8个邻居进行处理!  
    147.     //   
    148.     if ( ( x + 1 ) >= 0 && ( x + 1 ) < 10 && y >= 0 && y < 10 )  
    149.     {  
    150.         insert_to_opentable( x+1, y, curr_node, end_node, 10 );  
    151.     }  
    152.   
    153.     if ( ( x - 1 ) >= 0 && ( x - 1 ) < 10 && y >= 0 && y < 10 )  
    154.     {  
    155.         insert_to_opentable( x-1, y, curr_node, end_node, 10 );  
    156.     }  
    157.   
    158.     if ( x >= 0 && x < 10 && ( y + 1 ) >= 0 && ( y + 1 ) < 10 )  
    159.     {  
    160.         insert_to_opentable( x, y+1, curr_node, end_node, 10 );  
    161.     }  
    162.   
    163.     if ( x >= 0 && x < 10 && ( y - 1 ) >= 0 && ( y - 1 ) < 10 )  
    164.     {  
    165.         insert_to_opentable( x, y-1, curr_node, end_node, 10 );  
    166.     }  
    167.   
    168.     if ( ( x + 1 ) >= 0 && ( x + 1 ) < 10 && ( y + 1 ) >= 0 && ( y + 1 ) < 10 )  
    169.     {  
    170.         insert_to_opentable( x+1, y+1, curr_node, end_node, 14 );  
    171.     }  
    172.   
    173.     if ( ( x + 1 ) >= 0 && ( x + 1 ) < 10 && ( y - 1 ) >= 0 && ( y - 1 ) < 10 )  
    174.     {  
    175.         insert_to_opentable( x+1, y-1, curr_node, end_node, 14 );  
    176.     }  
    177.   
    178.     if ( ( x - 1 ) >= 0 && ( x - 1 ) < 10 && ( y + 1 ) >= 0 && ( y + 1 ) < 10 )  
    179.     {  
    180.         insert_to_opentable( x-1, y+1, curr_node, end_node, 14 );  
    181.     }  
    182.   
    183.     if ( ( x - 1 ) >= 0 && ( x - 1 ) < 10 && ( y - 1 ) >= 0 && ( y - 1 ) < 10 )  
    184.     {  
    185.         insert_to_opentable( x-1, y-1, curr_node, end_node, 14 );  
    186.     }  
    187. }  
    188.   
    189.   
    190. int main()  
    191. {   
    192.     // 地图数组的定义  
    193.     //   
    194.     AStarNode *start_node;          // 起始点  
    195.     AStarNode *end_node;            // 结束点  
    196.     AStarNode *curr_node;           // 当前点  
    197.     int       is_found;         // 是否找到路径  
    198.     int maze[][10] ={           // 仅仅为了好赋值给map_maze  
    199.                         { 1,0,0,3,0,3,0,0,0,0 },  
    200.                         { 0,0,3,0,0,3,0,3,0,3 },  
    201.                         { 3,0,0,0,0,3,3,3,0,3 },  
    202.                         { 3,0,3,0,0,0,0,0,0,3 },  
    203.                         { 3,0,0,0,0,3,0,0,0,3 },  
    204.                         { 3,0,0,3,0,0,0,3,0,3 },  
    205.                         { 3,0,0,0,0,3,3,0,0,0 },  
    206.                         { 0,0,2,0,0,0,0,0,0,0 },  
    207.                         { 3,3,3,0,0,3,0,3,0,3 },  
    208.                         { 3,0,0,0,0,3,3,3,0,3 },  
    209.                     };  
    210.     int       i,j,x;  
    211.       
    212.     // 下面准备点  
    213.     //   
    214.     for( i = 0; i < 10; ++i )  
    215.     {  
    216.         for ( j = 0; j < 10; ++j )  
    217.         {  
    218.             map_maze[i][j].s_g = 0;  
    219.             map_maze[i][j].s_h = 0;  
    220.             map_maze[i][j].s_is_in_closetable = 0;  
    221.             map_maze[i][j].s_is_in_opentable = 0;  
    222.             map_maze[i][j].s_style = maze[i][j];  
    223.             map_maze[i][j].s_x = i;  
    224.             map_maze[i][j].s_y = j;  
    225.             map_maze[i][j].s_parent = NULL;  
    226.   
    227.             if ( map_maze[i][j].s_style == STARTNODE )  // 起点  
    228.             {  
    229.                 start_node = &(map_maze[i][j]);  
    230.             }  
    231.             else if( map_maze[i][j].s_style == ENDNODE )    // 终点  
    232.             {  
    233.                 end_node = &(map_maze[i][j]);  
    234.             }  
    235.   
    236.             printf("%d ", maze[i][j]);  
    237.         }  
    238.   
    239.         printf("\n");  
    240.     }  
    241.   
    242.     // 下面使用A*算法得到路径  
    243.     //    
    244.     open_table[open_node_count++] = start_node;         // 起始点加入open表  
    245.       
    246.     start_node->s_is_in_opentable = 1;               // 加入open表  
    247.     start_node->s_g = 0;  
    248.     start_node->s_h = abs(end_node->s_x - start_node->s_x) + abs(end_node->s_y - start_node->s_y);  
    249.     start_node->s_parent = NULL;  
    250.       
    251.     if ( start_node->s_x == end_node->s_x && start_node->s_y == end_node->s_y )  
    252.     {  
    253.         printf("起点==终点!\n");  
    254.         return 0;  
    255.     }  
    256.       
    257.     is_found = 0;  
    258.   
    259.     while( 1 )  
    260.     {  
    261.         // for test  
    262.         //   
    263. /*      for ( x = 0; x < open_node_count; ++x ) 
    264.         { 
    265.             printf("(%d,%d):%d   ", open_table[x]->s_x, open_table[x]->s_y, open_table[x]->s_g+open_table[x]->s_h); 
    266.         } 
    267.         printf("\n\n"); 
    268. */  
    269.         curr_node = open_table[0];      // open表的第一个点一定是f值最小的点(通过堆排序得到的)  
    270.         open_table[0] = open_table[--open_node_count];  // 最后一个点放到第一个点,然后进行堆调整  
    271.         adjust_heap( 0 );               // 调整堆  
    272.           
    273.         close_table[close_node_count++] = curr_node;    // 当前点加入close表  
    274.         curr_node->s_is_in_closetable = 1;       // 已经在close表中了  
    275.   
    276.         if ( curr_node->s_x == end_node->s_x && curr_node->s_y == end_node->s_y )// 终点在close中,结束  
    277.         {  
    278.             is_found = 1;  
    279.             break;  
    280.         }  
    281.   
    282.         get_neighbors( curr_node, end_node );           // 对邻居的处理  
    283.   
    284.         if ( open_node_count == 0 )             // 没有路径到达  
    285.         {  
    286.             is_found = 0;  
    287.             break;  
    288.         }  
    289.     }  
    290.   
    291.     if ( is_found )  
    292.     {  
    293.         curr_node = end_node;  
    294.           
    295.         while( curr_node )  
    296.         {  
    297.             path_stack[++top] = curr_node;  
    298.             curr_node = curr_node->s_parent;  
    299.         }  
    300.   
    301.         while( top >= 0 )        // 下面是输出路径看看~  
    302.         {  
    303.             if ( top > 0 )  
    304.             {  
    305.                 printf("(%d,%d)-->", path_stack[top]->s_x, path_stack[top--]->s_y);  
    306.             }  
    307.             else  
    308.             {  
    309.                 printf("(%d,%d)", path_stack[top]->s_x, path_stack[top--]->s_y);  
    310.             }  
    311.         }  
    312.     }  
    313.     else  
    314.     {  
    315.         printf("么有找到路径");  
    316.     }  
    317.   
    318.     puts("");  
    319.   
    320.     return 0;  
    321. }  
    展开全文
  • 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 星算法总结

    2016-10-31 22:48:00
    A 星算法总结A 星算法FPGA EDA工具VPR布线器所采用的布线算法,面试滴滴的时候听说他们的路径规模用的也是A 星算法,感觉这个算法还蛮厉害的,对这个算法进行一个总结。 文章...

    A 星算法总结

    A 星算法FPGA EDA工具VPR布线器所采用的布线算法,面试滴滴的时候听说他们的路径规模用的也是A 星算法,感觉这个算法还蛮厉害的,对这个算法进行一个总结。
    文章http://www.tuicool.com/articles/MJrYz26 对这个算法用语言描述的很好,搬运下:

      A星寻路算法显然是用来寻路的,应用也很普遍,比如梦幻西游。。。算法的思路很简单,就是在bfs的基础上加了估值函数。它的核心是 F(x) = G(x) + H(x) 和open、close列表。
      G(x)表示从起点到X点的消耗(或者叫移动量什么的),H(X)表示X点到终点的消耗的估值,F(x)就是两者的和值。open列表记录了可能要走的区域,close列表记录了不会再考虑的区域。我们每次都选F值最小的区域搜索,就能搜到一条到终点的最短路径,其中估值H越接近准确值,需要搜索的节点就越少。

    A星算法的步骤:
    {
    将起点区域添加到open列表中,该区域有最小的和值。
    重复以下:
      将open列表中最小F值的区域X移除,然后添加到close列表中。
      对于与X相邻的每一块可通行且不在close列表中的区域T:
    如果T不在open列表中:添加到open列表,把X设为T的前驱
    如果T已经在open列表中:检查 F 是否更小。如果是,更新 T的F值 和前驱
    直到:
      终点添加到了close列表。(已找到路径)
      终点未添加到close列表且open列表已空。(未找到路径)
    }

    估值函数H(X)很有意思,不同的估值函数会带来不同的路径,因此在二维坐标系统下作了个小小的测试:

    曼哈顿距离

    在二维平面中 点(x1,y1)和点(x2, y2)的曼哈顿距离:H(X)= abs(x1-x2)+ abs(y1 - y2)。其中红色的点表示考察过的点,绿色的点表示最终生成的路径。
    曼哈顿距离

    殴几里得距离

    在二维平面中 点(x1,y1)和点(x2, y2)的曼哈顿距离:H(X)= sqrt((x1-x2)* (x1-x2)+ (y1 - y2)*(y1 - y2))
    这里写图片描述

    水平距离

    这是测着玩的: H(X)= abs(x1 - x2)
    这里写图片描述

    垂直距离

    这也是我测着玩的:H(X) = abs(y1 - y2)
    这里写图片描述

    迪杰斯特拉算法

    令H(x) = 0, A星算法就变成了 迪杰斯特拉算法,想想还真是!!
    这里写图片描述

    契比雪夫距离

    H(X)= max( abs(x1 - x2), abs(y1 - y2) )
    这里写图片描述

    看来加上H(X)效果大有改善!!
    代码为原创:http://download.csdn.net/detail/wjwever1/9669482

    展开全文
  • Java游戏服务器开发之A星算法

    千次阅读 2018-05-29 11:49:54
    Java游戏服务器开发之A星算法 学习这个主要是用于寻路算法。 参考资料主要是siki学院的视频,A计划--人工智能--A星算法。 网址http://www.sikiedu.com/course/62/tasks 代码也是大部分参考里面,原本是C#的,用...
  • A星算法的实现(C#)

    热门讨论 2010-11-28 20:16:43
    自己用C#写的一个实现A星算法的小程序,该程序动态演示使用A星算法寻路的过程,简单明了,是一个学习A星算法不错的资料。里面的代码有详细注释。
  • A星算法地图编辑器

    千次阅读 2015-07-30 20:02:37
    最近因为项目的需要,要使用到A星算法,相比大家都知道A星算法是通过把地图转化为二维数组,即一个只有0和1的数组,在这里我就不赘述A星算法的原理什么的,因为网上有很多介绍关于A星算法的文章,大家如果需要熟悉这...
  • python 实现A星算法

    千次阅读 2019-12-23 19:09:34
    python A星算法效果图 效果图 (程序在cmd中打印所有有点闪屏!!!)
  • python3.6实现的A星算法

    万次阅读 多人点赞 2018-06-20 22:28:40
    A星算法原理: 原理我就不再赘述,可以参考这篇博客https://blog.csdn.net/hitwhylz/article/details/23089415 最近用js写了一遍,用的同样的算法,需要js代码的看这里:...
  • A星算法示例(多种实现)

    热门讨论 2012-04-28 12:55:04
    A*(A星)算法示例,多种实现方法,语言为C++ 原创代码
  • js实现的A星算法

    千次阅读 2019-01-03 15:07:31
    最近在写js的slg游戏,需要用到a星算法。之前用python写过https://blog.csdn.net/qq_39687901/article/details/80753433,现在再用js写一遍。 二、源码 //二维数组 function Array2D(w, h, num) { var data = []...
  • A星算法寻找最短路径

    千次阅读 2017-12-29 11:32:37
    一个非常基础的算法就是A星算法。 我需要在一副图像中寻找两点之间的最短路径,而角色只能上下左右移动。 注意角色被规定的移动方式不同,那么我们设计的代价函数需要调整。 图像中的灰度为0的像素认为是障碍物。...
  • //拿到open列表中f最小的节点 curr_node = open_list.at(0); open_list.erase(open_list.begin()); curr_node->attr = ATTR_CLOSE;
  •   本篇实现的A星算法是基于贪婪优先算法实现的,由于贪婪优先算法得到的是次优路径,因此我们增加一个当前节点到起始节点的一个路径开销分量来提升路径的质量,筛选最优路径。具体实现如下: 节点类的编写   ...
  • 用简单直白的方式讲解A星寻路算法原理 https://www.cnblogs.com/leoin2012/p/3899822.html A星寻路算法介绍 https://www.cnblogs.com/zhoug2020/p/3468167.html matlab代码实现及效果实例: Astar/A星/A*算法...
  • A星算法和 IDA星算法

    千次阅读 2012-09-23 13:19:17
    首先讨论 A * 算法。其实我觉得他和广搜很相像,但是又有如下的要素: 1.估价函数 f = g + h,由两个部分组成: g 和 h,分别表示初始状态到当前状态的距离和当前状态到目标状态的估计距离。 2.每次扩展最优节点。...
  • 【算法导论】A*算法(A星算法

    千次阅读 2014-08-22 13:03:08
    这篇文章还可以在这里找到 英语 这篇blog是由iOS Tutorial Team的成员 Johann ...学习A星寻路算法是如何工作的! 你是否在做一款游戏的时候想创造一些怪兽或者游戏主角,让它们移动到特定的位置

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,668
精华内容 10,667
关键字:

a星算法代码