A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法煎娇。
注意是最有效的直接搜索算法。之后涌現(xiàn)了很多預(yù)處理算法（ALT，CH缸血，HL等等），在線查詢效率是A*算法的數(shù)千甚至上萬倍械筛。
公式表示為：f(n)=g(n)+h(n)
其中f(n)是從初始點經(jīng)由節(jié)點n到目標(biāo)點的估價函數(shù)属百，
g(n)是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，
h(n)是從n到目標(biāo)節(jié)點最佳路徑的估計代價变姨。
保證找到最短路徑（最優(yōu)解的）條件族扰，關(guān)鍵在于估價函數(shù)f(n)的選取：
估價值h(n)<= n到目標(biāo)節(jié)點的距離實際值，這種情況下渔呵，搜索的點數(shù)多怒竿，搜索范圍大，效率低扩氢。但能得到最優(yōu)解耕驰。并且如果h(n)=d(n)，即距離估計h(n)等于最短距離录豺，那么搜索將嚴(yán)格沿著最短路徑進(jìn)行朦肘，此時的搜索效率是最高的。
如果估價值>實際值,搜索的點數(shù)少双饥，搜索范圍小媒抠，效率高，但不能保證得到最優(yōu)解咏花。
using System;
usingSystem.Collections;
using System.Collections.Generic;
usingUnityEngine;
public enumGridType
{
Normal,//正常
Obstacle,//障礙物
Start,//起點
End//終點
}
//為了格子排序需要繼承IComparable接口實現(xiàn)排序
public class
MapGrid : IComparable//排序接口
{
public int x;//記錄坐標(biāo)
public int y;
public int f;//總消耗
public int g;//當(dāng)前點到起點的消耗
public int h;//當(dāng)前點到終點的消耗
public GridType type;//格子類型
public MapGrid fatherNode;//父節(jié)點
//排序
public int CompareTo(object obj)//排序比較方法ICloneable的方法
{
//升序排序
MapGrid grid = (MapGrid)obj;
if (this.f < grid.f)
{
return -1;//升序
}
if (this.f > grid.f)
{
return 1;//降序
}
return 0;
}
}
public classAStar : MonoBehaviour
{
//格子大小
public int row = 5;
public int col = 10;
public int size = 70;//格子大小
public MapGrid[,] grids;//格子數(shù)組
public ArrayList openList;//開啟列表
public ArrayList closeList;//結(jié)束列表
//開始,結(jié)束點位置
private int xStart = 2;
private int yStart = 1;
private int xEnd = 2;
private int yEnd = 5;
private StackfatherNodeLocation;
void Init()
{
grids = new MapGrid[row, col];//初始化數(shù)組
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col;j++)
{
grids[i, j] = newMapGrid();
grids[i, j].x = i;
grids[i, j].y = j;//初始化格子,記錄格子坐標(biāo)
}
}
grids[xStart, yStart].type =GridType.Start;
grids[xStart, yStart].h =Manhattan(xStart, yStart);//起點的h值
grids[xEnd, yEnd].type =GridType.End;//結(jié)束點
fatherNodeLocation = newStack();
//生成障礙物
for (int i = 1; i <= 3; i++)
{
grids[i, 3].type =GridType.Obstacle;
}
openList = new ArrayList();
openList.Add(grids[xStart,yStart]);
closeList = new ArrayList();
}
int Manhattan(int x, int y)//計算算法中的h
{
return (int)(Mathf.Abs(xEnd - x) +Mathf.Abs(yEnd - y)) * 10;
}
// Use this for initialization
void Start()
{
Init();
}
void DrawGrid()
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col;j++)
{
Color color =Color.yellow;
if (grids[i, j].type== GridType.Start)
{
color =Color.green;
}
else if (grids[i, j].type== GridType.End)
{
color =Color.red;
}
else if (grids[i,j].type == GridType.Obstacle)//障礙顏色
{
color =Color.blue;
}
else if(closeList.Contains(grids[i, j]))//關(guān)閉列表顏色如果當(dāng)前點包含在closList里
{
color = Color.yellow;
}
else { color =Color.gray; }
GUI.backgroundColor= color;
GUI.Button(newRect(j * size, i * size, size, size), FGH(grids[i, j]));
}
}
}
//每個格子顯示的內(nèi)容
string FGH(MapGrid grid)
{
string str = "F" +grid.f + "\n";
str += "G" + grid.g +"\n";
str += "H" + grid.h +"\n";
str += "(" + grid.x +"," + grid.y + ")";
return str;
}
void OnGUI()
{
DrawGrid();
for (int i = 0; i
{
//生成一個空行,存放開啟數(shù)組
GUI.Button(new Rect(i *size, (row + 1) * size, size, size), FGH((MapGrid)openList[i]));
}
//生成一個空行,存放關(guān)閉數(shù)組
for (int j = 0; j
{
GUI.Button(new Rect(j *size, (row + 2) * size, size, size), FGH((MapGrid)closeList[j]));
}
if (GUI.Button(new Rect(col *size, size, size, size), "next"))
{
NextStep();//點擊到下一步
}
}
void NextStep()
{
if (openList.Count == 0)//沒有可走的點
{
print("Over !");
return;
}
MapGrid grid =(MapGrid)openList[0];//取出openList數(shù)組中的第一個點
if (grid.type == GridType.End)//找到終點
{
print("Find");
ShowFatherNode(grid);//找節(jié)點//打印路線
return;
}
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1;j++)
{
if (!(i == 0&& j == 0))
{
int x =grid.x + i;
int y =grid.y + j;
//x,y不超過邊界,不是障礙物,不在closList里面
if (x >= 0&& x < row && y >= 0 && y < col &&grids[x, y].type != GridType.Obstacle && !closeList.Contains(grids[x,y]))
{
//到起點的消耗
int g= grid.g + (int)(Mathf.Sqrt((Mathf.Abs(i) + Mathf.Abs(j))) * 10);
if (grids[x, y].g == 0 || grids[x, y].g > g)
{
grids[x,y].g = g;
grids[x,y].fatherNode = grid;//更新父節(jié)點
}
//到終點的消耗
grids[x,y].h = Manhattan(x, y);
grids[x,y].f = grids[x, y].g + grids[x, y].h;
if (!openList.Contains(grids[x,y]))
{
openList.Add(grids[x,y]);//如果沒有則加入到openlist
}
openList.Sort();//排序
}
}
}
}
//添加到關(guān)閉數(shù)組
closeList.Add(grid);
//從open數(shù)組刪除
openList.Remove(grid);
}
//回溯法遞歸父節(jié)點
void ShowFatherNode(MapGrid grid)
{
if (grid.fatherNode != null)
{
//print(grid.fatherNode.x +"," + grid.fatherNode.y);
string str =grid.fatherNode.x + "," + grid.fatherNode.y;
fatherNodeLocation.Push(str);
ShowFatherNode(grid.fatherNode);
}
if (fatherNodeLocation.Count!=0)
{
print(fatherNodeLocation.Pop());
}
}
}
