如圖所示，為了向大家介紹AStar自動(dòng)尋路算法，我先用一個(gè)二維數(shù)組作為地圖的數(shù)據(jù)建立了一個(gè)如圖所示的地圖

privateint[,] map0 = new int[,]{{ 0,0,0,0,0,0,0},{ 0,1,1,1,1,1,0},{ 0,1,2,0,1,1,0},{ 0,1,1,0,1,1,0},{ 0,1,1,0,1,1,0},{ 0,1,1,1,1,1,0},{ 0,0,0,0,0,0,0}};

?

二維數(shù)組用來顯示地圖的基本信息是最為簡(jiǎn)單的一種方式，在游戲中的應(yīng)用是很多的, 例如貪吃蛇和俄羅斯方塊基本原理就是移動(dòng)方塊而已.?而一些大型游戲的地圖看起來比較平滑的起始只是進(jìn)行了些處理,?是將各種"地貌"鋪在這樣的小方塊上.?為了抽象理解看如下這張較為平滑的簡(jiǎn)易地圖作為理解

?

【問題分析】

1.????已知地圖樣貌信息和起始位置

2.????從初始方格周圍開始計(jì)算距離終止方格的信息并進(jìn)行記錄，減少信息冗余

3. ? ?可走動(dòng)方向?yàn)槠迕婵勺?個(gè)方向，但斜走時(shí)不可有上下左右墻阻擋（路徑抽象最小化如1圖可知次舉動(dòng)不可為，除非特殊情況的設(shè)定。本帖設(shè)定不可）

?

【實(shí)現(xiàn)策略】

?

1.????定義方格的信息（距離重點(diǎn)信息+移動(dòng)位置點(diǎn)信息（包含前一位置））權(quán)值

F = G + H

G: 表示從某位置移動(dòng)到網(wǎng)格上指定位置點(diǎn)的移動(dòng)耗費(fèi) (距離)—包含前一位置耗費(fèi)

H: .表示從指定的位置點(diǎn)移動(dòng)到終點(diǎn) B 的預(yù)計(jì)耗費(fèi)

2.???? 定義兩個(gè)容器

（1）“開啟列表”保存已檢測(cè)到和未到達(dá)的方格

（2）“關(guān)閉列表”保存已到達(dá)的過方格

3.???? 先將起始位置保存到（1），從（1）得到F值最小的并設(shè)為A, 再將A從（1）中移除，記錄A位置可到達(dá)方格并將他們的父親設(shè)為A并計(jì)算他們的權(quán)值并保存到（1）中。如果從（1）中得到F值最小方格為終點(diǎn)則結(jié)束

4.???? 線性遞歸 【3】

5.???? A為終點(diǎn)結(jié)束后只需從終點(diǎn)的的父節(jié)點(diǎn)開始向上遍歷則可得到完整的路徑點(diǎn)

?

?

?

【抽象分析】 使用圖例加強(qiáng)理解

◆???假設(shè)從綠方格到紅方格，將起點(diǎn)加入（1）；再從（1）得到F值最小從（1）中移除并設(shè)為A。在計(jì)算A可到達(dá)的方格加入（1）中并計(jì)算他們的權(quán)值,在將他們的父親設(shè)為A

◆???再從（1）得到F值最小的從（1）中移除并設(shè)為A。在計(jì)算A可到達(dá)的方格加入（1）中并將他們的父親設(shè)為A再計(jì)算他們的權(quán)值(需將G值進(jìn)行累==加上其父親的G值表示路程信息)，如A上面的方格G值原本位置因?yàn)槠涓赣H的G值為1所以就為1+1=2

● 從（1）得到F值最小的以第一個(gè)為先（否則只需更改算法設(shè)定）

?

?

◆???再從（1）得到F值最小的從（1）中移除并設(shè)為A。在計(jì)算A可到達(dá)的方格加入（1）中并將他們的父親設(shè)為A再計(jì)算他們的權(quán)值

◆???再從（1）得到F值最小的從（1）中移除并設(shè)為A。在計(jì)算A可到達(dá)的方格加入（1）中并將他們的父親設(shè)為A再計(jì)算他們的權(quán)值

◆???再從（1）得到F值最小的從（1）中移除并設(shè)為A。如果A為終點(diǎn)則結(jié)束

