基于unity实现A*寻路算法
基于unity实现A*寻路算法
·
目录
实现原理
在寻路的过程中会用到一个开启列表和一个关闭列表
开启列表:用于存放待选取节点,每次遍历周围节点后都会在开启列表中寻找当前最优节点放入关闭列表。
关闭列表:用于存放待确定路径集合,当放入的节点为终点时进行回溯获取最短路径。
g值:表示地点到站立点的曼哈顿距离
h值:站立点到终点的的曼哈顿距离
f值:g值与h值之和,为过该站立点从起点到终点的距离,通过该值筛选出最优路径。
实现思路
1.先将起始点放入开启列表中,将站立点设置为起点。
2.遍历站立点周围的节点如果能到达且该节点未置于开启或是关闭列表中时将其添加到开启列表中。
3.对开启列表进行排序寻找最其中f值最小的节点,并把该节点删除并放入关闭列表中,并将站立点改为该点。
4.循环2,3操作直至找到路径,或是当开启列表为空时则表明无法到达终点。
具体步骤
定义单位格基础类
public class node
{
public int x, y;//坐标(x,y)
public float f,g,h;//f(路径长度)=g(距起点长度)+h(距终点长度)
public node parent;
public NodeType type;
public node(int x,int y,NodeType type)
{
this.x = x;
this.y = y;
this.type = type;
}
}
初始化场景
NodeManager.GetInstance.MapInfo(mapW,mapH);
for(int i=0;i<mapW;i++)
for(int j=0;j<mapH;j++)
{
GameObject obj = GameObject.CreatePrimitive(PrimitiveType.Cube);
obj.transform.position = new Vector3(beginx + i * offsetx, beginy + j * offsety, 0);
obj.GetComponent<MeshRenderer>().material = normal;
node Node = NodeManager.GetInstance.Nodes[i, j];
a[obj] = Node; b[Node]=obj;
if (Node.type==NodeType.stop)
{
obj.GetComponent<MeshRenderer>().material=red;
}
}
寻路
public List<node> FindWay(Vector2Int start,Vector2Int end)
{
if(start.x<0|start.x>=mapWide|
start.y<0|start.y>=mapHigh|
end.x<0|end.x>=mapWide|
end.y<0|end.y>=mapHigh)//判断起点,终点是否合法
{
return null;
}
if(Nodes[start.x,start.y].type==NodeType.stop|
Nodes[end.x, end.y].type == NodeType.stop)//判断起点或终点是否可到达
{
return null;
}
closeList.Clear();
openList.Clear();
Nodes[start.x, start.y].parent = null;
Nodes[start.x, start.y].f = 0;
Nodes[start.x, start.y].g = 0;
Nodes[start.x, start.y].h = 0;
closeList.Add(Nodes[start.x, start.y]);
while(true)//遍历四周方格
{
FindOpenlist(start.x -1, start.y , 1, Nodes[start.x, start.y], Nodes[end.x, end.y]);
FindOpenlist(start.x , start.y + 1, 1 , Nodes[start.x, start.y], Nodes[end.x, end.y]);
FindOpenlist(start.x , start.y-1, 1, Nodes[start.x, start.y], Nodes[end.x, end.y]);
FindOpenlist(start.x + 1, start.y, 1 , Nodes[start.x, start.y], Nodes[end.x, end.y]);
if (openList.Count==0)
{
return null;
}
openList.Sort((node a,node b)=>{ if (a.f >= b.f) return 1; else return -1; });//排序选出当前最短距终点的点
closeList.Add(openList[0]);
start.Set(openList[0].x, openList[0].y);
openList.RemoveAt(0);
if(Nodes[start.x, start.y]== Nodes[end.x, end.y])
{
List<node> way = new List<node>();
way.Clear();
way.Add(Nodes[end.x, end.y]);
while(Nodes[end.x, end.y].parent!=null)
{
way.Add(Nodes[end.x, end.y].parent);
end.Set(Nodes[end.x, end.y].parent.x, Nodes[end.x, end.y].parent.y);
}
way.Reverse();//反转列表使路径从开始到终点
return way;
}
}
}
private void FindOpenlist(int x,int y,float g,node parent,node end)
{
if(x<0|x>=mapWide|
y<0|y>=mapHigh)
{
return;
}
node Node = Nodes[x, y];
if (Node == null |
Node.type == NodeType.stop |
closeList.Contains(Node) |
openList.Contains(Node))
return;
Node.parent = parent;
Node.g = parent.g + g;
Node.h = Mathf.Abs(end.x - Node.x) + Mathf.Abs(end.y - Node.y);
Node.f = Node.g + Node.h;
openList.Add(Node);
}
显示路径
IEnumerator way(List<node> way)
{
foreach(var a in way)
{
b[a].gameObject.GetComponent<MeshRenderer>().material = green;
yield return new WaitForSeconds(0.5f);
}
}
演示效果
能够到达
不能到达
更多推荐
已为社区贡献1条内容
所有评论(0)