a星算法c++实现_递归算法理解

a星算法c++实现_递归算法理解翻了翻别人写的博客,我看到一个A星算法,只怪自己见识太少,竟然没听过这个算法。网上查了好些资料,自己对这算法理解了些,并用C#实现出来。           A星算法,也叫A*算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。如在一张dota地图上,英雄从一个地方走动到地图上另一个点,它选择最优路线的算法。       如上图,绿点是

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

         翻了翻别人写的博客,我看到一个A星算法,只怪自己见识太少,竟然没听过这个算法。网上查了好些资料,自己对这算法理解了些,并用C#实现出来。

     a星算法c++实现_递归算法理解

               A星算法,也叫A*算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。 如在一张dota地图上,英雄从一个地方走动到地图上另一个点,它选择最优路线的算法。

             如上图,绿点是开始点,红点是目的地,黑色区域是不可通过区域。 通过A*算法,黄色线段就是找到的最优路线。

        我想了想,其实用漫水算法也能找这路线啊。这A星算法优点在于处理速度快,并不是像漫水一样,各个方向都在寻找。

         A*算法原理。就以上面那种情况说明吧, 从绿色点开始,你想去红色点,你下一步有八个方向选择。

a星算法c++实现_递归算法理解

     八个方向选择,你肯定想往右边走,这样才能离目的地近。横竖走,还是斜着走,更倾向横竖走,距离短。

    用G表示你从起始点走的距离。横或竖一格G=10,斜着G=14。

    用H表示你离目的地的距离,这里就是个估算,就像你老远看下,在那个方向,估算下距离。用曼哈顿距离表示就可以了。 比如你在(1,1),要去(5,5).距离就当你竖着走4格,横着走4个,八格就到了。估算,别管障碍物。八格那么,H=80.变大十倍(因为G变大10倍了)。

    那么用F=G+H表示你周围的格子,你要去目的地花的代价。 越小越好。

     然后你建两个表,存放一些东西。你要探索的格子存在OpenList里去,你找到最好的存到CloseList去。你存的不仅仅是这个格子的F值,还有它指向的方向,不然你的G有什么意义。


      然后你就有F的值了,你周围的八个格子F都有了,加入到你的OpenList里去。选个F最小的格子,移出OpenList,存到CloseList去。走到这个格子,探索这个格子周围的格子忽略障碍物和边界,忽略CloseList里的格子,其他统统加入到Openlist里。如果有格子在OpenList里,看看他们原来的G值和你走过去的G值大小比较下,如果你的G大,就让那个格子以前那样,你的G小,更新它。

      然后在OpenList找最小F那个格子,移出OpenList,加入CloseList,走到这个格子,打开周围格子,循环下去,直到你哪天一不小心打开了目的地的格子。就停止吧。

   最后,从目的地这个格子的指向,一路指向你开始的格子!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MyAXing
{
    class MyPoint      //定义了MyPoint这种数据结构  就是我说的上面那种格子
    {
        public int x;
        public int y;
        public int G;
        public int H;
        public MyPoint father;
        public MyPoint()
        {
        }
        public MyPoint(int x0, int y0, int G0, int H0,MyPoint F)
        {
            x = x0;
            y = y0;
            G = G0;
            H = H0;
            father = F;
        }
    }
}

按照上面的思路,写出来就是了。定义两个List<MyPoint>来存Mypoint。

        List<MyPoint> Open_List = new List<MyPoint>();
        List<MyPoint> Close_List = new List<MyPoint>();

更新下,贴上源码//

