Unity A*算法实现+演示

注意：

本文是对基于下方文章链接的理论，并最终代码实现，感谢作者大大的描述，非常详细，流程稍微做了些改动，文末有工程网盘链接，感兴趣的可以下载。

A*算法详解(个人认为最详细,最通俗易懂的一个版本)-CSDN博客

1、效果演示：

2、A*算法流程：

（1）         把起点加入 open list 。

（2）         重复如下过程：

                        a.         遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。

                        b.         对当前方格的 8连通的每一个方格            

                                         ◆     如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。

                                         ◆     如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记录该方格的 F ， G 和 H 值。

                                         ◆     如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值。

                         c.         把这个节点移到 close list 。

                         d.         停止，当你

                                         ◆     把终点加入到了 open list 中，此时路径已经找到了，或者

                                         ◆     查找终点失败，并且 open list 是空的，此时没有路径。

（3）         保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

3、代码：

逻辑层Node结点定义：

using UnityEngine;public enum GridState
{Empty,Block,
}
public class Node
{public GridState curState;public int X;public int Y;public int F;public int G;public int H;public Node parentNode;public Node(int x, int y){X = x;Y = y;ResetNode();}public void ResetNode(){curState = GridState.Empty;F = 0;G = 0;H = 0;parentNode = null;}public void CalculateValue(Node endNode){if (parentNode == null) return;//计算GG = GetPredictGValue(parentNode);//曼哈顿距离计算HH = Mathf.Abs(endNode.X - X) + Mathf.Abs(endNode.Y - Y);F = G + H;}public int GetPredictGValue(Node targetNode){int predictG = 0;//四连通if (targetNode.X == X || targetNode.Y == Y){predictG = targetNode.G + 10;}//八连通else{predictG = targetNode.G + 14;}return predictG;}}

寻路算法：

using System.Collections.Generic;public partial class PathFind
{private List<Node> openList;private List<Node> closeList;private Node[,] allNodeList;public void AStarInit(Node[,] allNodes){openList = new List<Node>();closeList = new List<Node>();allNodeList = allNodes;}public void FindRoad(Node startNode, Node endNode){openList.Add(startNode);LoopFindRoad(endNode);}private void LoopFindRoad(Node endNode){//找到终点或者不存在路径if (openList.Count == 0||openList.Contains(endNode)){return;}//找到F值最小的Node smallestFNode = null;for (int i = 0; i < openList.Count; i++){if (smallestFNode == null){smallestFNode = openList[i];continue;}if (openList[i].F<=smallestFNode.F){smallestFNode = openList[i];}}//获得八连通格子List<Node> eightAdjacent = GetRoundNode(smallestFNode);//更新代价for (int i = 0; i < eightAdjacent.Count; i++){//不在openList里面if (!openList.Contains(eightAdjacent[i])){eightAdjacent[i].parentNode = smallestFNode;eightAdjacent[i].CalculateValue(endNode);openList.Add(eightAdjacent[i]);}else{//判断是否需要更新F,G,Hif (eightAdjacent[i].GetPredictGValue(smallestFNode) <= eightAdjacent[i].G){eightAdjacent[i].parentNode = smallestFNode;eightAdjacent[i].CalculateValue(endNode);}}}//转移结点openList.Remove(smallestFNode);closeList.Add(smallestFNode);LoopFindRoad(endNode);}/// <summary>/// 获得八连通格子中可达到并且不在closeList中的格子/// </summary>/// <returns></returns>private List<Node> GetRoundNode(Node targetNode){int x = targetNode.X;int y = targetNode.Y;List<Node> tempList = new List<Node>();if (IsReachableNode(x, y + 1)) tempList.Add(allNodeList[x, y + 1]);if (IsReachableNode(x + 1, y + 1)) tempList.Add(allNodeList[x + 1, y + 1]);if (IsReachableNode(x + 1, y)) tempList.Add(allNodeList[x + 1, y]);if (IsReachableNode(x + 1, y - 1)) tempList.Add(allNodeList[x + 1, y - 1]);if (IsReachableNode(x, y - 1)) tempList.Add(allNodeList[x, y - 1]);if (IsReachableNode(x - 1, y - 1)) tempList.Add(allNodeList[x - 1, y - 1]);if (IsReachableNode(x - 1, y)) tempList.Add(allNodeList[x - 1, y]);if (IsReachableNode(x - 1, y + 1)) tempList.Add(allNodeList[x - 1, y + 1]);return tempList;}/// <summary>/// 判断格子是否可到达/// </summary>/// <param name="x"></param>/// <param name="y"></param>/// <returns></returns>private bool IsReachableNode(int x, int y){if (x >= allNodeList.GetLength(0) || x <= 0){return false;}if (y >= allNodeList.GetLength(1) || y <= 0){return false;}if (allNodeList[x, y].curState == GridState.Block){return false;}if (closeList.Contains(allNodeList[x, y])){return false;}return true;}
}

4、补充：

如果希望过障碍时，不允许他斜向过障碍，可以额外加个判断，原理很简单，对于8连通的角落点，判断角落点的4连通是否有障碍，如果有障碍就不算入可到达格子。

代码如下：

演示：

5、工程网盘链接：

通过网盘分享的文件：AStarDemo.unitypackage
链接: https://pan.baidu.com/s/1L_f1DIkqe9Oqm_dnFSSVew 提取码: 1212