# a*原理 unity3d

## Unity A*算法实现

2017-01-18 23:13:18 lil_black 阅读数 1096
• ###### Unity 值得看的500+ 技术内容列表

Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具，是一个全面整合的专业游戏引擎。

```using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using Astar;

namespace Astar
{
public class PathFinder : MonoBehaviour
{
List<Node> Open = new List<Node>();
List<Node> Close = new List<Node>();
List<Node> All = new List<Node>();

Node start;
Node end;

public static bool LOG { get { return false; } }
public static float F { get { return 5; } }

void Start()
{
Init();
}

//初始化
void Init()
{
Open.Clear();
Close.Clear();
for (int x = 0; x < Map.width; x++)
{
for (int z = 0; z < Map.deep; z++)
{
}
}
}

void Reset()
{
Open.Clear();
Close.Clear();
foreach (var node in All)
{
node.Reset();
}
}

public List<IntVector2> Find(IntVector2 from, IntVector2 to)
{
Reset();
if (LOG) Debug.Log("find start.");
start = GetNode(from);
start.cost = 0;
start.f = 0;
end = GetNode(to);
int count = 0;
while (Open.Count != 0)
{
var N = GetMinFNode();
if (LOG) Debug.Log("find step " + count + ":" + N.pos + " , f=" + N.f);
var dirs = new IntVector2[4] { new IntVector2(0, 1), new IntVector2(0, -1), new IntVector2(1, 0), new IntVector2(-1, 0) };
foreach (var dir in dirs)
{
bool inclose;
var X = GetNode(N.pos + dir, out inclose);
//在地图外
if (X == null)
{
continue;
}
else if (X == end)
{
X.last = N;
List<IntVector2> res = new List<IntVector2>();
var cur = end;
while (cur.last != null)
{
cur = cur.last;
}
res.Reverse();
return res;
}
//在Open内
//Debug.LogError("运行到这里了");
else if (!inclose)
{
UpdateFValue(N, X);
continue;
}
//在Close内
else if (inclose)
{
bool reOpen = UpdateFValue(N, X);
if (reOpen)
{
Close.Remove(X);
}
continue;
}
}
Debug.DrawLine((Vector3)N.pos, (Vector3)N.pos + Vector3.up, Color.red, 1);
Open.Remove(N);
}
return null;
}

/// <summary>
/// 对X的值进行更新。
/// </summary>
/// <param name="N">当前正在Close的点</param>
/// <param name="X">刷新值的点</param>
/// <returns>返回是否需要重新OPEN</returns>
bool UpdateFValue(Node N, Node X)
{
if (X.cost > N.cost + 1) X.cost = N.cost + 1;
if (X.left < 0) X.left = Node.distance(end, X);
var newF = X.cost + X.left * F;
if (newF < X.f)
{
X.f = newF;
X.last = N;
return true;
}
else return false;
}

Node GetNode(IntVector2 v, out bool inClose)
{
if (!Map.IsInMap(v))
{
inClose = false;
return null;
}
if (!Map.Walkable(v.x, v.z))
{
inClose = false;
return null;
}
for (int i = 0; i < Open.Count; i++)
{
if (Open[i].pos == v)
{
inClose = false;
return Open[i];
}
}
for (int i = 0; i < Close.Count; i++)
{
if (Close[i].pos == v)
{
inClose = true;
return Close[i];
}
}
Debug.Log("意料之外的情况");
inClose = false;
return null;
}

Node GetNode(IntVector2 v)
{
bool useless;
return GetNode(v, out useless);
}

Node GetMinFNode()
{
if (Open.Count == 0) return null;
Node result = Open[0];
foreach (var node in Open)
{
if (node.f < result.f)
{
result = node;
}
}
return result;
}

void Update()
{
if (Input.GetKeyDown(KeyCode.F))
{
IntVector2 a = (IntVector2)GameObject.Find("a").transform.position;
IntVector2 b = (IntVector2)GameObject.Find("b").transform.position;
var path = Find(a, b);
for (int i = 1; i < path.Count; i++)
{
Debug.DrawLine((Vector3)path[i - 1], (Vector3)path[i], Color.yellow, 3f);
}
path = PathFixer.Fix(path, 0.3f);
for (int i = 1; i < path.Count; i++)
{
Debug.DrawLine((Vector3)path[i - 1] + Vector3.up * 0.2f, (Vector3)path[i] + Vector3.up * 0.2f, Color.red, 3f);
}
}
}
}
}
```

a*原理 unity3d 相关内容

## A*算法理解（unity C#）

2018-10-19 17:54:56 codingriver 阅读数 4174
• ###### Unity 值得看的500+ 技术内容列表

Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具，是一个全面整合的专业游戏引擎。

#### 0X01 A*算法基本概念

F(n) = G + H。F代表当前检查点的总花费，G代表起点到当前检查点的花费，H代表当前检查点到终点的预估花费。

A*算法的特点： A*算法在理论上是时间最优的，但是也有缺点：它的空间增长是指数级别的。

