一.介绍
A星算法其实并不是最短路径算法,它找到的路径并不是最短的,它的目标首先是能以最快的速度找到通往目的地的路
B星实际上是A星的优化 但是B星的缺点是不能向后查找 所以会有问题
还有一种D星的可以用来找最短路径不做过多介绍
二.原理
A星通过从起始点开始,检查相邻方格的方式,向外扩展,直到找到目标;
将平面网格化通过计算每个格子的预测值来寻找最近的路径
G-当前点与起始点的距离
H-当前点与目标点的距离
F的值是G和F的和 也就是预测值或者叫总费
这里的预测值算法有好几种 例如:可以斜着走,不可以斜着走,还有一种是三角形 NavMesh 就是用这种方法的
F,G和H的评分被写在每个方格里.
A星的缺点是它的空间增长是指数级别的;(格子越多计算的量也就越大)<优化可以使用 二叉堆 >
原理的话基本上网上都能找到 我就直接上代码了
三.代码
我用得是可以斜着走的 如果是直来直往的改一下计算距离的方法就可以了
三角形的写法有兴趣可以看看NavMesh的底层
准备工作:创建出地图
将障碍物设置层级 为UnWalk
之后就可以开始敲代码了
首先创建出每个格子的节点类
public class Node
{
public bool walkable;
public int x;
public int y;
public Vector3 pos;
public int hCost;
public int gCost;
public Node parent;
public Node( int x, int y, bool walkable, Vector3 pos)
{
this.walkable = walkable;
this.x = x;
this.y = y;
this.pos = pos;
}
public int fCost { get { return gCost + hCost; } }
}
之后创建出网格
public class Grid : MonoBehaviour
{
public Transform player, target;
Node playerNode, targetNode;
public List<Node> path;
public LayerMask unwalkbaleMesk;
public Vector2 gridSizze;
public float nodeRadius;
float nodeDiameter;
public int nodeNumX;
public int nodeNumY;
public Node[,] grid;
void Start()
{
nodeDiameter = nodeRadius * 2;
nodeNumX = Mathf.RoundToInt(gridSizze.x / nodeDiameter);
nodeNumY = Mathf.RoundToInt(gridSizze.y / nodeDiameter);
CreateGrid();
}
private void CreateGrid()
{
grid = new Node[nodeNumX, nodeNumY];
Vector3 startPos = transform.position - new Vector3(gridSizze.x/2,0, gridSizze.y/2);
for (int x = 0; x < nodeNumX; x++)
{
for (int y = 0; y < nodeNumY; y++)
{
Vector3 currentPos = startPos + new Vector3(x * nodeDiameter + nodeRadius,0, y * nodeDiameter + nodeRadius);
bool walkable = !Physics.CheckSphere(currentPos, nodeRadius, unwalkbaleMesk);
grid[x, y] = new Node(x,y,walkable,currentPos);
}
}
}
public Node GetNodeFromPosition(Vector3 pos)
{
float percentX = (pos.x + gridSizze.x / 2) / gridSizze.x;
float percentY = (pos.z + gridSizze.y / 2) / gridSizze.y;
percentX = Mathf.Clamp01(percentX);
percentY = Mathf.Clamp01(percentY);
int x = Mathf.RoundToInt( percentX * (nodeNumX - 1));
int y = Mathf.RoundToInt( percentY * (nodeNumY - 1));
return grid[x,y];
}
private void OnDrawGizmos()
{
Gizmos.color = Color.green;
Gizmos.DrawCube(transform.position, new Vector3(gridSizze.x,1,gridSizze.y));
if (grid!=null)
{
foreach (Node n in grid)
{
if (n.walkable)
{
Gizmos.color = Color.grey;
if (GetNodeFromPosition(player.position)==n)
{
Gizmos.color = Color.red;
}
if (GetNodeFromPosition(target.position)==n)
{
Gizmos.color = Color.yellow;
}
if (path!=null&&path.Contains(n))
{
Gizmos.color = Color.blue;
}
Gizmos.DrawCube(n.pos,new Vector3(nodeDiameter*0.9f,1,nodeDiameter*0.9f));
}
}
}
}
void Update()
{
}
}
最后是AStar的寻路代码
public class PathFinding : MonoBehaviour
{
Grid myGrid;
Node startNode, targetNode;
private void Awake()
{
myGrid = GetComponent<Grid>();
}
void FindPath(Vector3 startPos,Vector3 targetPos)
{
startNode = myGrid.GetNodeFromPosition(startPos);
targetNode = myGrid.GetNodeFromPosition(targetPos);
List<Node> openSet = new List<Node>();
HashSet<Node> closeSet = new HashSet<Node>();
openSet.Add(startNode);
while (openSet.Count > 0)
{
Node currentNode = openSet[0];
for (int i = 1; i < openSet.Count; i++)
{
if (openSet[i].fCost < currentNode.fCost || (openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost))
{
currentNode = openSet[i];
}
}
openSet.Remove(currentNode);
closeSet.Add(currentNode);
if (currentNode == targetNode)
{
Debug.Log("Path was found");
RetrievePath(currentNode);
return;
}
foreach (Node n in GetNeighbors(currentNode))
{
if (!n.walkable||closeSet.Contains(n))
continue;
int newgCost = currentNode.fCost + GetDistance(currentNode, n);
bool inOpenSet = openSet.Contains(n);
if (newgCost<n.gCost||!inOpenSet)
{
n.gCost = newgCost;
n.hCost = GetDistance(n, targetNode);
n.parent = currentNode;
if (!inOpenSet)
{
openSet.Add(n);
}
}
}
}
}
private void RetrievePath(Node n)
{
List<Node> p = new List<Node>();
while (n != startNode)
{
p.Add(n);
n = n.parent;
}
myGrid.path = p;
}
int GetDistance(Node n1, Node n2)
{
int distanceX = (int)Mathf.Abs(n1.x - n2.x);
int distanceY = (int)Mathf.Abs(n1.y - n2.y);
if (distanceX> distanceY)
{
return 14 * (distanceY) + 10 * (distanceX - distanceY);
}
else
{
return 14 * (distanceX) + 10 * (distanceY - distanceX);
}
}
private List<Node> GetNeighbors(Node n)
{
List<Node> neighbors = new List<Node>();
int xx = n.x, yy = n.y;
for (int x = -1; x <=1; x++)
{
for (int y = -1; y <=1 ; y++)
{
if (x==0&&y==0)
continue;
if (xx+x>=0&&xx+x<myGrid.nodeNumX&&yy+y>=0&&yy+y<myGrid.nodeNumY)
{
neighbors.Add(myGrid.grid[xx + x, yy + y]);
}
}
}
return neighbors;
}
void Start()
{
}
void Update()
{
FindPath(myGrid.player.position,myGrid.target.position);
}
}
需要在地图中心创建一个空物体 之后将Grid和PathFinding挂在上边,设置起点中点就ok了
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)