前言：關(guān)于A*算法的寫法用法網(wǎng)上有很多教程厘唾，我這里只講解我目前用到的寫法褥符。
一龙誊、算法流程介紹
1.寫一個(gè)信息類
這個(gè)類的作用主要是用于保存算法地圖中每個(gè)格子的信息抚垃。
public class Point
{
public Point parent { get; set; }//該格子的父節(jié)點(diǎn)
public Vector2 worldpos;//該格子在場景中的坐標(biāo)
public int x;//算法中的x方向第幾格
public int y;//算法中的y方向第幾格
public float h;//該格子與父節(jié)點(diǎn)的距離
public float g;//該格子與目標(biāo)點(diǎn)的距離
public float f;//h與g的綜合，也是該格子在線路中的優(yōu)先級(jí)
public bool isWall;//是否是障礙物趟大，能不能通過
public Point(Vector2 worldpos, int x, int y, Point parent = null)
{
this.parent = parent;
this.worldpos = worldpos;
this.x = x;
this.y = y;
}
public void UpdateParent(Point parent, float g)
{
this.parent = parent;
this.g = g;
this.f = this.g + h;
}
}
2.繪制算法地圖
在A算法中首先要將我們?cè)趗nity中用到的地圖變換成算法中的數(shù)組鹤树。所以我們的第一步就是繪制算法地圖，以確定哪些地方可以走逊朽，哪些地方是障礙物罕伯，不可以走。繪制地圖要有一個(gè)起始原點(diǎn)叽讳，即圖中攝像機(jī)的左下角（原點(diǎn)可以自定義位置追他，我的設(shè)定的繪制地圖大小是1510，所以圖中顯示的方格數(shù)量是150個(gè)）岛蚤。
3.確定起點(diǎn)和終點(diǎn)
在范例中我是直接將目前要移動(dòng)的物體綁定為起點(diǎn)邑狸，終點(diǎn)可自己指定。
擬定A為起點(diǎn)单雾，B為終點(diǎn)
4.開始查找路徑
1、我們要寫兩個(gè)列表硅堆，用于保存信息。
- 開啟列表:
List<Point> openList = new List<Point>();
待檢查方格的集合列表够掠，尋找周圍可以達(dá)到的點(diǎn)朴乖，加入到此表中， 并保存中心點(diǎn)為父節(jié)點(diǎn) - 關(guān)閉列表：
List<Point> closeList = new List<Point>();
列表中保存不需要再次檢查的方格
2买羞、把起始點(diǎn)和終點(diǎn)的二維坐標(biāo)轉(zhuǎn)換到算法地圖中的格子位置；
public Point GetIdem(Vector2 pos)
{
int i = Mathf.RoundToInt((pos.x - ((Vector2)meshOrigin.position).x) / lengthofbox);
int j = Mathf.RoundToInt((pos.y - ((Vector2)meshOrigin.position).y) / lengthofbox);
i = Mathf.Clamp(i, 0, mapWith - 1);
j = Mathf.Clamp(j, 0, mapHeight - 1);
return map[i, j];
}
3期丰、將起始位置添加到開啟列表中。
4吃挑、開始循環(huán)钝荡。查找開啟列表中F值最小的那個(gè)方格point（不知道F值是啥的看開頭信息類代碼）（如果是第一輪，此時(shí)開啟列表內(nèi)只有起始位置）
private Point FindMinFOfPoint(List<Point> openList)
{
float f = float.MaxValue;
Point temp = null;
foreach (Point p in openList)
{
if (p.f < f)
{
temp = p;
f = p.f;
}
}
//print("返回起始列表中最小的節(jié)點(diǎn)F：" + temp.f);
return temp;
}
5舶衬、如果point是終點(diǎn)就跳出循環(huán)埠通，否則繼續(xù)執(zhí)行。
6逛犹、將point從開啟列表中移除端辱，并添加到關(guān)閉列表中。
7虽画、寫一個(gè)周圍列表用于保存point周圍的格子舞蔽。
此時(shí)是第一次循環(huán)÷胱“周圍列表”中保存的為圖中綠色格子渗柿，此時(shí)的A點(diǎn)已經(jīng)從“開啟列表”中移除，并放入到“關(guān)閉列表”中
List<Point> surroundPoints = GetSurroundPoints(point);
/// <summary>
/// 獲取當(dāng)前節(jié)點(diǎn)周圍的四個(gè)節(jié)點(diǎn)
/// </summary>
/// <param name="point"></param>
/// <returns></returns>
private List<Point> GetSurroundPoints(Point point)
{
//需要八個(gè)方向都可以走脖岛，將該方法中注釋部分代碼解開即可
Point up = null, down = null, left = null, right = null;
//Point lu = null, ru = null, ld = null, rd = null;
if (point.y < mapHeight - 1)
{
up = map[point.x, point.y + 1];
}
if (point.y > 0)
{
down = map[point.x, point.y - 1];
}
if (point.x > 0)
{
left = map[point.x - 1, point.y];
}
if (point.x < mapWith - 1)
{
right = map[point.x + 1, point.y];
}
//if (up != null && left != null)
//{
// lu = map[point.x - 1, point.y + 1];
//}
//if (up != null && right != null)
//{
// ru = map[point.x + 1, point.y + 1];
//}
//if (down != null && left != null)
//{
// ld = map[point.x - 1, point.y - 1];
//}
//if (down != null && right != null)
//{
// rd = map[point.x + 1, point.y - 1];
//}
List<Point> list = new List<Point>();
if (down != null && down.isWall == false)
{
list.Add(down);
}
if (left != null && left.isWall == false)
{
list.Add(left);
}
if (right != null && right.isWall == false)
{
list.Add(right);
}
if (up != null && up.isWall == false)
{
list.Add(up);
}
//if (lu != null && lu.isWall == false && left.isWall == false && up.isWall == false)
//{
// list.Add(lu);
//}
//if (ld != null && ld.isWall == false && left.isWall == false && down.isWall == false)
//{
// list.Add(ld);
//}
//if (ru != null && ru.isWall == false && right.isWall == false && up.isWall == false)
//{
// list.Add(ru);
//}
//if (rd != null && rd.isWall == false && right.isWall == false && down.isWall == false)
//{
// list.Add(rd);
//}
return list;
}
8朵栖、移除周圍列表里面已經(jīng)存在于關(guān)閉列表里的格子。
注意：此時(shí)是第二次循環(huán)柴梆。因?yàn)锳已經(jīng)計(jì)算過一次陨溅，寫入到在“關(guān)閉列表”里了，所以要從“周圍列表”中移除轩性，避免二次計(jì)算声登。
9狠鸳、遍歷周圍列表
- 如果開啟列表里存在周圍列表里的格子，那么判斷該格子是基于它的父節(jié)點(diǎn)優(yōu)先級(jí)（f值）高一些悯嗓，還是基于自己優(yōu)先級(jí)高一些，如果基于自己優(yōu)先級(jí)高一些則將它的父節(jié)點(diǎn)設(shè)為自己铅祸。
- 如果開啟列表中不存在該格子的父節(jié)點(diǎn)設(shè)為自己临梗，并計(jì)算它的f盟庞、h什猖、g值不狮，并添加到開啟列表中
10摇零、返回第4步循環(huán)，直到開啟列表中沒有格子為止俊嗽。（地圖全部走完）
如果此時(shí)還沒有得到完整路徑绍豁，說明無法到達(dá)終點(diǎn)（終點(diǎn)可能在障礙物中的情況）竹揍。
5.生成路徑泛型隊(duì)列
此時(shí)我們已經(jīng)在關(guān)閉列表中找到了終點(diǎn)，那么我們根據(jù)終點(diǎn)的父節(jié)點(diǎn)一直向上找就可以找到一條完整的路徑昧碉。
終點(diǎn)的g值是68被饿，它的父節(jié)點(diǎn)是58的格子狭握，58格子的父節(jié)點(diǎn)是48哎垦，依次循環(huán)就可以找到起點(diǎn)恃疯，形成圖中藍(lán)色格子路徑
private List<Point> Generatepath(Point start, Point end)
{
List<Point> path = new List<Point>();
if (end != null)
{
Point node = end;//從終點(diǎn)開始生成路線
while (node != start)
{
path.Add(node);//將節(jié)點(diǎn)放入路徑隊(duì)列中
node = node.parent;//下一個(gè)節(jié)點(diǎn)為該節(jié)點(diǎn)的父節(jié)點(diǎn)
}
path.Reverse();//將路徑節(jié)點(diǎn)倒序
}
//Debug.LogWarning(path.Count);
return path;
}
6.繪制路徑
這里需要有LineRenderer組件
private void ShowPath()
{
int count = path.Count;
if (path.Count > 0)
{
pathline.positionCount = count;
for (int i = 0; i < count; i++)
{
pathline.SetPosition(i, path[i].worldpos);
}
}
else
{
pathline.positionCount = 0;
}
}
二愿题、具體demo代碼演示
- 這里由于我的demo里面對(duì)開啟列表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了一些二叉堆優(yōu)化潘酗，看不懂的同學(xué)自行去科普二叉堆。在控制人物移動(dòng)方面可以把update里的按鍵操作代碼取消注釋攒砖，這樣人物移動(dòng)會(huì)跟精準(zhǔn)吹艇。還有我的設(shè)定是如果障礙物周圍有路面也可以到達(dá)抛猖，總而言之大家看著改吧鼻听。
using UnityEngine;
public class Point
{
public Point parent { get; set; }//該格子的父節(jié)點(diǎn)
public Vector2 worldpos;//該格子在場景中的坐標(biāo)
public int x;//算法中的x方向第幾格
public int y;//算法中的y方向第幾格
public float h;//該格子與目標(biāo)點(diǎn)的距離
public float g;//該格子與父節(jié)點(diǎn)的距離
public float f;//h與g的綜合撑教，也是該格子在線路中的優(yōu)先級(jí)
public bool isWall;//是否是障礙物伟姐，能不能通過
public Point(Vector2 worldpos, int x, int y, Point parent = null)
{
this.parent = parent;
this.worldpos = worldpos;
this.x = x;
this.y = y;
}
public void UpdateParent(Point parent, float g)
{
this.parent = parent;
this.g = g;
this.f = this.g + h;
}
}
using System.Collections.Generic;
using UnityEngine;
public class Astar : MonoBehaviour
{
public static Astar instance;
public const int mapWith = 15;//地圖的長
public const int mapHeight = 10;//地圖的寬
private Point[,] map = new Point[mapWith, mapHeight];
public GameObject Ground;//地圖不可行走格子的圖片
public GameObject Way;//地圖可行走格子的圖片
[Range(0.5f, 1.5f)]
public float lengthofbox;//地圖中每個(gè)格子大小倒戏，這個(gè)可以根據(jù)實(shí)際情況改
public LayerMask NodeLayer;//選擇障礙物所在的層
public Transform meshOrigin;//網(wǎng)格地圖起點(diǎn)對(duì)象
private void Awake()
{
instance = this;
for (int x = 0; x < mapWith; x++)
{
for (int y = 0; y < mapHeight; y++)
{
//從起始點(diǎn)meshOrigin開始繪制網(wǎng)格
Vector2 pos = new Vector2(x * lengthofbox, y * lengthofbox) + (Vector2)meshOrigin.position;
//繪制可視化地面背景
GameObject gameObject = Instantiate(Ground);
gameObject.transform.position = new Vector3(pos.x, pos.y, 100)杜跷；
gameObject.transform.SetParent(GameObject.Find("Ground").transform);
//方形范圍檢測（這里如果判斷我將能檢測到的方形碰撞盒的地方設(shè)為可行走路面葛闷，如果想改為障礙將感嘆號(hào)去掉即可）
bool iswall = !Physics2D.BoxCast(pos, new Vector2(lengthofbox, lengthofbox), 0, new Vector2(0, 0), NodeLayer);
map[x, y] = new Point(pos, x, y);
map[x, y].isWall = iswall;
}
}
}
/// <summary>
/// 繪制算法地圖
/// </summary>
private void InitMap()
{
for (int x = 0; x < mapWith; x++)
{
for (int y = 0; y < mapHeight; y++)
{
//從起始點(diǎn)meshOrigin開始繪制網(wǎng)格
Vector2 pos = new Vector2(x * lengthofbox, y * lengthofbox) + (Vector2)meshOrigin.position;
//方形范圍檢測（這里如果判斷我將能檢測到的方形碰撞盒的地方設(shè)為可行走路面，如果想改為障礙將感嘆號(hào)去掉即可）
bool iswall = !Physics2D.BoxCast(pos, new Vector2(lengthofbox, lengthofbox), 0, new Vector2(0, 0), NodeLayer);
map[x, y] = new Point(pos, x, y);
map[x, y].isWall = iswall;
}
}
}
/// <summary>
/// 二叉堆添加
/// </summary>
/// <param name="openList"></param>
/// <param name="point"></param>
private void AddPoint(List<Point> openList, Point point)
{
openList.Add(point);
int last = openList.Count - 1;
while (last >= 1)
{
int half = last >> 1;
if (openList[last].f >= openList[half].f)
{
break;
}
Point temporary = openList[last];
openList[last] = openList[half];
openList[half] = temporary;
last >>= 1;
}
}
/// <summary>
/// 二叉堆刪除
/// </summary>
/// <param name="openList"></param>
/// <param name="point"></param>
private void RemovePoint(List<Point> openList, Point point)
{
int last = openList.Count;
int head = openList.IndexOf(point) + 1;//防止索引為零，必須+1
while ((head << 1) + 1 <= last)
{
int child1 = head << 1;
int child2 = child1 + 1;
int childMin = openList[child1 - 1].f < openList[child2 - 1].f ? child1 : child2;
openList[head - 1] = openList[childMin - 1];
head = childMin;
}
openList.Remove(openList[head - 1]);
}
/// <summary>
/// 查找最優(yōu)路徑
/// </summary>
/// <param name="start">起點(diǎn)</param>
/// <param name="end">終點(diǎn)</param>
public List<Point> FindPath(Vector2 startPos, Vector2 endPos)
{
Point start = GetIdem(startPos);
Point end = GetIdem(endPos);
//Debug.LogWarning("起點(diǎn)算法坐標(biāo)"+start.x + "+" + start.y);
//Debug.LogWarning("終點(diǎn)算法坐標(biāo)"+end.x + "+" + end.y);
List<Point> openList = new List<Point>();
List<Point> closeList = new List<Point>();
AddPoint(openList, start);//將起始位置添加到Open列表
//終點(diǎn)在路面上的情況
while (openList.Count > 0)
{
Point point = openList[0];//獲取開啟列表中F值最小的格子延蟹，
if (point == end)
{
return Generatepath(start, end);
}
RemovePoint(openList, point);
closeList.Add(point);
//四周節(jié)點(diǎn)列表
List<Point> surroundPoints = GetSurroundPoints(point);
PointsFilter(surroundPoints, closeList);
foreach (Point surroundPoint in surroundPoints)
{
if (openList.IndexOf(surroundPoint) > -1)//如果周圍節(jié)點(diǎn)在起始列表中
{
// 計(jì)算經(jīng)過的Open列表中最小f值到周圍節(jié)點(diǎn)的G值
float nowG = CalcG(surroundPoint, surroundPoint.parent);
if (nowG < surroundPoint.g)
{
surroundPoint.UpdateParent(point, nowG);
}
}
else
{
surroundPoint.parent = point;//設(shè)置周圍列表的父節(jié)點(diǎn)
CalcF(surroundPoint, end);//計(jì)算周圍節(jié)點(diǎn)的F，G,H值
AddPoint(openList, surroundPoint); //最后將周圍節(jié)點(diǎn)添加進(jìn)Open列表
}
}
}
//終點(diǎn)在障礙物上沥匈，且障礙物周圍至少有一格為路面的情況
List<Point> endSurroundPoints = GetSurroundPoints(end);//終點(diǎn)周圍格子
Point optimal = null;//最優(yōu)點(diǎn)
foreach (Point surroundPoint in endSurroundPoints)
{
if (closeList.IndexOf(surroundPoint) > -1)
{
if (optimal != null)
{
if (surroundPoint.g < optimal.g)
optimal = surroundPoint;
}
else
{
optimal = surroundPoint;
}
}
}
if (optimal != null)
{
return Generatepath(start, optimal);
}
//終點(diǎn)在障礙物上，無法到達(dá)
Debug.LogWarning("找不到路徑");
return Generatepath(start, null);
}
/// <summary>
/// 獲取坐標(biāo)點(diǎn)在算法地圖中的坐標(biāo)
/// </summary>
/// <param name="pos"></param>
/// <returns></returns>
public Point GetIdem(Vector2 pos)
{
int i = Mathf.RoundToInt((pos.x - ((Vector2)meshOrigin.position).x) / lengthofbox);
int j = Mathf.RoundToInt((pos.y - ((Vector2)meshOrigin.position).y) / lengthofbox);
i = Mathf.Clamp(i, 0, mapWith - 1);
j = Mathf.Clamp(j, 0, mapHeight - 1);
return map[i, j];
}
/// <summary>
/// 獲取當(dāng)前節(jié)點(diǎn)周圍的四個(gè)節(jié)點(diǎn)
/// </summary>
/// <param name="point"></param>
/// <returns></returns>
private List<Point> GetSurroundPoints(Point point)
{
//需要八個(gè)方向都可以走散址，將該方法中注釋部分代碼解開即可
Point up = null, down = null, left = null, right = null;
//Point lu = null, ru = null, ld = null, rd = null;
if (point.y < mapHeight - 1)
{
up = map[point.x, point.y + 1];
}
if (point.y > 0)
{
down = map[point.x, point.y - 1];
}
if (point.x > 0)
{
left = map[point.x - 1, point.y];
}
if (point.x < mapWith - 1)
{
right = map[point.x + 1, point.y];
}
//if (up != null && left != null)
//{
// lu = map[point.x - 1, point.y + 1];
//}
//if (up != null && right != null)
//{
// ru = map[point.x + 1, point.y + 1];
//}
//if (down != null && left != null)
//{
// ld = map[point.x - 1, point.y - 1];
//}
//if (down != null && right != null)
//{
// rd = map[point.x + 1, point.y - 1];
//}
List<Point> list = new List<Point>();
if (down != null && down.isWall == false)
{
list.Add(down);
}
if (left != null && left.isWall == false)
{
list.Add(left);
}
if (right != null && right.isWall == false)
{
list.Add(right);
}
if (up != null && up.isWall == false)
{
list.Add(up);
}
//if (lu != null && lu.isWall == false && left.isWall == false && up.isWall == false)
//{
// list.Add(lu);
//}
//if (ld != null && ld.isWall == false && left.isWall == false && down.isWall == false)
//{
// list.Add(ld);
//}
//if (ru != null && ru.isWall == false && right.isWall == false && up.isWall == false)
//{
// list.Add(ru);
//}
//if (rd != null && rd.isWall == false && right.isWall == false && down.isWall == false)
//{
// list.Add(rd);
//}
return list;
}
/// <summary>
/// 將關(guān)閉列表中已經(jīng)存在的節(jié)點(diǎn)從周圍節(jié)點(diǎn)中移除
/// </summary>
/// <param name="surroundPoints">四周節(jié)點(diǎn)列表</param>
/// <param name="closeList">關(guān)閉列表</param>
private void PointsFilter(List<Point> surroundPoints, List<Point> closeList)
{
foreach (Point p in closeList)
{
if (surroundPoints.IndexOf(p) > -1)
{
surroundPoints.Remove(p);
}
}
}
/// <summary>
/// 計(jì)算經(jīng)過起始列表中最小f值到周圍節(jié)點(diǎn)的G值
/// </summary>
/// <param name="surroundPoint"></param>
/// <param name="parent"></param>
/// <returns></returns>
private float CalcG(Point surroundPoint, Point parent)
{
return Vector2.Distance(new Vector2(surroundPoint.x, surroundPoint.y), new Vector2(parent.x, parent.y)) + parent.g;
}
/// <summary>
/// 計(jì)算周圍節(jié)點(diǎn)的F拉背，G椅棺，H值
/// </summary>
/// <param name="surroundPoint"></param>
/// <param name="end"></param>
private void CalcF(Point surroundPoint, Point end)
{
//F = G + H
float h = Mathf.Abs(end.x - surroundPoint.x) + Mathf.Abs(end.y - surroundPoint.y);
float g = 0;
if (surroundPoint.parent == null)
{
g = 0;
}
else
{
g = Vector2.Distance(new Vector2(surroundPoint.x, surroundPoint.y), new Vector2(surroundPoint.parent.x, surroundPoint.parent.y)) + surroundPoint.parent.g;
}
float f = g + h;
surroundPoint.f = f;
surroundPoint.g = g;
surroundPoint.h = h;
}
/// <summary>
/// 生成路徑泛型隊(duì)列
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
private List<Point> Generatepath(Point start, Point end)
{
List<Point> path = new List<Point>();
if (end != null)
{
Point node = end;//從終點(diǎn)開始生成路線
while (node != start)
{
path.Add(node);//將節(jié)點(diǎn)放入路徑隊(duì)列中
node = node.parent;//下一個(gè)節(jié)點(diǎn)為該節(jié)點(diǎn)的父節(jié)點(diǎn)
}
path.Reverse();//將路徑節(jié)點(diǎn)倒序
}
//Debug.LogWarning(path.Count);
return path;
}
private void Update()
{
//當(dāng)?shù)貓D發(fā)生改變后重新繪制算法地圖
if (Input.GetKeyDown(KeyCode.Q))
{
InitMap();
}
}
}
using System.Collections.Generic;
using UnityEngine;
public class Move : MonoBehaviour
{
[Range(0.5f, 3f)]
public float speed = 1.5f;//移動(dòng)速度
public GameObject end;//終點(diǎn)
private LineRenderer pathline;//給對(duì)象添加LineRenderer組件
[Range(0.1f, 2f)]
public float lineWidth = 0.2f;//線寬
private int order = 0;//路徑隊(duì)列中當(dāng)前坐標(biāo)序號(hào)
private List<Point> path = new List<Point>();//路徑
private Vector3 vector3;//移動(dòng)方向
void Start()
{
//路徑繪畫初始化
pathline = gameObject.GetComponent<LineRenderer>();
pathline.startWidth = lineWidth;
pathline.endWidth = lineWidth;
}
void Update()
{
//if (Input.GetKeyDown(KeyCode.W))
{
path.Clear();
order = 0;
//獲取路徑
path = new List<Point>(Astar.instance.FindPath(gameObject.transform.position, end.transform.position));
//計(jì)算初始行走方向
if (path.Count > 0)
vector3 = new Vector3(path[order].worldpos.x, path[order].worldpos.y, path[order].worldpos.y) - gameObject.transform.position;
Debug.LogWarning(gameObject.name + ";" + path.Count);
ShowPath();
}
//開始移動(dòng)
Run();
}
private void Run()
{
if (path.Count > 0)
{
//開始向下個(gè)路徑點(diǎn)位移
gameObject.transform.position += vector3.normalized * speed * Time.deltaTime;
//如果到達(dá)下一個(gè)路徑點(diǎn)
if (Vector3.Distance(new Vector3(path[order].worldpos.x, path[order].worldpos.y, path[order].worldpos.y), gameObject.transform.position) <= 0.1f)
{
print(gameObject.name + ":" + path[order].f + ";" + order + "; " + path[order].worldpos);
order++;
//如果沒有下個(gè)路徑點(diǎn)了
if (path.Count <= order)
{
path.Clear();
order = 0;
}
else
{
//計(jì)算下個(gè)路徑點(diǎn)行走方向
vector3 = new Vector3(path[order].worldpos.x, path[order].worldpos.y, path[order].worldpos.y) - gameObject.transform.position;
}
}
}
}
/// <summary>
/// 繪制路徑
/// </summary>
private void ShowPath()
{
int count = path.Count;
if (path.Count > 0)
{
pathline.positionCount = count;
for (int i = 0; i < count; i++)
{
pathline.SetPosition(i, path[i].worldpos);
}
}
else
{
pathline.positionCount = 0;
}
}
}