#### 0X02 A*算法寻路过程

1. 将起点A添加到open列表中（A没有计算花费F是因为当前open列表只有这一个节点）。
2. 检查open列表，选取花费F最小的节点M（检查M如果为终点是则结束寻路，如果open列表没有则寻路失败，直接结束）。
3. 对于与M相邻的每一节点N：（下面本来没有序号的，csdn markdown的bug）
• 如果N是阻挡障碍，那么不管它。
• 如果N在closed列表中，那么不管它。
• 如果N不在open列表中：添加它然后计算出它的花费F(n)=G+H。
• 如果N已在open列表中：当我们使用当前生成的路径时，检查F花费是否更小。如果是，更新它的花费F和它的父节点。
4. 重复2，3步。

#### 0X03 A*算法寻路详细描述

``````    /// <summary>
/// 使用A*算法寻路
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
void FindPath(Vector2 start,Vector2 end)
{
//和A*算法无关，只是为了显示使用
int showFindNum=1;

//开启列表
List<Cell> openLs = new List<Cell>();
//关闭列表
List<Cell> closeLs = new List<Cell>();

//起点
Cell startCell = grid.GetCell(start);
//终点
Cell endCell = grid.GetCell(end);
Debug.LogFormat("寻路开始,start({0}),end({1})!",start,end);

//将起点作为待处理的点放入开启列表，

//如果开启列表没有待处理点表示寻路失败，此路不通
while(openLs.Count>0)
{
//遍历开启列表，找到消费最小的点作为检查点
Cell cur = openLs[0];
for (int i = 0; i < openLs.Count; i++)
{
if(openLs[i].fCost<cur.fCost&&openLs[i].hCost<cur.hCost)
{
cur = openLs[i];
}
}
Debug.Log("当前检查点：" + cur.ToString()+" 编号："+showFindNum+"  open列表节点数量："+openLs.Count);
//显示在界面，和A*算法无关
cur.obj.transform.Find("Num").GetComponent<Text>().text=showFindNum.ToString();
showFindNum++;

//从开启列表中删除检查点，把它加入到一个“关闭列表”，列表中保存所有不需要再次检查的方格。
openLs.Remove(cur);

//检查是否找到终点
if(cur==endCell)
{
Debug.Log("寻路结束!");
grid.CreatePath(cur);
return;
}

//根据检查点来找到周围可行走的点
//1.如果是墙或者在关闭列表中则跳过
//2.如果点不在开启列表中则添加
//3.如果点在开启列表中且当前的总花费比之前的总花费小，则更新该点信息
List<Cell> aroundCells = GetAllAroundCells(cur);
foreach (var cell in aroundCells)
{

if (cell.isWall || closeLs.Contains(cell))
continue;

int cost= cur.gCost+ GetDistanceCost(cell, cur);

if(cost<cell.gCost||!openLs.Contains(cell))
{
cell.gCost = cost;
cell.hCost = GetDistanceCost(cell,endCell);
cell.parent = cur;
Debug.Log("cell:" + cell.ToString() + "  parent:" + cur.ToString() + "  " + cell.PrintCost());
if(!openLs.Contains(cell))
{
}

//显示在界面，和A*算法无关
cell.obj.transform.Find("Cost").GetComponent<Text>().text = cell.fCost.ToString();
}

}

}

Debug.Log("寻路失败!");
}
``````

• 将起点（3，6）放到open列表中。

• 选择open列表中花费最小的点M（3，6）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算（3，6）相邻的点，一共8个点，并且分别计算花费F（红色数字），都添加到open中
+

• 选择open列表中花费最小的点M（4，6）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算（4，6）相邻的点，一共8个点，右侧是障碍物，其它5个点都在open中，分别计算当前路径花费和原来对比，都大，所以没有更新花费和父节点

• 选择open列表中花费最小的点M（4，5）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算M相邻的点，在下面有三个新节点添加open中，其它五个点要么是障碍要么是已经在open中且花费比原来大，

• 选择open列表中花费最小的点M（4，7）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算M相邻的点，在上面有三个新节点添加open中，其它五个点要么是障碍要么是已经在open中且花费比原来大，

• 选择open列表中花费最小的点M（3，5）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算M相邻的点，在左下有一个新节点添加open中，在正下面有一个点（3，4）的花费比原来小，更新该节点信息，其它的点已经在open中且花费比原来大，

• 选择open列表中花费最小的点M（3，7）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算M相邻的点，在左下有一个新节点添加open中，在正下面有一个点（3，8）的花费比原来小，更新该节点信息，其它的点已经在open中且花费比原来大，

• 选择open列表中花费最小的点M（5，4）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算M相邻的点，有五个新节点添加open中，其它三个点要么是障碍要么是已经在open中且花费比原来大，

• 选择open列表中花费最小的点M（5，8）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算M相邻的点，有五个新节点添加open中，其它三个点要么是障碍要么是已经在open中且花费比原来大，

