A星搜寻算法

发布时间：2017-12-26责任编辑：朱明浏览：1508

好久以前就听过A*搜寻算法，这次就好好研究下这个经典的算法。

不看不知道，一看吓一跳原来除了A*算法之外还有好多搜寻算法，比如Dijkstra 算法、BFS算法，DFS算法，这些先放一下，先主要看一下A*搜寻算法。

A*搜寻算法，俗称A星算法，作为启发式搜索算法中的一种，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。可以进行启发式的搜索，找到一条最短路径。

A*算法最为核心的部分，就在于它的一个估值函数的设计上：

f(n)=g(n)+h(n)

其中f(n)是每个可能试探点的估值，它有两部分组成：一部分，为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值，h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。

h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。

例如对于几何路网来说，可以取两节点间曼哈顿距离做为距离估计，即f=g(n) + (abs(dx - nx) + abs(dy - ny))；这样估价函数f(n)在g(n)一定的情况下，会或多或少的受距离估计值h(n)的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。

算法实现：

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

算起点的h(s);

将起点放入OPEN表;

while(OPEN!=NULL)

{

从OPEN表中取f(n)最小的节点n;

if(n节点==目标节点)

break;

for(当前节点n的每个子节点X)

{

计算f(X);

if(XinOPEN)

if(新的f(X)<OPEN中的f(X))

{

把n设置为X的父亲;

更新OPEN表中的f(n);

}

if(XinCLOSE)

continue;

if(Xnotinboth)

{

把n设置为X的父亲;

求f(X);

并将X插入OPEN表中;//还没有排序

}

}//endfor

将n节点插入CLOSE表中;

按照f(n)将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

}//endwhile(OPEN!=NULL)

保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；

算法实现（c#）：

class ProgramTest

{

static void Main(string[] args)

{

test mytest = new test();

//定义出发位置

Point pa = new Point();

pa.x = 0;

pa.y = 0;

//定义目的地

Point pb = new Point();

pb.x = 9;

pb.y = 9;

mytest.FindWay(pa, pb);

mytest.PrintMap();

Console.ReadLine();

}

class test

{

//一格代表10个单位，斜边代表14个单位,

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 }

};

//开启列表

ArrayList Open_List = new ArrayList();

//关闭列表

ArrayList Close_List = new ArrayList();

//访问列表

ArrayList _readList = new ArrayList();

//从开启列表查找F值最小的节点

private Point GetMinFFromOpenList()

{

Point Pmin = null;

for (int i = 0; i < Open_List.Count; i++)

{

if ((Pmin != null) && Pmin.GetF() > ((Point)Open_List[i]).GetF())

Pmin = (Point)Open_List[i];

if (i == 0) Pmin = (Point)Open_List[0];

}

if (Pmin != null) Open_List.Remove(Pmin);

return Pmin;

}

//获取节点的索引,list没有节点的话，返回-1

private int findNodeIndex(ArrayList list, Point node)

{

for (int i = 0; i < list.Count; i++)

{

if (((Point)list[i]).EqualTo(node))

return i;

}

return -1;

}

//计算某个点的G值

private int GetG(Point 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;

}

//计算某个点的H值

private int GetH(Point p, Point pb)

{

//曼哈顿距离算法

//一格代表10个单位，斜边代表14个单位,所以路径长度*10

return (Math.Abs(p.x - pb.x) + Math.Abs(p.y - pb.y)) * 10;

}

public void FindWay(Point pa, Point pb)

{

pa.G = 0;

pa.H = GetH(pa, pb);

Open_List.Add(pa);

Point p = null;

while (Open_List.Count > 0)

{

Point p0 = GetMinFFromOpenList();

if (p0.EqualTo(pb))

{

p = p0;

break;

}

//依次检测当前格子周围8个格子

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 < 10 && yt >= 0 && yt < 10) && !(xt == p0.x && yt == p0.y))

{

Point pt = new Point();

pt.x = xt;

pt.y = yt;

pt.father = p0;

pt.G = GetG(pt);

pt.H = GetH(pt, pb);

int no = findNodeIndex(Open_List, pt);

int nc = findNodeIndex(Close_List, pt);

float newg = pt.G;

//检测是否在open列表中，如果有且g(n)不大于新的g(n)则跳过

if (no >= 0 && ((Point)Open_List[no]).G <= newg)

continue;

//检测是否在close列表中，如果有且g(n)不大于新的g(n)则跳过

if (nc >= 0 && ((Point)Close_List[nc]).G <= newg)

continue;

//加入访问列表

_readList.Add(pt);

if (nc >= 0)

Close_List.RemoveAt(nc);

if (no >= 0)

{

//修改nt的父节点，更新open表里f(n)数据

Point nt = (Point)Open_List[no];

nt.G = (int)newg;

nt.father = p0;

nt.H = GetH(pt, pb);

}

else

{

Open_List.Add(pt);

}

Close_List.Add(p0);

}

//修改访问过的格子的值

foreach (Point item in _readList)

{

R[item.x, item.y] = 4;

}

//修改最短路径的格子的值

while (p != null)

{

R[p.y, p.x] = 3;

p = (Point)p.father;

}

//打印函数

public void PrintMap()

{

for (int a = 0; a < 10; a++)

{

for (int b = 0; b < 10; b++)

{

if (R[a, b] == 1) Console.Write("█"); //所用格子用“█”表示

else if (R[a, b] == 3) Console.Write("★"); //求得的路径用“★”表示

else if (R[a, b] == 4) Console.Write("○"); //访问过的格子用“○”表示

else Console.Write(" ");

}

Console.Write(" ");

}

class Point

{

public int y;

public int x;

public int G;

public int H;

public Point father;

public Point()

{

}

public Point(int x0, int y0, int G0, int H0, Point F)

{

x = x0;

y = y0;

G = G0;

H = H0;

father = F;

}

//获取f（n）的值

public int GetF()

{

return G + H;

}

//比较函数

public virtual bool EqualTo(Point node)

{

return (node.x == this.x) && (node.y == this.y);

}

最终从（0,0）到（9,9）的距离用“★”表示出来了。

缩略图 (2).jpg

游戏开发组供稿

A星 搜寻算法

A星搜寻算法