?【代碼實(shí)現(xiàn)】

Point類????? ? --方格信息類

public class Point {public Point Parent { get; set; }public float F { get; set; }public float G { get; set; }public float H { get; set; }public int mapPointX { get; set; }public int mapPointY { get; set; }public Vector2 MapVector2 { get; set; }public bool IsWall { get; set; }private bool _isVisi;public bool IsVisi { get { return _isVisi && !IsWall; } set { _isVisi = value; } }public Point(int mapX, int mapY, Point parent = null){this.mapPointX = mapX;this.mapPointY = mapY;MapVector2 = new Vector2(mapPointX, mapPointY);this.Parent = parent;IsWall = false;IsVisi = true;}public Point(bool isVisi = false){IsVisi = isVisi;}public void UpdateParent(Point parent, float g){this.Parent = parent;this.G = g;F = G + H;} }

?

AStar類????? ? --實(shí)現(xiàn)類

?

public class Astar :MonoBehaviour{private const float COST_HOR = 1f;private const float COST_VER = 1f;private const float COST_DIA = 2f;private static int mapWidth;private static int mapHeight;private static Point[,] map; //數(shù)據(jù)地圖//private static List<GameObject> objList = new List<GameObject>(); //最佳移動(dòng)點(diǎn)集private static List<Point> closeList = new List<Point>();//得到傳入的數(shù)據(jù)--初始化數(shù)據(jù)地圖--計(jì)算最佳移動(dòng)點(diǎn)集--返回最佳移動(dòng)點(diǎn)集public static Vector3[] StartMake (int[,] map0,Vector3Int sPos, Vector3Int ePos){if(sPos == ePos) return new Vector3[1] { sPos };if (sPos.x > map0.GetLength(0) || ePos.x > map0.GetLength(0) || sPos.y > map0.GetLength(1) || ePos.y > map0.GetLength(1)) {Debug.LogError("["+sPos.x + "," + sPos.y+"]["+ ePos.x+","+ ePos.y+"]");Debug.LogError("數(shù)組索引超出范圍");return new Vector3[1] { sPos };}InitMap(map0, sPos, ePos);Point start = map[sPos.x, sPos.y];Point end = map[ePos.x, ePos.y];if (FindPath(start, end)){return GetPathPoints(start, end); //返回最佳移動(dòng)點(diǎn)集}else{return new Vector3[1] { sPos };}}//初始化數(shù)據(jù)地圖static void InitMap(int[,] map0, Vector3Int start, Vector3Int end){mapWidth = map0.GetLength(0);mapHeight = map0.GetLength(1);//print(mapWidth + " " + mapHeight);map = new Point[mapWidth, mapHeight];for (int x = 0; x < mapWidth; x++) {for (int y = 0; y < mapHeight; y++) {map[x,y] = new Point(x,y);if(map0[x,y] == 0)map[x, y].IsWall = true;}}}//計(jì)算最佳移動(dòng)點(diǎn)集static bool FindPath(Point start, Point end) {List<Point> openList = new List<Point>();//List<Point> closeList = new List<Point>();closeList.Clear();openList.Add(start);while (openList.Count > 0) {Point point = GetMinF(openList);openList.Remove(point);closeList.Add(point);List<Point> surroundPoints = GetGroundPoint(point);GetSurroundPoints(surroundPoints, closeList);foreach (Point surroundPoint in surroundPoints) {if (openList.IndexOf(surroundPoint) > -1){float nowG = CalcG(surroundPoint, point);if (nowG < point.G){surroundPoint.UpdateParent(point, nowG);}}else {surroundPoint.Parent = point;CalcFGH(surroundPoint, end);FindAndSort(openList, surroundPoint);}}if (openList.IndexOf(end) > -1){return true;}else if (openList.Count == 0){break;}}return false;}static void FindAndSort(List<Point> openList, Point point){bool IsInsert = true;foreach (Point pointT in openList){if (point.mapPointX == pointT.mapPointX && point.mapPointY == pointT.mapPointY){IsInsert = false;}}if (IsInsert){openList.Add(point);}}static void GetSurroundPoints(List<Point> src, List<Point> closeList) {foreach (Point p in closeList) {if (src.IndexOf(p) > -1){src.Remove(p);}}}static List<Point> GetGroundPoint(Point point) {Point up = null, down = null, right = null, left = null;Point uR = null, uL = null, dR = null, dL = null;List<Point> tempList = new List<Point>();//上下左右if (point.mapPointY < mapHeight - 1) up = map[point.mapPointX, point.mapPointY + 1];else up = new Point();if (point.mapPointY > 0) down = map[point.mapPointX, point.mapPointY - 1];else down = new Point();if (point.mapPointX < mapWidth - 1) right = map[point.mapPointX + 1, point.mapPointY];else right = new Point();if (point.mapPointX > 0) left = map[point.mapPointX - 1, point.mapPointY];else left = new Point();//上右 上左 下右 下左 if (up.IsVisi && right.IsVisi) uR = map[point.mapPointX + 1, point.mapPointY + 1];else uR = new Point();if (up.IsVisi && left.IsVisi) uL = map[point.mapPointX - 1, point.mapPointY + 1];else uL = new Point();if (down.IsVisi && right.IsVisi) dR = map[point.mapPointX + 1, point.mapPointY - 1];else dR = new Point();if (down.IsVisi && left.IsVisi) dL = map[point.mapPointX - 1, point.mapPointY - 1];else dL = new Point();if (up.IsVisi) tempList.Add(up);if (down.IsVisi) tempList.Add(down);if (right.IsVisi) tempList.Add(right);if (left.IsVisi) tempList.Add(left);if (uR.IsVisi && up.IsVisi && right.IsVisi) tempList.Add(uR);if (uL.IsVisi && up.IsVisi && left.IsVisi) tempList.Add(uL);if (dR.IsVisi && down.IsVisi && right.IsVisi) tempList.Add(dR);if (dL.IsVisi && down.IsVisi && right.IsVisi) tempList.Add(dL);return tempList;}static Point GetMinF(List<Point> tempList) {Point point = null;float minPoint = float.MaxValue;for (int i = tempList.Count - 1; i >= 0; i--) {if (tempList[i].F <= minPoint){minPoint = tempList[i].F;point = tempList[i];}}return point;}static void CalcFGH(Point now, Point end) {// F =G + Hfloat h = Mathf.Abs(end.mapPointX - now.mapPointX) + Mathf.Abs(end.mapPointY - now.mapPointY);float g;if (now.Parent == null){g = 0;}else{float disance = Vector2.Distance(now.Parent.MapVector2, now.MapVector2);float disanceZ = Mathf.RoundToInt(disance);if (disance - disanceZ != 0){g = disance * COST_DIA + now.Parent.G;}else{if (now.Parent.mapPointX == now.mapPointX && now.Parent.mapPointY != now.mapPointY)g = disance * COST_HOR + now.Parent.G;elseg = disance * COST_VER + now.Parent.G;}}now.G = g;now.H = h;now.F = g + h;}static float CalcG(Point now, Point parent) {return Vector2.Distance(now.MapVector2, parent.MapVector2) + parent.G;}static Vector3[] GetPathPoints(Point start, Point end){List<Vector3> path = new List<Vector3>();Vector3[] pathPoints;Point point = end;while (true){path.Add(new Vector3(point.mapPointX, point.mapPointY,0));point = point.Parent;if (point == null)break;}pathPoints = new Vector3[path.Count];for (int i = 1; i <= path.Count; i++){pathPoints[i - 1] = path[path.Count - i];}return pathPoints;}}

?

AStar 輔助方法測(cè)試用

?

#region AStarPaintList<Vector3> GetPathPoints(Point start, Point end) {foreach (GameObject obj in objList) {Destroy(obj);}objList.Clear();for (int x = 0; x < mapWidth; x++){for (int y = 0; y < mapHeight; y++){if (map[x, y].IsWall){PaintSceneCube(x+ mapWidth, y, Color.black);}PaintTest(x + mapWidth, y, map[x, y]);}}List<Vector3> path = new List<Vector3>();List<Vector3> path0 = new List<Vector3>();Point point = end;while (true) {path.Add(new Vector3(point.mapPointX, 0.5f, point.mapPointY));Color color = Color.gray;if (point == start){color = Color.green;}if (point == end){color = Color.red;}PaintSceneCube(point.mapPointX+ mapWidth, point.mapPointY, color,point);point = point.Parent;if (point == null)break;}for (int i=1;i<= path.Count;i++) {path0.Add(path[path.Count - i]);}return path0;}void PaintSceneCube(int x, int y, Color color){GameObject gameObject = GameObject.CreatePrimitive(PrimitiveType.Cube);gameObject.transform.position = new Vector3(x, 0, y);gameObject.transform.SetParent(GameObject.Find("GameFaced").transform);gameObject.GetComponent<Renderer>().material.color = color;objList.Add(gameObject);}void PaintSceneCube(int x, int y, Color color,Point point) {GameObject gameObject = GameObject.CreatePrimitive(PrimitiveType.Cube);gameObject.transform.position = new Vector3(x, 0, y);gameObject.transform.SetParent(GameObject.Find("GameFaced").transform);gameObject.GetComponent<Renderer>().material.color = color;objList.Add(gameObject);}void PaintTest(int x, int y, Point point) {if (point.F <= 0)return;GameObject testObject = Instantiate(testObj);testObject.transform.position = new Vector3(x, 0.7f, y);testObject.transform.SetParent(GameObject.Find("GameFaced").transform);testObject.transform.Find("F").GetComponent<Text>().text = Mathf.RoundToInt(point.F).ToString();testObject.transform.Find("G").GetComponent<Text>().text = Mathf.RoundToInt(point.G).ToString();testObject.transform.Find("H").GetComponent<Text>().text = Mathf.RoundToInt(point.H).ToString();objList.Add(testObject);}#endregion

?

主控制類

?

public class GameManager : MonoBehaviour {private int[,] map0 = new int[,]{{ 0,0,0,0,0,0,0},{ 0,1,1,1,1,1,0},{ 0,1,2,0,1,1,0},{ 0,1,1,0,1,1,0},{ 0,1,1,0,1,1,0},{ 0,1,1,1,1,1,0},{ 0,0,0,0,0,0,0}};#region AStarprivate Astar astar = new Astar();public GameObject testObj;#endregionpublic GameObject wallObject;public GameObject planeObject;public GameObject gamePlayerObject;private GameObject gamePlayer = null;private List<Vector3> targetPos = new List<Vector3>();void Start () {Init();}// Update is called once per framevoid Update () {if (Input.GetMouseButtonDown(0)){Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);RaycastHit hit;if (Physics.Raycast(ray, out hit)){if (hit.collider.tag == "Plane"){Vector3 temp = new Vector3(hit.transform.position.x,0.5f, hit.transform.position.z);AtarGetPos(temp);//targetPos.Add(temp);}}}}private void FixedUpdate(){PlayerMove(targetPos);}void Init() {for (int i = 0; i < map0.GetLength(0); i++){for (int j = 0; j < map0.GetLength(1); j++){switch (map0[i,j]){case 0:Instantiate(wallObject, new Vector3(i, 0, j), Quaternion.identity, transform);break;case 1:Instantiate(planeObject, new Vector3(i, 0, j), Quaternion.identity, transform);break;case 2:Instantiate(planeObject, new Vector3(i, 0, j), Quaternion.identity, transform);gamePlayer = Instantiate(gamePlayerObject, new Vector3(i, 0.5f, j), Quaternion.identity);break;default:break;}}}}void PlayerMove(List<Vector3> vector3) {if (vector3.Count > 0){Vector3 pos = new Vector3((int)vector3[0].x, 0.5f, (int)vector3[0].z);gamePlayer.transform.position = pos;vector3.Remove(vector3[0]);}}void AtarGetPos(Vector3 temp) {targetPos.Clear();Vector3 pos = new Vector3((int)gamePlayer.transform.position.x, 0.5f, (int)gamePlayer.transform.position.z);targetPos = astar.StartMake(map0, gamePlayer.transform.position, temp, testObj);} }

【效果演示】? ? 右邊為AStar 輔助方法測(cè)試用

【工程代碼】

*提示：本博文中的腳本可能會(huì)與工程代碼中的有些許不同以工程代碼中的為準(zhǔn)

鏈接：? 碼云倉庫

總結(jié)

以上是生活随笔為你收集整理的自动寻路之 --AStar算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。