• 选择open列表中花费最小的点M（6，5）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算M相邻的点，有四个新节点添加open中，其它四个点要么是障碍要么是已经在open中且花费比原来大或者相等，

• 选择open列表中花费最小的点M（6，7）,将M从open中移除，添加到closed列表中，后面检查时不再检查该点。

• 计算M相邻的点，有两个新节点添加open中，其它六个点要么是障碍要么是已经在open中且花费比原来大或者相等，

• 选择open列表中花费最小的点M（7，6）,将M从open中移除，添加到closed列表中，和终点对比相等，寻路结束。

A算法完全理解

A星寻路算法介绍

a*原理 unity3d 相关内容

## Unity3d利用A*寻路算法实现寻路模拟

2017-11-03 16:29:18 qq_33747722 阅读数 10583
• ###### Unity 值得看的500+ 技术内容列表

Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具，是一个全面整合的专业游戏引擎。

# 简易地图

游戏的地图, 则是将各种"地貌"铺在这样的小方块上.

# 寻路步骤

1. 从起点开始把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格

的列表.

2. 寻找起点周围可以到达的方格将它们放入"开启列表", 并设置它们的"父方格" A.

3. 从"开启列表"中删除起点 A, 并将起点加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格

"关闭列表" , 它不需要再执行检查.

"开启列表" 中找出相对最靠谱的方块, 什么是最靠谱? 它们通过公式 F=G+H 来计算.

F = G + H

G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).

H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以上下左右移动).

"开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块), 然后对它进行如下处

:

4. 把它从 "开启列表" 中删除并放到 "关闭列表" .

5. 检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑的方格如果这些方格

6. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过 C 的路径) 到达它的话, G 值是否会更低一些如果新的值更低那就把它的 "父方格" 改为目前选中的方格 C, 然后重新计算它的值和 (H 值不需要重新计算因为对于每个方块, H 值是不变的). 如果新的值比较高就说明经过再到达不是一个明智的选择因为它需要更远的路这时我们什么也不做.

# Unity代码实现

