A* 算法理解与实现
发表于2018-05-18
A*算法是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。在很多游戏中都有用到该算法。
F=G（已花费）+H（将花费）；
G：直线花费10点。斜着走花费14点。
A* 算法的核心是，确定F花费最少的节点，并将节点记录下来。
1、建立节点信息类，用以处理节点。
2、确定初始节点 Node root = new Node(start);
3、利用BFS思想，确定可以拓展的节点
4、在确定可拓展节点前，拓展队列中最小花费的节点，作为将要拓展节点的父节点。（父节点唯一）
5、在可扩展节点处，实例新的节点信息，确定父节点，并计算当前节点的F、G、H值。（计算与终点的预估值H）（G为已花费）
核心在于F值的大小会影响优先级。
6、当节点坐标与终点坐标重合时，即找到目标，通过循环，将此线路的父节点压入栈中。
7、通过读取栈中的值，可以确定路线。
public class Node
｛
//坐标
public int X, Y;
//消耗
public int F, G, H;
//父节点
public Node Parent;
//计算H值
public void CalculateH(Vector2 end) ｛
this.H = (int )(10 * (Mathf.Abs(end.x - X) + Mathf.Abs(end.y - Y)));
｝
public void CalculateF() ｛
this.F = this .G + this.H;
｝
public Node( int x,int y,Node parent= null) ｛
this.X = x;
this.Y = y;
this.Parent = parent;
｝
public Node( Vector2 point,Node parent = null)
｛
this.X =(int )point.x;
this.Y = (int )point.y;
this.Parent = parent;
｝
｝
#region Segment
public static Stack <Vector2> path = new Stack <Vector2>();
Vector2 start;
Vector2 end;
public const int RowCount = 7;
public const int ColCount = 9;
byte[,] mapData = new byte [RowCount, ColCount];
Transform player;
Vector3 moveDir;
Vector3 targer;
#endregion
#region Mothed
private void Start()
｛
//LoadMapData();
//CreateMap();
//GetStartEnd();
//BFS();
//player = GameObject.CreatePrimitive(PrimitiveType.Sphere).transform;
//player.transform.position = GetPosition(start);
//targer = GetPosition(path.Peek());
｝
public void Update()
｛
moveDir = (targer - player.position).normalized;
player.Translate(moveDir* Time.deltaTime);
if (Vector3 .Distance(player.transform.position,targer)<0.1f)
｛
path.Pop();
if (path.Count==0)
｛
this.enabled = false ;
｝
else
｛
targer = GetPosition(path.Peek());
｝
｝
｝
//获取游戏数据
private void LoadMapData()
｛
string path = Application .dataPath + "/Map/map.txt";
StreamReader sr = new StreamReader(path);
string result = sr.ReadToEnd();
string[] data = result.Split(new string[] ｛ "\r\n" ｝, System.StringSplitOptions .None);
for (int i = 0; i < RowCount; i++)
｛
for (int j = 0; j < ColCount; j++)
｛
mapData[i, j] = byte.Parse(data[i][j].ToString());
｝
｝
｝
//生成地图数据
public void CreateMap()
｛
GameObject Roads = new GameObject( "Roads");
GameObject red = Resources .Load("red", typeof(GameObject )) as GameObject;
GameObject blue = Resources .Load("blue", typeof(GameObject )) as GameObject;
GameObject yellow = Resources .Load("yellow", typeof(GameObject )) as GameObject;
for (int i = 0; i < RowCount; i++)
｛
for (int j = 0; j < ColCount; j++)
｛
GameObject road = null ;
switch (mapData[i, j])
｛
case 0:
road = Instantiate(red) as GameObject ;
break;
case 1:
road = GameObject.CreatePrimitive(PrimitiveType .Cube);
break;
case 2:
road = Instantiate(blue) as GameObject ;
break;
case 9:
road = Instantiate(yellow) as GameObject ;
break;
default:
road = GameObject.CreatePrimitive(PrimitiveType .Cube);
break;
｝
road.transform.SetParent(Roads.transform);
road.transform.position = GetPosition(i, j);
road.transform.localScale = Vector3.one * 0.8f;
road.name = i.ToString() + "_" + j.ToString();
｝
｝
｝
Vector3 GetPosition( int x, int y)
｛
int pos_x = -RowCount / 3 + y;
int pos_y = ColCount / 3 + x;
return new Vector3(pos_x, 0, pos_y);
｝
Vector3 GetPosition( Vector2 pos)
｛
int pos_x = -RowCount / 3 + (int )pos.y;
int pos_y = ColCount / 3 + (int )pos.x;
return new Vector3(pos_x, 1, pos_y);
｝
void GetStartEnd()
｛
for (int i = 0; i < mapData.GetLength(0); i++)
｛
for (int j = 0; j < mapData.GetLength(1); j++)
｛
if (mapData[i, j] == 0)
｛
start.x = i;
start.y = j;
｝
else if (mapData[i, j] == 9)
｛
end.x = i;
end.y = j;
Debug.Log(new Vector2(i, j));
｝
｝
｝
｝
List< Node> list = new List< Node>();
List< Node> visited = new List< Node>();
private Vector2[] dirs = new Vector2[] ｛ Vector2.up, Vector2 .down, Vector2.left, Vector2.right, new Vector2(1, 1), new Vector2(-1, 1), new Vector2 (1, -1), new Vector2(-1, -1) ｝;
void BFS()
｛
Node root = new Node(start);
list.Add(root);
while (list.Count > 0)
｛
//f值排序
list.Sort(Comparer);
Node node = list[0];
list.Remove(node); //移除
visited.Add(node); //添加访问节点
for (int i = 0; i < dirs.Length; i++)
｛
Vector2 point;
point.x = node.X + dirs[i].x;
point.y = node.Y + dirs[i].y;
if (IsOk(point))
｛
Node n = new Node(point, node);
n.G = i > 3 ? node.G + 14 : node.G + 10;
n.CalculateH(end);
n.CalculateF();
list.Add(n);
if (point == end)
｛
Debug.Log("find" );
Node p = n;
while (p != null )
｛
Debug.Log(p.X + "\t" + p.Y);
path.Push( new Vector2 (p.X,p.Y));
p = p.Parent;
｝
return;
｝
｝
｝
｝
｝
private int Comparer(Node x, Node y)
｛
if (x.F == y.F)
｛
return 0;//表示不交互位置
｝
else if (x.F > y.F)
｛
return 1;//表示交互位置
｝
else
｛
return -1;//表示不交换位置
｝
｝
public bool IsOk(Vector2 point)
｛
if (point.x <= 0 || point.x >= mapData.GetLength(0) || point.y <= 0 || point.y >= mapData.GetLength(1))
｛
return false ;
｝
if (mapData[(int )point.x, (int)point.y] == 2)
｛
return false ;
｝
for (int i = 0; i < visited.Count; i++)
｛
if (visited[i].X == point.x && visited[i].Y == point.y)
｛
return false ;
｝
｝
for (int i = 0; i < list.Count; i++)
｛
if (list[i].X == point.x && list[i].Y == point.y)
｛
return false ;
｝
｝
return true ;
｝