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

全栈程序员站长

发布于 2022-11-08 15:40:23

5090

发布于 2022-11-08 15:40:23

文章被收录于专栏：全栈程序员必看

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

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

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

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

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

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

用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()+"}";
}
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/185196.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年10月6日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法