```using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarAlgorithm
{
private const int mGridWidth = 20;
private const int mGridHeight = 10;

//使用二维数组存储点网格
public AStarPoint[,] mPointGrid = new AStarPoint[mGridWidth,mGridHeight];
//存储路径方格子
public List<AStarPoint> mPathPosList = new List<AStarPoint>();

private static AStarAlgorithm _instance;
public static AStarAlgorithm GetInsatnce
{
get
{
if (_instance == null)
{
_instance = new AStarAlgorithm();
}

return _instance;
}
}

public AStarAlgorithm()
{
InitPoint();
}

//在网格上设置点的信息
private void InitPoint()
{
for (int i = 0; i < mGridWidth; i++)
{
for (int j = 0; j < mGridHeight; j++)
{
mPointGrid[i, j] = new AStarPoint(i, j);
}
}

//设置障碍物
mPointGrid[4, 2].mIsObstacle = true;
mPointGrid[4, 3].mIsObstacle = true;
mPointGrid[4, 4].mIsObstacle = true;
mPointGrid[4, 5].mIsObstacle = true;
mPointGrid[4, 6].mIsObstacle = true;

//显示障碍物
for (int x = 0; x < mGridWidth; x++)
{
for (int y = 0; y < mGridHeight; y++)
{
if (mPointGrid[x, y].mIsObstacle)
{
CreatePath(x, y, Color.blue);
}
}
}
}

public void ClearGrid()
{
for (int x = 0; x < mGridWidth; x++)
{
for (int y = 0; y < mGridHeight; y++)
{
if (!mPointGrid[x, y].mIsObstacle)
{
if (mPointGrid[x, y].mGameObject != null)
{
GameObject.Destroy(mPointGrid[x, y].mGameObject);
mPointGrid[x, y].mGameObject = null;

//重新设置父节点
mPointGrid[x, y].mParentPoint = null;
}
}
}
}
}

//寻路
public List<AStarPoint> FindPath(AStarPoint mStartPoint, AStarPoint mEndPoint)
{
if (mEndPoint.mIsObstacle || mStartPoint.mPosition == mEndPoint.mPosition)
{
return  null;
}

//开启列表
List<AStarPoint> openPointList = new List<AStarPoint>();
//关闭列表
List<AStarPoint> closePointList = new List<AStarPoint>();

while (openPointList.Count > 0)
{
//寻找开启列表中最小预算值的表格
AStarPoint minFPoint = FindPointWithMinF(openPointList);
//将当前表格从开启列表移除 在关闭列表添加
openPointList.Remove(minFPoint);
//找到当前点周围的全部点
List<AStarPoint> surroundPoints = FindSurroundPoint(minFPoint);
//在周围的点中，将关闭列表里的点移除掉
SurroundPointsFilter(surroundPoints, closePointList);
//寻路逻辑
foreach (var surroundPoint in surroundPoints)
{
if (openPointList.Contains(surroundPoint))
{
//计算下新路径下的G值（H值不变的，比较G相当于比较F值）
float newPathG = CalcG(surroundPoint, minFPoint);
if (newPathG < surroundPoint.mG)
{
surroundPoint.mG = newPathG;
surroundPoint.mF = surroundPoint.mG + surroundPoint.mH;
surroundPoint.mParentPoint = minFPoint;
}
}
else
{
//将点之间的
surroundPoint.mParentPoint = minFPoint;
CalcF(surroundPoint, mEndPoint);
}
}

//如果开始列表中包含了终点，说明找到路径
if (openPointList.IndexOf(mEndPoint) > -1)
{
break;
}
}

return ShowPath(mStartPoint, mEndPoint);
}

private List<AStarPoint> ShowPath(AStarPoint start, AStarPoint end)
{
mPathPosList.Clear();

AStarPoint temp = end;
while (true)
{

Color c = Color.white;
if (temp == start)
{
c = Color.green;
}
else if (temp == end)
{
c = Color.red;
}
CreatePath(temp.mPositionX, temp.mPositionY, c);

if (temp.mParentPoint == null)
break;
temp = temp.mParentPoint;
}

return mPathPosList;
}

private void CreatePath(int x, int y, Color color)
{
GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
go.transform.position = new Vector3(x, y, 0);
go.GetComponent<Renderer>().material.color = color;
go.transform.SetParent(GameObject.Find("Path").transform);

if (mPointGrid[x, y].mGameObject != null)
{
GameObject.Destroy(mPointGrid[x, y].mGameObject);
}
mPointGrid[x, y].mGameObject = go;
}

//寻找预计值最小的格子
private AStarPoint FindPointWithMinF(List<AStarPoint> openPointList)
{
float f = float.MaxValue;
AStarPoint temp = null;
foreach (AStarPoint p in openPointList)
{
if (p.mF < f)
{
temp = p;
f = p.mF;
}
}
return temp;
}

//寻找周围的全部点
private List<AStarPoint> FindSurroundPoint(AStarPoint point)
{
List<AStarPoint> list = new List<AStarPoint>();

////////////判断周围的八个点是否在网格内/////////////
AStarPoint up = null, down = null, left = null, right = null;
AStarPoint lu = null, ru = null, ld = null, rd = null;
if (point.mPositionY < mGridHeight - 1)
{
up = mPointGrid[point.mPositionX, point.mPositionY + 1];
}
if (point.mPositionY > 0)
{
down = mPointGrid[point.mPositionX, point.mPositionY - 1];
}
if (point.mPositionX > 0)
{
left = mPointGrid[point.mPositionX - 1, point.mPositionY];
}
if (point.mPositionX < mGridWidth - 1)
{
right = mPointGrid[point.mPositionX + 1, point.mPositionY];
}
if (up != null && left != null)
{
lu = mPointGrid[point.mPositionX - 1, point.mPositionY + 1];
}
if (up != null && right != null)
{
ru = mPointGrid[point.mPositionX + 1, point.mPositionY + 1];
}
if (down != null && left != null)
{
ld = mPointGrid[point.mPositionX - 1, point.mPositionY - 1];
}
if (down != null && right != null)
{
rd = mPointGrid[point.mPositionX + 1, point.mPositionY - 1];
}

/////////////将可以经过的表格添加到开启列表中/////////////
if (down != null && down.mIsObstacle == false)
{
}
if (up != null && up.mIsObstacle == false)
{
}
if (left != null && left.mIsObstacle == false)
{
}
if (right != null && right.mIsObstacle == false)
{
}
if (lu != null && lu.mIsObstacle == false && left.mIsObstacle == false && up.mIsObstacle == false)
{
}
if (ld != null && ld.mIsObstacle == false && left.mIsObstacle == false && down.mIsObstacle == false)
{
}
if (ru != null && ru.mIsObstacle == false && right.mIsObstacle == false && up.mIsObstacle == false)
{
}
if (rd != null && rd.mIsObstacle == false && right.mIsObstacle == false && down.mIsObstacle == false)
{
}

return list;
}

//将关闭带你从周围点列表中关闭
private void SurroundPointsFilter(List<AStarPoint> surroundPoints, List<AStarPoint> closePoints)
{
foreach (var closePoint in closePoints)
{
if (surroundPoints.Contains(closePoint))
{
Debug.Log("将关闭列表的点移除");
surroundPoints.Remove(closePoint);
}
}
}

//计算最小预算值点G值
private float CalcG(AStarPoint surround, AStarPoint minFPoint)
{
return Vector3.Distance(surround.mPosition, minFPoint.mPosition) + minFPoint.mG;
}

//计算该点到终点的F值
private void CalcF(AStarPoint now, AStarPoint end)
{
//F = G + H
float h = Mathf.Abs(end.mPositionX - now.mPositionX) + Mathf.Abs(end.mPositionY - now.mPositionY);
float g = 0;
if (now.mParentPoint == null)
{
g = 0;
}
else
{
g = Vector2.Distance(new Vector2(now.mPositionX, now.mPositionY), new Vector2(now.mParentPoint.mPositionX, now.mParentPoint.mPositionY)) + now.mParentPoint.mG;
}
float f = g + h;
now.mF = f;
now.mG = g;
now.mH = h;
}
}
```

