Unity笔记-33-AStarPathFinding算法
前言
本篇主要讲解AStarPathFinding算法核心与在Unity中的简单应用，仅限于2D场景。
- AStarPathFinding的估量代价
算法核心的寻路依据是估量代价，本算法中使用F表示
F = G + H
G表示当前点到起始点的估量代价，H表示当前点到终点的估量代价
- 地图网格化
对于一个平面地图，对其进行网格化，将其分解为多个格子
蓝色
表示障碍物
红色
表示起点
绿色
表示终点
- 地图格子
对于每一个地图格子，它都有
F，G，H
三个值，F由G与H可以得到，那么该计算得到G，H值呢？
-
G，H
值的计算
从起点开始计算，从当前中心格子遍历起点周围八个格子，
如图由中心格子向周围八个格子蔓延，并对其进行遍历。
遍历当前格子的
计算步骤
如果是障碍物则跳过不参与计算
- 计算H值
H值是从当前点到终点的估量代价，不考虑斜向仅考虑水平竖值方向的距离之和，仅需要当前格子的二维坐标的x，y值分别与终点二维坐标的x，y值差的绝对值的和，公式：abs(currentPos.x-endPos.x)+abs(currentPos.y-endPos.y)
即可获得H值
- 计算G值
首先计算当前格子与中心格子的坐标距离
公式：sqrt((currentPos.x-centerPos.x)^2+(currentPos.y-centerPos.y)^2)
该距离加上中心格子的G值，即是当前格子的G值
这样就算计算完了一个格子，然后把剩下7个格子都计算一遍。
接着，在从蔓延出来的8个格子中选择估量代价（F）最小的格子为中心重复以上步骤，计算估量代价。
这里我们会发现
一些问题
- 每次蔓延都会造成大量相同格子的估量代价重复计算。
H值每次计算都是相同的，但是每一次产生G值未必相同，因此我们需要进行筛选，我们需要最小的G值，也就是最小的估量代价。因此，每次计算新的G值，都需要进行判断，如果当前新的G值大于等于原本的G值，则不更新G值。
- 如果每个格子都无止境的向外蔓延是无法找到终点的，因此我们还需要获得这些蔓延遍历的格子并且对其进行排序与筛选以确认下一次的最佳中心格子，并且如果这个格子已经被当作中心格子遍历过了，那么就不再参与计算
因此我们需要一个
List
去存储这些遍历到的合法格子，我们称为
openList
，此外我们还需要一个List去存储那些已经被作为中心格子向外遍历过的格子，我们称为
closeList
每次计算下一个中心格子时，首先对
openList
按照估量代价进行排序（从小到大），以最小的那个格子作为下一个中心格子向外遍历，遍历获得的
新
格子被加入
openList
中，如果
openList
中已经有该格子则不重复添加。每次遍历完成后，将当前中心格子从
openList
中移除，并加入
closeList
循环判断
openList
中是否还存在格子，如果
openList.Count
为0时，则退出循环，并提示路径无法找到。如果计算下一个中心格子时该点恰好为终点，则退出循环，并回溯路径。
如何回溯路径
当中心格子去遍历周围其他格子时，如果对其赋予了新的G值，也就是相对于旧G值较小的G值，则更新G值并将中心格子作为这些格子的
parent
以能够回溯路径。
在找到终点时，根据
parent
不断向前回溯路径，就能找到起点。但是我们想要获得的路是从起点开始到终点结束的，但是回溯是反的。显然这里只需要使用栈即可。通过栈，每次回溯路径都将当前格子入栈，在回溯至起点时，开始出栈并以某种形式输出格子，以观察路径。
算法的缺陷
如果是死路，那么算法会遍历所有可能的路径，知道走到完完全全的死路才会停止，显然这其中大量计算是无用的。在我们的视角，如果这条路是死路，则应该放弃继续蔓延。而完完全全的死路在实际应用过程中通常很难出现，因此就会产生大量的无用计算，遍历的大部分格子其实都是无用的，效率过低。应该需要某种方式去计算路径，在遍历到一定程度时判断路径是否能够到达，在适当时机放弃遍历
代码示例
AStar算法类，格子模型类
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;
using Random = UnityEngine.Random;
public class AStar : MonoBehaviour
{
[Header("方块")]
public GameObject cubePrefab;
[Header("方块边长")]
public float cubeLength = 0.5f;
[Header("网格长度")]
public int gridScale = 10;
public int gridLength;
public int gridWidth;
分割线
//[Multiline(1)]
[Space]
[Header("障碍物出现概率")]
[Range(0,100)]
public int obstacleScale = 30;
[Header("起点")]
public int startX;
public int startY;
[Header("终点")]
public int endX;
public int endY;
private GridItem[,] _gridItems;
private int pathCount;
private Coroutine AStarCount = null;
private Coroutine pathFinding = null;
/// <summary>
/// 地形网格化
/// </summary>
private void GridInit()
{
gridLength = (int)(transform.localScale.x * gridScale / cubeLength);
gridWidth = (int)(transform.localScale.z * gridScale / cubeLength);
_gridItems = new GridItem[gridLength, gridWidth];
for (int i = 0; i < gridLength; i++)
{
for (int j = 0; j < gridWidth; j++)
{
GameObject cube = Instantiate(cubePrefab, new Vector3((float)i * cubeLength, 0, (float)j * cubeLength)
+ new Vector3(-gridScale / 2 * transform.localScale.x, 0, -gridScale / 2 * transform.localScale.z)//地形偏移量
+ new Vector3(cubeLength / 2, 0, cubeLength / 2)//方块偏移量
+ transform.position//地形坐标
, Quaternion.identity);
//设置父物体
cube.transform.SetParent(transform);
GridItem item = cube.GetComponent<GridItem>();
_gridItems[i, j] = item;
item.x = i;
item.y = j;
//设置Item类型
if (Random.Range(1, 101) <= obstacleScale)
{
//设置为障碍物类型
item.SetItemType(ItemType.Obstacle);
}
}
}
try
{
_gridItems[startX, startY].SetItemType(ItemType.Start);
_gridItems[endX, endY].SetItemType(ItemType.End);
}
catch (IndexOutOfRangeException e)
{
try
{
_gridItems[startX, startY].SetItemType(ItemType.Normal);
_gridItems[endX, endY].SetItemType(ItemType.Normal);
}
catch
{
}
startX = 0;
startY = 0;
endX = gridLength - 1;
endY = gridWidth - 1;
_gridItems[startX, startY].SetItemType(ItemType.Start);
_gridItems[endX, endY].SetItemType(ItemType.End);
Debug.LogWarning("起点/终点数组越界,已自动修正为默认值");
}
}
#region A Star Field
//开放列表，存储所有FGH待计算格子
private List<GridItem> openList;
//关闭列表，存储所有发现者格子
private List<GridItem> closeList;
//路径栈
private Stack<GridItem> pathStack;
#endregion
/// <summary>
/// 寻路算法
/// </summary>
IEnumerator AStarPathFinding()
{
//初始化列表
openList = new List<GridItem>();
closeList = new List<GridItem>();
pathStack = new Stack<GridItem>();
//将起点放置开启列表
openList.Add(_gridItems[startX,startY]);
//开启循环
while (openList.Count > 0)
{
yield return new WaitForSeconds(0.1f);
//按照F值排序
openList.Sort();
//找到F值最小的F值
GridItem center = openList[0];
center.SetColor(Color.gray);
if (center.itemType == ItemType.End)
{
GeneratePath(center);
//TODO:回溯找到导航路径
break;
}
//以center格子为中心去发现它周边的八个格子
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
//如果是中心则跳过
if (i == 0 && j == 0) continue;
//真正的发现格子的坐标为
int x = center.x + i;
int y = center.y + j;
//判断下标是否越界,注意要-1，下标从0开始
if (x < 0 || x > gridLength - 1) continue;
if (y < 0 || y > gridWidth - 1) continue;
//判断是否是障碍物
//临时存储当前格子
GridItem crtItem = _gridItems[x, y];
if (crtItem.parent == null)//第一次被遍历的格子
{
crtItem.SetColor(Color.yellow);
}
else
{
crtItem.SetColor(Color.cyan);
}
if (crtItem.itemType == ItemType.Obstacle) continue;
//如果该格子已经被作为中心计算过，则跳过
if (closeList.Contains(crtItem)) continue;
int H = CountH(x, y);
//赋值给格子
crtItem.H = H;
int G = CountOffsetG(i, j) + center.G;
//判断新旧G值
//如果该格子从未计算过G值，或者比原来的G值要大
if (crtItem.G == 0 || crtItem.G > G)
{
//更新G值
crtItem.G = G;
//更新发现者
crtItem.parent = center;
}
crtItem.F = crtItem.G + crtItem.H;
//将当前格子添加到openlist
if (!openList.Contains(crtItem))
{
openList.Add(crtItem);
}
}
}
//For循环结束
//将当前中心从openList中移除
openList.Remove(center);
//并添加到closeList
closeList.Add(center);
//遍历到了尽头，仍然没有找到中终点
if (openList.Count == 0)
{
Debug.Log("无法找到路径！");
break;
}
}
}
/// <summary>
/// 生成路径
/// </summary>
private void GeneratePath(GridItem item)
{
//把当前元素入栈
pathStack.Push(item);
//判断当前元素是否有发现者
if (item.parent != null)
{
//递归查找
GeneratePath(item.parent);
}
else
{
//找到起点了，路径点存储完毕
//生成路径
pathCount = pathStack.Count;
pathFinding = StartCoroutine(ShowPath());
}
}
IEnumerator ShowPath()
{
while (pathStack.Count > 0)
{
yield return new WaitForSeconds(0.7f);
GridItem item = pathStack.Pop();
if (item.itemType == ItemType.Normal)
{
item.SetColor(Color.Lerp(Color.red, Color.green, (pathCount - pathStack.Count) / (float)pathCount));
}
}
}
/// <summary>
/// 计算H，即当前点到终点的距离，不考虑斜向走
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
private int CountH(int x,int y)
{
//计算水平方向步数
int newX = x - endX;
newX = newX > 0 ? newX : -newX;
//计算垂直方向步数
int newY = y - endY;
newY = newY > 0 ? newY : -newY;
return 10 * (newX + newY);
}
private int CountOffsetG(int i,int j)
{
if (i == 0 || j == 0) return 10;
return 14;
}
[Obsolete]
private int OldCountOffsetG(int i,int j)
{
return (int)Mathf.Sqrt(i*i+j*j)*10;
}
private void DestrouAllCube()
{
for(int i = 0; i < transform.childCount; i++)
{
Destroy(transform.GetChild(i).gameObject);
}
}
private void Start()
{
GridInit();
AStarCount = StartCoroutine(AStarPathFinding());
}
private void Update()
{
if (Input.GetKeyDown(KeyCode.Space))
{
if (AStarCount != null)
StopCoroutine(AStarCount);
if (pathFinding != null)
StopCoroutine(pathFinding);
DestrouAllCube();
GridInit();
AStarCount = StartCoroutine(AStarPathFinding());
}
}
}
using System.Collections;
using System.Collections.Generic;
using System;
using UnityEngine;
public class GridItem : MonoBehaviour,IComparable<GridItem>
{
public int x;
public int y;
public ItemType itemType;
//F = G + H
public int F;
public int G;
public int H;
//发现者
public GridItem parent;
private MeshRenderer _meshRenderer;
private void Awake()
{
_meshRenderer = GetComponent<MeshRenderer>();
}
public void SetColor(Color color)
{
if (itemType == ItemType.Normal)
_meshRenderer.material.color = color;
}
public void SetItemType(ItemType itemType)
{
this.itemType = itemType;
switch (itemType)
{
case ItemType.Obstacle:
_meshRenderer.material.color = Color.blue;
break;
case ItemType.Start:
_meshRenderer.material.color = Color.red;
break;
case ItemType.End:
_meshRenderer.material.color = Color.green;
break;
case ItemType.Normal:
_meshRenderer.material.color = Color.white;
break;
}
}
public int CompareTo(GridItem other)
{
if (this.F < other.F) return -1;
else if (this.F > other.F) return 1;
else
{
return 0;
}
}
}
public enum ItemType
{
Normal,
Obstacle,
Start,
End
}