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 ;
}
#endregion