```using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 存储寻路点信息
/// </summary>
public class AStarPoint
{
//父“格子”
public AStarPoint mParentPoint { get; set; }
//格子显示对象
public GameObject mGameObject { get; set; }

public float mF { get; set; }
public float mG { get; set; }
public float mH { get; set; }
//点的位置
public Vector2 mPosition { get; set; }
public int mPositionX { get; set; }
public int mPositionY { get; set; }
//该点是否处于障碍物
public bool mIsObstacle { get; set; }

public AStarPoint(int positionX,int positionY)
{
this.mPositionX = positionX;
this.mPositionY = positionY;
this.mPosition = new Vector2(mPositionX, mPositionY);
this.mParentPoint = null;
}
}
```

# 寻路模拟

```using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class DoPlayer : MonoBehaviour
{
private GameObject mCubeParent;

//存储路径点
private List<AStarPoint> mPathPosList;

//网格大小
private const int mGridWidth = 20;
private const int mGridHeight = 10;

private AStarPoint[,] mPointGrid;

private AStarPoint mStartPos;
private AStarPoint mEndPos { get; set; }

//每一秒发生位移
private float mTime = 0.7f;
private float mTimer = 0.0f;

//目标点
private int mTargetX { get; set; }
private int mTargetY { get; set; }

private void Start()
{
mCubeParent = GameObject.Find("Plane");

mPointGrid = AStarAlgorithm.GetInsatnce.mPointGrid;
mStartPos = mPointGrid[0, 0];

InitBG();
}

private void Update()
{
mTimer += Time.deltaTime;
if (mTimer >= mTime)
{
mTimer = 0;
Walk();
}
}

private void Walk()
{
if (mPathPosList != null && mPathPosList.Count > 1)
{
mStartPos = mPathPosList[mPathPosList.Count - 1];
Color color = mStartPos.mGameObject.GetComponent<Renderer>().material.color;
mPathPosList.Remove(mStartPos);
Destroy(mStartPos.mGameObject);
mStartPos.mGameObject = null;

mStartPos = mPathPosList[mPathPosList.Count - 1];
mStartPos.mGameObject.GetComponent<Renderer>().material.color = color;

}
}

private void InitBG()
{
for (int i = 0; i < mGridWidth; i++)
{
for (int j = 0; j < mGridHeight; j++)
{
CreateCube(i, j, Color.gray);
}
}
}

private void CreateCube(int x, int y, Color color)
{
GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
go.transform.SetParent(mCubeParent.transform);
go.transform.position = new Vector3(x, y, 0);
go.transform.localScale = new Vector3(0.9f, 0.9f, 0.9f);
go.GetComponent<Renderer>().material.color = color;

}

public void FindPath(int mTargetX, int mTargetY)
{
if (mPathPosList != null)
{
mPathPosList.Clear();
}
AStarAlgorithm.GetInsatnce.ClearGrid();

//网格点对象重新刷新了  需要使用网格来索引到点 mPathPosList存储的点是之前的AStarPoint
this.mEndPos = mPointGrid[mTargetX, mTargetY];
this.mStartPos = mPointGrid[mStartPos.mPositionX, mStartPos.mPositionY];

mPathPosList = AStarAlgorithm.GetInsatnce.FindPath(this.mStartPos, mEndPos);
}
}
```

```using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Cube : MonoBehaviour
{
public delegate void VoidDelegate(int x, int y);
public VoidDelegate FindPath;

private void OnMouseDown()
{
if (FindPath != null)
{
FindPath((int)this.transform.position.x, (int)this.transform.position.y);
}
}
}```

# 效果展示

## 原文地址：blog.liujunliang.com.cn

a*原理 unity3d 相关内容

## Unity3D A* 寻路算法

2017-05-15 14:31:24 jxw167 阅读数 2609
• ###### Unity 值得看的500+ 技术内容列表

Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具，是一个全面整合的专业游戏引擎。

CSDN视频网址：http://edu.csdn.net/lecturer/144