Form1

  public partial class Form1 : Form
    {

        enum mycc
        {
            wall,
            start,
            des
        }

        mycc mychoose = mycc.wall;

        byte[,] R = new byte[10, 10] { 
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
            
            };

        mybutton[,] mybut = new mybutton[20, 20];

        byte[,] myR = new byte[20, 20];


        MyPoint pa = new MyPoint();
        MyPoint pb = new MyPoint();

        void init()
        {
            for (int i = 0; i < 20; i++)
            {
                for (int j = 0; j < 20; j++)
                {
                    myR[i, j] = 1;
                    mybut[i, j].BackColor = Color.Transparent;
                }
            }
        }



        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            AxingTest ax = new AxingTest(R);

            //定义起始位置
            MyPoint pa = new MyPoint();
            pa.x = 1;
            pa.y = 1;

            //定义目的地
            MyPoint pb = new MyPoint();
            pb.x = 8;
            pb.y = 8;

            List<MyPoint> myp = new List<MyPoint>();
           myp= ax.FindeWay(pa, pb);
           foreach (MyPoint p in myp)
           {
            //   textBox1.AppendText(p.ToString() + " ");
           }
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            for (int i = 0; i < 20; i++)
            {
                for (int j = 0; j < 20; j++)
                {
                    mybut[i, j] = new mybutton();
                    mybut[i, j].X = i;
                    mybut[i, j].Y = j;
                    mybut[i, j].Size = new Size(20, 20);
                    mybut[i, j].Location = new Point(i * 20, j * 20);
                    this.Controls.Add(mybut[i, j]);
                    mybut[i, j].MouseDown += Form1_MouseDown;
                }
            }
        }

        void Form1_MouseDown(object sender, MouseEventArgs e)
        {
            mybutton myb = (mybutton)sender;
            int x = myb.X;
            int y = myb.Y;
            if (mychoose == mycc.wall)
            {
                mybut[x, y].BackColor = Color.Black;
                myR[y, x] = 0;
            }

            if (mychoose == mycc.start)
            {
                mybut[x, y].BackColor = Color.Green;
              //  myR[x, y] = 1;
                pa.x = x;
                pa.y = y;
            }

            if (mychoose == mycc.des)
            {
                mybut[x, y].BackColor = Color.Red;
              //  myR[x, y] = 1;
                pb.x = x;
                pb.y = y;
            }

        }

        private void button6_Click(object sender, EventArgs e)
        {
            init();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            mychoose = mycc.wall;
        }

        private void button3_Click(object sender, EventArgs e)
        {
            mychoose = mycc.start;
        }

        private void button4_Click(object sender, EventArgs e)
        {
            mychoose = mycc.des;
        }

        private void button5_Click(object sender, EventArgs e)
        {
            AxingTest ax = new AxingTest(myR);
            List<MyPoint> myp = new List<MyPoint>();
            myp = ax.FindeWay(pa, pb);

            foreach (MyPoint p in myp)
            {
                mybut[p.x, p.y].BackColor = Color.Yellow;
            }
            mybut[pb.x, pb.y].BackColor = Color.Red;
        }
    }


    public class mybutton : Button
    {
        int x;
        int y;
        public int X
        {
            set { x = value; }
            get { return x; }
        }

        public int Y
        {
            set { y = value; }
            get { return y; }
        }
    }


AXingTest

    class AxingTest
    {
        List<MyPoint> Open_List = new List<MyPoint>();
        List<MyPoint> Close_List = new List<MyPoint>();
        byte[,] R;

        //byte[,] R = new byte[10, 10] { 
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        //    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
            
        //    };

        public AxingTest(byte[,] R)
        {
            this.R = R;
        }


        //从开启列表查找F值最小的节点
        private MyPoint GetMinFFromOpenList()
        {
            MyPoint Pmin = null;
            foreach (MyPoint p in Open_List)
                if (Pmin == null || Pmin.G + Pmin.H > p.G + p.H)
                    Pmin = p;
            return Pmin;
        }

        //判断一个点是否为障碍物
        private bool IsBar(MyPoint p, byte[,] map)
        {
            if (map[p.y, p.x] == 0) return true;
            return false;
        }

        //判断关闭列表是否包含一个坐标的点
        private bool IsInCloseList(int x, int y)
        {
            foreach (MyPoint p in Close_List)
                if (p.x == x && p.y == y)
                    return true;
            return false;
        }

        //从关闭列表返回对应坐标的点
        private MyPoint GetPointFromCloseList(int x, int y)
        {
            foreach (MyPoint p in Close_List)
                if (p.x == x && p.y == y)
                    return p;
            return null;
        }

        private bool IsInOpenList(int x, int y)
        {
            foreach (MyPoint p in Open_List)
                if (p.x == x && p.y == y)
                    return true;
            return false;
        }

        private MyPoint GetPointFromeOpenList(int x, int y)
        {
            foreach (MyPoint p in Open_List)
                if (p.x == x && p.y == y)
                    return p;
            return null;
        }

        private int GetG(MyPoint p)
        {
            if (p.father == null) return 0;
            if (p.x == p.father.x || p.y == p.father.y)
                return p.father.G + 10;
            else
                return p.father.G + 14;
        }

        private int GetH(MyPoint p, MyPoint pb)
        {
            return Math.Abs(p.x - pb.x)*10 + Math.Abs(p.y - pb.y)*10;
        }

        private void CheckP8(MyPoint p0, byte[,] map, MyPoint pa, ref MyPoint pb)
        {
            for (int xt = p0.x - 1; xt <= p0.x + 1; xt++)
            {
                for (int yt = p0.y - 1; yt <= p0.y + 1; yt++)
                {
                    //排除超过边界和关闭自身的点
                    if((xt>=0&&xt<R.GetLength(0)&&yt>=0&&yt<R.GetLength(1))&&!(xt==p0.x&&yt==p0.y))
                    {
                        //排除障碍点和关闭列表中的点
                        if(map[yt,xt]!=0&&!IsInCloseList(xt,yt))
                        {
                            if (IsInOpenList(xt, yt))
                            {
                                MyPoint pt = GetPointFromeOpenList(xt, yt);
                                int G_new = 0;
                                if (p0.x == pt.x || p0.y == pt.y)
                                    G_new = p0.G + 10;
                                else
                                    G_new = p0.G + 14;

                                if (G_new < pt.G)
                                {
                                    Open_List.Remove(pt);
                                    pt.father = p0;
                                    pt.G = G_new;
                                    Open_List.Add(pt);
                                }


                            }
                            else
                            {
                                //不在开启列表中
                                MyPoint pt = new MyPoint();
                                pt.x = xt;
                                pt.y = yt;
                                pt.father = p0;
                                pt.G = GetG(pt);
                                pt.H = GetH(pt, pb);
                                Open_List.Add(pt);
                            }
                        }
                    }
                }
            }
        }

        public List<MyPoint> FindeWay(MyPoint pa, MyPoint pb)
        {
            List<MyPoint> myp = new List<MyPoint>();
            Open_List.Add(pa);
            while (!(IsInOpenList(pb.x, pb.y) || Open_List.Count == 0))
            {
                MyPoint p0 = GetMinFFromOpenList();
                if (p0 == null) return null;
                Open_List.Remove(p0);
                Close_List.Add(p0);
                CheckP8(p0, R, pa, ref pb);
            }

            MyPoint p = GetPointFromeOpenList(pb.x, pb.y);
            while (p.father != null)
            {
                myp.Add(p);
                p = p.father;
               // R[p.y, p.x] = 3;
            }
            return myp;
        }


    }

