[ACM]A* Path Finding Implementation

一个U3D中的A*实现

关于A*的一些原理相关资料网上有很多，可以搜搜，下面只给出U3D中一个A*的基于C#的实现实例：

最终效果

准备工作

场景中包括一个代表可行走区域的plane,不可行走区域的蓝色Cube,代表玩家的球体player和代表目标点的球体EndPoint，A*是空的gameobject,仅用于添加脚本。其中Cube的tag全部设为Unwalkable表示为障碍物。

首先我们需要将一个平面划分为一些小方格，每个方格都是一个节点，所以先定义一个节点类，并进行一些准备工作：

public class Node{
 public bool _canWalk; // 是否可以通过（障碍物）
 public Vector3 _worldPos; 
 public int _gridX, _gridY; // 网格索引，对应节点位置
 public int gCost; // 到起始点的距离 
 public int hCost; // 到目标点的距离
 public int fCost{ // 总路径消耗 
   get{return gCost + hCost;}
 }
 public Node parent;

 // Node构造函数
 public Node(bool CanWalk,Vector3 Postion,int x,int y) {
  _canWalk = CanWalk;
  _worldPos = Postion;
  _gridX = x;
  _gridY = y;
 }
}

接着在start中对数据初始化，创建节点，根据需要的精细度，可以自己调节每个节点的大小

void Start () {
//数据初始化
  nodeDiameter = nodeRadius * 2;//计算直径
  gridCntX = Mathf.RoundToInt (gridSize.x / nodeDiameter);//计算各个方向的格子数,mathf取整
  gridCntY = Mathf.RoundToInt (gridSize.y / nodeDiameter);
  grid = new Node[gridCntX, gridCntY];//网格数组初始化
  CreateGrid ();//创建节点 
}

 private void CreateGrid(){
  Vector3 startPoint = transform.position - gridSize.x / 2 *
  Vector3.right-Vector3.forward*gridSize.y/2;        //选定区域左下角节点作为初始点
  for (int i=0; i < nodeDiameter; i++) {
      for (int j=0; j < nodeDiameter; j++) {
                //获取每个节点的位置（之前全部节点直径加本节点半径）
      Vector3 worldPoint = startPoint+Vector3.right*(i*nodeDiameter + nodeRadius) + Vector3.forward*(j*nodeDiameter + nodeRadius);
                //检测碰撞，没有检测到碰撞时返回true,表示可行走区域
    bool walkable=!Physics.CheckSphere(worldPoint,nodeRadius,WhatLayer);
                //初始化完成，向数组中添加新节点   
    grid[i,j]=new Node(walkable,worldPoint,i,j);
    }
  }
 }

节点创建完之后需要在场景视图中画出来:

void OnDrawGizmos(){
  Gizmos.DrawWireCube (transform.position, new Vector3 (gridSize.x, 1, gridSize.y));
        //画出网格边缘（中心位置，方块大小（纵轴，高度，横轴））
  if (grid == null) return;//数组为空，返回
  Node playerNode = GetFromPostion (player.position);//获取玩家位置  foreach (var node in grid) {
//遍历，如果可以行走标记为白色
   Gizmos.color=node._canWalk ? Color.white : Color.red;
//红色区域可能为不太精确，可以提高网格密度提高精度
   Gizmos.DrawCube(node._worldPos,Vector3.one*(nodeDiameter-.1f));
            //画出格子，-0.1f使得每个格子周围存在空隙
  }
  if (playerNode != null && playerNode._canWalk) {
   Gizmos.color = Color.cyan;
   Gizmos.DrawCube(playerNode._worldPos,Vector3.one*(nodeDiameter-.1f));
  }
//将玩家所在位置格子更新为青色
 }

算法部分

做完准备工作，接下来就是算法的部分，我们新建一个FindPath的脚本：

public class FindPath : MonoBehaviour {

 public Transform player, Endpoint; 
 private Grid _grid;

 void Start () {
  _grid = GetComponent (); 
} 

 void Update () {
  FindingPath (player.position, Endpoint.position); 
}

 void FindingPath(Vector3 StartPos,Vector3 EndPos){
  Node startNode = _grid.GetFromPostion (StartPos);
  Node EndNode = _grid.GetFromPostion (EndPos);
  List openSet = new List();//开启列表
  HashSet closeSet = new HashSet();//关闭列表
  openSet.Add(startNode);//放入起始节点
  while (openSet.Count>0) {//若开启列表还有元素
   Node currentNode = openSet[0];//如果当前节点是最优节点

   for(int i=0;i <openSet.Count;i++) {
    if(openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost){
                    //总fCost相同且小于当前hCost
     currentNode = openSet[i];
    }
   }
   openSet.Remove(currentNode);//从开启列表移除
   closeSet.Add(currentNode);//添加到关闭列表
   if(currentNode == EndNode){//当前Node为目标节点，结束查询
    GeneratePath(startNode,EndNode);
    return ;
   }

   foreach(var node in _grid.GetNeibourhood(currentNode)){
    if(!node._canWalk || closeSet.Contains(node)) continue;//跳过不能走的节点 
   int newCost = currentNode.gCost+GetDistanceNodes(currentNode,node);                //当前耗费

    if(newCost < currentNode.fCost) {
     node.gCost=newCost;
     node.hCost=GetDistanceNodes(node,EndNode);
     node.parent=currentNode;
     if(!openSet.Contains(node)){
      openSet.Add (node);
     }
    }
   }
  }
 }

 private void GeneratePath(Node startNode,Node endNode){
        //回溯，找到开始节点
  List path = new List ();
  Node temp = endNode;
  while (temp!=startNode) {
//不是开始节点，继续循环
   path.Add(temp);
   temp = temp.parent;            //不断向上循环父节点
  }

  path.Reverse ();
//路径反向
  _grid.path = path;
 }

 int GetDistanceNodes(Node a,Node b){
//获取两节点间距离
  int cntX = Mathf.Abs (a._gridX - b._gridX);//在x轴相差格数
  int cntY = Mathf.Abs (a._gridY - b._gridY);//在y轴相差格数
  if (cntX > cntY) {
      return 14 * cntY + 10 * (cntX - cntY);//14为斜边距离*10,乘以相差格数
     }
   else {
   return 14*cntX+10*(cntY-cntX);
  }
 }
}

同时，需要在之前的脚本中获取到相邻节点：

public List GetNeibourhood(Node node){//相邻节点列表
    List neibourhood = new List ();
    for (int i=-1; i<=1; i++) {
      for (int j=-1; j<=1; j++) {
        if (i==0 && j==0) continue;
        int tempX = node._gridX + i;
        int tempY = node._gridY + j;
        if (tempX < gridCntX && tempX > 0 && tempY > 0 && tempY < gridCntY) { 
           //是否越界
          neibourhood.Add (grid [tempX, tempY]);
        }
      }
    }
  return neibourhood;
  }

最后用黑色格子画出最终路径：

if (path != null) {
         //画出最终路径
    foreach(var node in path){
    Gizmos.color=Color.black;//路径为黑色
    Gizmos.DrawCube(node._worldPos,Vector3.one*(nodeDiameter-.1f));
   }
  }

运行一下就可以看到效果，可以很方便地添加到自己的游戏项目中使用

The End