```void DrawSerializationSettings () {
serializationSettingsArea.Begin();
GUILayout.BeginHorizontal();

if (GUILayout.Button("Save & Load", level0LabelStyle)) {
serializationSettingsArea.open = !serializationSettingsArea.open;
}

if (script.data.cacheStartup && script.data.file_cachedStartup != null) {
GUIUtilityx.PushTint(Color.yellow);
GUILayout.Label("Startup cached", thinHelpBox, GUILayout.Height(15));
GUILayout.Space(20);
GUIUtilityx.PopTint();
}

GUILayout.EndHorizontal();

// This displays the serialization settings
script.data.cacheStartup = EditorGUILayout.Toggle(new GUIContent("Cache startup", "If enabled, will cache the graphs so they don't have to be scanned at startup"), script.data.cacheStartup);

script.data.file_cachedStartup = EditorGUILayout.ObjectField(script.data.file_cachedStartup, typeof(TextAsset), false) as TextAsset;

if (script.data.cacheStartup && script.data.file_cachedStartup == null) {
EditorGUILayout.HelpBox("No cache has been generated", MessageType.Error);
}

if (script.data.cacheStartup && script.data.file_cachedStartup != null) {
EditorGUILayout.HelpBox("All graph settings will be replaced with the ones from the cache when the game starts", MessageType.Info);
}

GUILayout.BeginHorizontal();

if (GUILayout.Button("Generate cache")) {
var serializationSettings = new Pathfinding.Serialization.SerializeSettings();
serializationSettings.nodes = true;

if (EditorUtility.DisplayDialog("Scan before generating cache?", "Do you want to scan the graphs before saving the cache.\n" +
"If the graphs have not been scanned then the cache may not contain node data and then the graphs will have to be scanned at startup anyway.", "Scan", "Don't scan")) {
}

// Save graphs
var bytes = script.data.SerializeGraphs(serializationSettings);

// Store it in a file
script.data.file_cachedStartup = SaveGraphData(bytes, script.data.file_cachedStartup);
script.data.cacheStartup = true;
}

if (GUILayout.Button("Load from cache")) {
if (EditorUtility.DisplayDialog("Are you sure you want to load from cache?", "Are you sure you want to load graphs from the cache, this will replace your current graphs?", "Yes", "Cancel")) {
}
}

GUILayout.EndHorizontal();

if (script.data.data_cachedStartup != null && script.data.data_cachedStartup.Length > 0) {
EditorGUILayout.HelpBox("Storing the cached starup data on the AstarPath object has been deprecated. It is now stored " +
"in a separate file.", MessageType.Error);

if (GUILayout.Button("Transfer cache data to separate file")) {
script.data.file_cachedStartup = SaveGraphData(script.data.data_cachedStartup);
script.data.data_cachedStartup = null;
}
}

GUILayout.Space(5);

GUILayout.BeginHorizontal();
if (GUILayout.Button("Save to file")) {
string path = EditorUtility.SaveFilePanel("Save Graphs", "", "graph.bytes", "bytes");

if (path != "") {
var serializationSettings = Pathfinding.Serialization.SerializeSettings.Settings;
if (EditorUtility.DisplayDialog("Include node data?", "Do you want to include node data in the save file. " +
"If node data is included the graph can be restored completely without having to scan it first.", "Include node data", "Only settings")) {
serializationSettings.nodes = true;
}

if (serializationSettings.nodes && EditorUtility.DisplayDialog("Scan before saving?", "Do you want to scan the graphs before saving? " +
"\nNot scanning can cause node data to be omitted from the file if the graph is not yet scanned.", "Scan", "Don't scan")) {
}

uint checksum;
var bytes = SerializeGraphs(serializationSettings, out checksum);
Pathfinding.Serialization.AstarSerializer.SaveToFile(path, bytes);

EditorUtility.DisplayDialog("Done Saving", "Done saving graph data.", "Ok");
}
}

if (GUILayout.Button("Load from file")) {
string path = EditorUtility.OpenFilePanel("Load Graphs", "", "");

if (path != "") {
byte[] bytes;
try {
} catch (System.Exception e) {
Debug.LogError("Could not load from file at '"+path+"'\n"+e);
bytes = null;
}

if (bytes != null) DeserializeGraphs(bytes);
}
}

GUILayout.EndHorizontal();
}

serializationSettingsArea.End();
}
```

```		public static void SaveToFile (string path, byte[] data) {
#if NETFX_CORE
throw new System.NotSupportedException("Cannot save to file on this platform");
#else
using (var stream = new FileStream(path, FileMode.Create)) {
stream.Write(data, 0, data.Length);
}
#endif
}

/** Load the specified data from the specified path */
public static byte[] LoadFromFile (string path) {
#if NETFX_CORE
throw new System.NotSupportedException("Cannot load from file on this platform");
#else
using (var stream = new FileStream(path, FileMode.Open)) {
var bytes = new byte[(int)stream.Length];
return bytes;
}
#endif
}```

a*原理 unity3d 相关内容

## unity3D 简单实现A*算法

2018-08-11 17:35:13 liaoshengg 阅读数 2874
• ###### Unity 值得看的500+ 技术内容列表

Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具，是一个全面整合的专业游戏引擎。

#### 前言

1. 学习A*思想
2. 其他算法，计算机估计距离
3. 曼哈顿（城市街区算法、直来直去）
4. 几何法（对角线，勾股定理）
5. 估算法（先对角线，再直线）本文使用估算法计算距离
6. GHF
7. G : 从开始到当前位置的移动步数
8. H : 从当前位置到目标位置的距离，使用上面3种算法获得
9. F ：G + H 的总和
10. OpenList 和 CloseList
11. OpenList ：被考虑最短有效路径的位置集合
12. CloseList : 不被考虑最短语效路径的位置集合
13. 寻路思想：知道F = G + H 且知道如何计算得出，知道OpenList 和CloseList并知道如何得出