MyPoint

    class MyPoint
    {
        public int x;
        public int y;
        public int G;
        public int H;
        public MyPoint father;
        public MyPoint()
        {
        }
        public MyPoint(int x0, int y0, int G0, int H0,MyPoint F)
        {
            x = x0;
            y = y0;
            G = G0;
            H = H0;
            father = F;
        }

        public override string ToString()
        {
            return "{"+x.ToString() + "," + y.ToString()+"}";
        }
    }

       

       

            

               

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/185196.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • idea如何配置jdk环境(安装jdk如何配置环境变量)

    IntelliJIDEA是支持JAVA开发得一种IDE安装它需要下载后逐步安装,没什么难点,但是最后会需要一个注册码,网上找个几个都提示过期了。但是从http://idea.lanyus.com/可以在线生成但是它提示注册码无效可以但是试过之后仍然不行,所以我去掉这两句话就可以了。然后需要安装JDK和配置环境变量一.下载JDK1.去jdk官网地址:http:…

  • 手机扫码登录实现原理「建议收藏」

    扫码登录原理最近接到一个需求,要求我用手机扫码实现用户登录,这是近几年比较流行的登录方式。这样确实是实现用户体验至上,操作简单,方便实用。拿到需求之后,我与后端大哥商量后,敲定了具体的实施方案。其实重要的还是要弄懂他实现的原理。需求:用户至上的体验效果,手机扫码同步登录状态很多企业在开发自己app的同时会推出网页版,为了登录更方便、更安全。企业会选用手机扫一扫,实现用户登录。神奇的是。为什么…

  • css中绝对定位_绝对定位和相对定位怎么用

    css中绝对定位_绝对定位和相对定位怎么用文章目录相对定位position:relative;特性用途绝对定位position:absolute;绝对定位参考点单独盒子绝对定位参考点:父辈元素设置了相对定位,则子元素绝对定位以父辈元素为参考点。绝对定位水平居中固定定位参考点相对定位position:relative; &lt;styletype="text/css"&gt; .box1{ width:200p…

    2022年10月27日
  • 报表开发-列表参数

    1.目的:做一个下图的筛选框-实现多选(这是在已有报表基础上加一个筛选框,如果从无到有,步骤略有不同)(点击前)(点击时)2.首先配置数据源制作报表,点击报表中任意一个指标,在左上角出现数据源3.从组件中拖一个列表参数过来4.拖过来是这样子的,右键,录入数据5.录入固定数据,绑定数据源(记得按“应用”和“确定”)添加完就下面这样了6….

  • 0x80ff0000解决方法_蓝屏代码0x0000050修复

    0x80ff0000解决方法_蓝屏代码0x0000050修复问题描述:在F盘新建文件夹或文件的时候提示0x8000FFFF灾难性错误;解决方法:1、在F盘的位置,右击选择属性2、在弹出的窗口中选择工具,点击检查3、根据系统提示进行响应的驱动扫描与修复,就酱紫咯…

  • Ubuntu18.04 安装 Idea 2018.2 Ultimate[通俗易懂]

    Ubuntu18.04 安装 Idea 2018.2 Ultimate[通俗易懂]Ubuntu18.04Idea

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号