#### F G H 分别表示什么，有什么用，如何计算机它们？

1. 首先得G表示的是从起始结点走到下一个结点（下下…下个）的距离，因此这个G是每走一格就会叠加一次并赋值给新的结点，从而累计得到从当前结点到下下下..个结点的距离
newCostg = gCost + GetDistance()
nodeCell.gCost = newCostg; //移动步数
2. 其次是H，它表示从当前结点到终点结点的最短距离
3. F 就是 G + H 得到的估算值

f(n)=g(n)+h(n)
f(n) 是从初始状态经由状态n到目标状态的代价估计，
g(n) 是在状态空间中从初始状态到状态n的实际代价，
h(n) 是从状态n到目标状态的最佳路径的估计代价。
（对于路径搜索问题，状态就是图中的节点，代价就是距离）

``````    //计算距离 ,这里是因为NodeItem是嵌套类，在Grid里面
public int GetDistance(Grid.NodeItem a,Grid.NodeItem b) {
//估算法
int x = Mathf.Abs (a.x - b.x);
int y = Mathf.Abs (a.y - b.y);
//根号2 = 1.4  然后都扩大10倍 去除小数计算,这里返回值都放大了10倍
if (x > y) {
return 14 * y + 10 * (x - y);
}else{
return 14 * x + 10 * (y - x);
}
//也可以用曼哈顿得到距离
//return Mathf.Abs (a.x-b.x)+Mathf.Abs(a.y-b.y);//得到正数，但是可能是浮点数
}``````

#### OpenList和CloseList是什么，可以用来做什么？

OpenList ：被考虑最短有效路径的位置集合
CloseList : 不被考虑最短语效路径的位置集合

1、从第一个结点开始，放入OpenList容器，然后这个结点获取全部周围符合条件（1）的结点；
2、把符合条件的结点全部放入OpenList容器；
3、并且还要对周围符合条件（2）的每个结点进行更新他们的G值和H值，记录这个当前结点为它们的父结点；
4、然后把这第一个结点放入CloseList容器里 这是第一次循环

5、随后进入第二次循环，

6、找到后就获取这个当前结点的周围结点，然后重新进入第2步骤到第5步骤；
7、此时它会慢慢接近终点，直到发现当前结点==最终结点；
8、最终结点找到后根据最终结点的父结点一个一个返回（类似数据结构的链表）找到开始结点；
9、此时用一个容器（List容器、Stack容器等）来接收这些结点，这些结点的Position就是最短路径

##### CS脚本代码

###### 结点类
``````using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarNode {

public bool isWall;
public int posX;
public int posY;
public int posZ;

public Vector3 pos;
public AStarNode parentNode;

public int costG;
public int costH;

public int CostF{
get{ return costG + costH; }
}

public AStarNode(bool _isWall,Vector3 _pos,int _z,int _x){
this.isWall = _isWall;
this.pos = _pos;
this.posX = _x;
this.posZ = _z;
}
}
``````

###### 结点地图生成类
``````using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarMAP : MonoBehaviour {

public AStarNode [,] AllNodeGroup;

public int xWidth;
public int zHeight;
private float nodeRange = 0.4f;

public GameObject nodeWallPrefabs;

void Awake(){
Init();
}

void Init(){

zHeight = 40;
xWidth = 40;
AllNodeGroup = new AStarNode[zHeight, xWidth];
//初始化所有结点，把结点node存入二维数组里
for (int i = 0; i < zHeight; i++) {
for (int j = 0; j < xWidth; j++) {

Vector3 nodePos =new Vector3 (j,0,i);
nodePos += new Vector3 (0.5f, 0, 0.5f);
bool isWall = Physics.CheckSphere (nodePos, nodeRange, wallLayer);
AStarNode nd = new AStarNode (isWall, nodePos,i,j);

if (isWall) {
GameObject obj = GameObject.Instantiate (nodeWallPrefabs, nodePos, Quaternion.identity) as GameObject;

}
AllNodeGroup[i,j] = nd;

}
}
}

public List<AStarNode> GetAroundNodes(AStarNode curNode){

List<AStarNode> retGroup = new List<AStarNode> ();
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (i == 0 && j == 0) {
continue;
}
int z = curNode.posZ + i;
int x = curNode.posX + j;

if (x >= 0 && x < xWidth && z >= 0 && z < zHeight) {
retGroup.Add (AllNodeGroup [z, x]);
}
}
}
return retGroup;

}

public AStarNode GetItem(Vector3 pos){
int x = Mathf.RoundToInt (pos.x - 0.5f);
int z = Mathf.RoundToInt (pos.z - 0.5f);
x = Mathf.Clamp (x, 0, xWidth - 1);
z = Mathf.Clamp (z, 0, zHeight - 1);
return AllNodeGroup [z, x];
}
}
``````
###### 找最短路径类

``````using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarFindPath : MonoBehaviour {

private AStarMAP aStarMap;

public List<Vector3> peoplePath;
public List<AStarNode> peopleNodePath;

void Start(){
aStarMap = GetComponent<AStarMAP> ();
}

private int GetDistance(AStarNode startNode,AStarNode endNode){
int x = Mathf.Abs (startNode.posX - endNode.posX);
int z = Mathf.Abs (startNode.posZ - endNode.posZ);
if (x > z) {
return 10 * (x - z) + 14 * z;
} else {
return 10 * (z - x) + 14 * x;
}
}

//根据开始和结束点来查找最优路径
private void toFindPath(Vector3 startPos,Vector3 endPos) {

//根据位置获取到NodeItem
AStarNode start = aStarMap.GetItem (startPos);
AStarNode end = aStarMap.GetItem (endPos);

List<AStarNode> openList = new List<AStarNode> ();
List<AStarNode> closeList = new List<AStarNode> ();

//从开始点开始判断
while (openList.Count > 0) {
AStarNode curNode = openList [0];
for (int i = 0; i < openList.Count; i++) {
//h是估算法的距离  f是估算法加实际格子的距离g
if (openList [i].CostF < curNode.CostF && openList [i].costH < curNode.costH) {
curNode = openList [i];
}
}

openList.Remove (curNode);

//已经找到结束点
if (curNode == end) {
Debug.Log (">>");
GetPathWithPos (startPos, endPos);
return;
}
// 获取当前点的周围点
List<AStarNode> nodeItemGroup =  aStarMap.GetAroundNodes(curNode);

//遍历当前点周围的NodeItem 对其进行
foreach (AStarNode nodeCell in nodeItemGroup) {
//先过滤： 墙 closeList
if (nodeCell.isWall || closeList.Contains (nodeCell)) {
continue;
}

//计算 G H F 进行赋值
int newCostg = curNode.costG + GetDistance (curNode, nodeCell);

if (newCostg <= nodeCell.costG || !openList.Contains (nodeCell)) {
//刷新g h
nodeCell.costG = newCostg; //移动步数距离
nodeCell.costH = GetDistance (nodeCell, end);//到该结点到终点的距离
//设置中心点为父亲
nodeCell.parentNode = curNode;
if (!openList.Contains (nodeCell)) {
}
}
}
}
}

//获取路径
private void GetPathWithPos(Vector3 startPos,Vector3 endNodePos){
//此处可以优化GC内存
peopleNodePath = new List<AStarNode> ();
peoplePath = new List<Vector3> ();

AStarNode endNode = aStarMap.GetItem (endNodePos);
AStarNode startNode = aStarMap.GetItem (startPos);

if (endNode != null) {

AStarNode temp = endNode;

while (temp != startNode) {
temp = temp.parentNode;
}
peopleNodePath.Reverse ();
peoplePath.Reverse ();
}
}
//提供给人物移动类使用
public List<Vector3> PeopleGoTo(Vector3 startpos,Vector3 endpos){
toFindPath (startpos, endpos);
return peoplePath;
}

public List<AStarNode> PeopleGoToWithNode(Vector3 startpos,Vector3 endpos){
toFindPath (startpos, endpos);
return peopleNodePath;
}
}
``````
##### 人物移动实现类

A*算法可以做出接口来用的，不过需要根据需求情况设置一些值。

``````using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PlayerTest : MonoBehaviour {

AStarFindPath astarFindPath;
public Vector3 endPos = new Vector3(12.5f,0,0.5f);
RaycastHit hit;
Ray ray;

AStarNode currentNode;
public bool isGO = true;
List<AStarNode> pathGroupNode;
void Awake(){
astarFindPath = GetComponent<AStarFindPath> ();
}
void Start () {
pathGroupNode = new List<AStarNode> ();
}
void Update(){
peopleCtrl ();
}
void peopleCtrl(){
if (Input.GetMouseButtonDown (0)) {
ray = Camera.main.ScreenPointToRay (Input.mousePosition);
if (Physics.Raycast (ray, out hit)) {
endPos = hit.point;
pathGroupNode.Clear ();
i = 1;
//执行A*算法
pathGroupNode = astarFindPath.PeopleGoToWithNode (transform.position, endPos);
if (pathGroupNode.Count <= 1) {
Debug.Log ("不需要走");
return;
}
currentNode = pathGroupNode [1];
StopAllCoroutines ();
StartCoroutine (pahtGo ());

} else {
Debug.Log ("重新点击");
}
}
}
IEnumerator pahtGo(){
while (true) {
if (Vector3.Distance (transform.position, currentNode.pos) <= 0.5f) {
currentNode = pathGroupNode[i++];
if (currentNode == null) {
Debug.Log ("到终点了...");
yield break;
}
if (i >= pathGroupNode.Count) {
Debug.Log ("到达目的地");
yield break;
}
} else {
transform.LookAt (currentNode.pos);
transform.Translate (Vector3.forward * 2f * Time.deltaTime, Space.Self);
}
yield return new WaitForEndOfFrame ();
}
}
}``````

a*原理 unity3d 相关内容