devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Unity 中的简单A*寻路 （AStar寻路）实现

作者：从前慢现在也慢 | 2024-02-16 15:43:49

赞

踩

Unity 中的简单A*寻路 （AStar寻路）实现

本文实现的A*算法，未经过大量的优化，后续文章会进一步实现优化

后篇：A*优化讨论

寻路代码实现

结点类：

  1. using System.Collections;
  2. using System.Collections.Generic;
  3. using UnityEngine;
  4.  
  5. public enum E_Node_Type
  6. {
  7.     /// <summary>
  8.     /// 可行走
  9.     /// </summary>
  10.     Normal,
  11.     /// <summary>
  12.     /// 障碍
  13.     /// </summary>
  14.     Obstacles
  15. }
  16.  
  17.  
  18. public class AStarNode 
  19. {
  20.     /// <summary>
  21.     /// x坐标
  22.     /// </summary>
  23.     public int x;
  24.     /// <summary>
  25.     /// y坐标
  26.     /// </summary>
  27.     public int y;
  28.  
  29.     /// <summary>
  30.     /// 寻路消耗
  31.     /// </summary>
  32.     public float f;
  33.     /// <summary>
  34.     /// 距离起点距离
  35.     /// </summary>
  36.     public float g;
  37.     /// <summary>
  38.     /// 距离终点距离
  39.     /// </summary>
  40.     public float h;
  41.  
  42.     /// <summary>
  43.     /// 父结点
  44.     /// </summary>
  45.     public AStarNode father;
  46.  
  47.     /// <summary>
  48.     /// 结点类型
  49.     /// </summary>
  50.     public E_Node_Type type;
  51.  
  52.     public AStarNode(int xPos, int yPos, E_Node_Type t)
  53.     {
  54.         this.x = xPos;
  55.         this.y = yPos;
  56.         this.type = t;
  57.     }
  58.  
  59. }

结点管理类：

  1. using System.Collections;
  2. using System.Collections.Generic;
  3. using UnityEngine;
  4.  
  5. public class AStarManger : BaseManger<AStarManger>
  6. {
  7.     public int mapW;
  8.     public int mapH;
  9.  
  10.     private AStarNode startNode;
  11.     private AStarNode endNode;
  12.  
  13.     //private Vector2 endVec = Vector2.right * -1;
  14.  
  15.     public AStarNode[,] nodes;
  16.  
  17.     List<AStarNode> openList = new List<AStarNode>();
  18.     List<AStarNode> closeList = new List<AStarNode>();
  19.  
  20.     /// <summary>
  21.     /// 初始化
  22.     /// </summary>
  23.     public void InitAStarManger(int mapW, int mapH)
  24.     {
  25.         if(mapH < 0 || mapW < 0)
  26.         {
  27.             Debug.LogError("地图尺寸存在问题");
  28.             return;
  29.         }
  30.         this.mapW = mapW;
  31.         this.mapH = mapH;
  32.         
  33.         nodes = new AStarNode[mapW, mapH];
  34.  
  35.         for(int i = 0; i < this.mapW; i++)
  36.         {
  37.             for(int j = 0; j < this.mapH; j++)
  38.             {
  39.                 AStarNode an = new AStarNode(i, j, Random.Range(0, 100) < 20 ? E_Node_Type.Obstacles : E_Node_Type.Normal);
  40.                 nodes[i, j] = an;
  41.             }
  42.         }
  43.  
  44.     }
  45.  
  46.     /// <summary>
  47.     /// 开始寻径
  48.     /// </summary>
  49.     /// <returns></returns>
  50.     public List<AStarNode> FindPath(Vector2 startPos, Vector2 endPos)
  51.     {
  52.         if(startPos.x < 0 || startPos.y < 0 || endPos.x < 0 || endPos.y < 0 
  53.             || startPos.x >= this.mapW || startPos.y >= this.mapH 
  54.             || endPos.x >= this.mapW || endPos.y >= this.mapH)
  55.         {
  56.             Debug.LogError("坐标超出范围");
  57.             return null;
  58.         }
  59.  
  60.         startNode = nodes[(int)startPos.x, (int)startPos.y];
  61.         endNode = nodes[(int)endPos.x, (int)endPos.y];
  62.  
  63.         if(startNode.type is E_Node_Type.Obstacles || endNode.type is E_Node_Type.Obstacles)
  64.         {
  65.             Debug.LogError("起始结点或目标结点为障碍");
  66.             return null;
  67.         }
  68.  
  69.         startNode.father = null;
  70.         startNode.f = 0;
  71.         startNode.g = 0;
  72.         startNode.h = 0;
  73.  
  74.         openList.Clear();
  75.         closeList.Clear();
  76.  
  77.         closeList.Add(startNode);
  78.  
  79.         while(true)
  80.         {
  81.             //找附近点，并将符合条件的添加进openList
  82.             AddNearlyNode2OpenList(startNode.x - 1, startNode.y -1, 1.4f, startNode, endPos);
  83.             AddNearlyNode2OpenList(startNode.x, startNode.y - 1, 1f, startNode, endPos);
  84.             AddNearlyNode2OpenList(startNode.x + 1, startNode.y - 1, 1.4f, startNode, endPos);
  85.             AddNearlyNode2OpenList(startNode.x - 1, startNode.y, 1f, startNode, endPos);
  86.             AddNearlyNode2OpenList(startNode.x + 1, startNode.y, 1f, startNode, endPos);
  87.             AddNearlyNode2OpenList(startNode.x - 1, startNode.y + 1, 1.4f, startNode, endPos);
  88.             AddNearlyNode2OpenList(startNode.x, startNode.y + 1, 1f, startNode, endPos);
  89.             AddNearlyNode2OpenList(startNode.x + 1, startNode.y + 1, 1.4f, startNode, endPos);
  90.  
  91.             if(openList.Count == 0)
  92.             {
  93.                 Debug.LogWarning("终点不可达");
  94.                 return null;
  95.             }
  96.  
  97.             //排序
  98.             openList.Sort(SortRuler);
  99.             //选择新的父节点
  100.             startNode = openList[0];
  101.             //添加到closeList
  102.             closeList.Add(startNode);
  103.             openList.RemoveAt(0);
  104.             //判断是否到达终点
  105.             if(startNode == endNode)
  106.             {
  107.                 List<AStarNode> path = new List<AStarNode>();
  108.                 path.Add(endNode);
  109.                 while(endNode.father != null)
  110.                 {
  111.                     path.Add(endNode.father);
  112.                     endNode = endNode.father;
  113.                 }
  114.                 path.Reverse();
  115.                 return path;
  116.             }
  117.         }
  118.     }
  119.  
  120.     private int SortRuler(AStarNode a, AStarNode b)
  121.     {
  122.         if (a.f >= b.f) return 1;
  123.         else return -1;
  124.     }
  125.  
  126.     /// <summary>
  127.     /// 将父结点周围符合条件结点，添加进openList
  128.     /// </summary>
  129.     private void AddNearlyNode2OpenList(int x, int y, float g, AStarNode father, Vector2 endPos)
  130.     {
  131.         //判断传入坐标是否超范围
  132.         if(x < 0 || y < 0 || x >= this.mapW || y >= this.mapH)
  133.         {
  134.             return;
  135.         }
  136.  
  137.         AStarNode an = nodes[x, y];
  138.  
  139.         //如果该结点是障碍结点 或 ol,cl里有，忽略
  140.         //如果结点为null，或是上下左右都有障碍物，忽略
  141.         if(an.type is E_Node_Type.Obstacles
  142.             || an is null || closeList.Contains(an)
  143.             || nodes[x, father.y].type is E_Node_Type.Obstacles 
  144.             || nodes[father.x, y].type is E_Node_Type.Obstacles)
  145.         {
  146.             return;
  147.         }
  148.  
  149.         //单独判断是否在ol里，优化。如果结点已经在ol里，并且下一个最小f值的点也可以算到该点，那么该点的父节点不会变为这个最小值点，导致不是最短路径
  150.         if(openList.Contains(an))
  151.         {
  152.             float gThis = father.g + g;
  153.             if(gThis < an.g)
  154.             {
  155.                 an.g = gThis;
  156.                 an.f = an.g + an.h;
  157.                 an.father = father;
  158.             }
  159.             return;
  160.         }
  161.  
  162.         //父结点距离起点距离，加上自己距离父结点距离
  163.         an.g = father.g + g;
  164.         an.h = Mathf.Abs(endPos.x - x) + Mathf.Abs(endPos.y - y);
  165.         //计算曼哈顿距离
  166.         an.f = an.g + an.h;
  167.  
  168.         //将结点加入openList
  169.         openList.Add(an);
  170.  
  171.         //设置父结点
  172.         an.father = father;
  173.     }
  174. }
  175.

单例模板：

  1. using System.Collections;
  2. using System.Collections.Generic;
  3. using UnityEngine;
  4.  
  5. public class BaseManger<T> where T : new() 
  6. {
  7.     private static T instance;
  8.  
  9.     public static T Getinstance()
  10.     {
  11.         if(instance is null)
  12.         {
  13.             instance = new T();
  14.         }
  15.         return instance;
  16.     }
  17. }

Unity中界面构建

测试脚本：

  1. using System.Collections;
  2. using System.Collections.Generic;
  3. using UnityEngine;
  4. using UnityEngine.UIElements;
  5.  
  6. public class Test : MonoBehaviour
  7. {
  8.     public float BeginX;
  9.     public float BeginY;
  10.  
  11.     public float offsetX;
  12.     public float offsetY;
  13.  
  14.     public int mapW;
  15.     public int mapH;
  16.  
  17.     private Vector2 beginPos = Vector2.right * -1;
  18.     private Dictionary<string, GameObject> cubes = new Dictionary<string, GameObject>();
  19.     List<AStarNode> list = new List<AStarNode>();
  20.  
  21.     private GameObject tmpStart;
  22.     private GameObject tmpEnd;
  23.     // Start is called before the first frame update
  24.     void Start()
  25.     {
  26.         Init();
  27.     }
  28.  
  29.     // Update is called once per frame
  30.     void Update()
  31.     {
  32.         if(Input.GetMouseButtonDown(0))
  33.         {
  34.             Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
  35.             RaycastHit info;
  36.             if(Physics.Raycast(ray, out info, 1000))
  37.             {
  38.                 if(beginPos == Vector2.right * -1)
  39.                 {
  40.                     if (list != null)
  41.                     {                       
  42.                         for (int i = 0; i < list.Count; i++)
  43.                         {
  44.                             cubes[list[i].x + "_" + list[i].y].GetComponent<MeshRenderer>().material.color = Color.white;
  45.                         }
  46.                     }
  47.  
  48.                     string[] strs = info.collider.gameObject.name.Split('_');
  49.                     beginPos = new Vector2(int.Parse(strs[0]), int.Parse(strs[1]));
  50.  
  51.                     if (tmpEnd) tmpEnd.GetComponent<MeshRenderer>().material.color = Color.white;
  52.                     if (tmpStart) tmpStart.GetComponent<MeshRenderer>().material.color = Color.white;
  53.  
  54.                     tmpStart = info.collider.gameObject;
  55.                     tmpStart.GetComponent<MeshRenderer>().material.color = Color.yellow;
  56.                 }
  57.                 else
  58.                 {
  59.                     string[] strs = info.collider.gameObject.name.Split('_');
  60.                     Vector2 endPos = new Vector2(int.Parse(strs[0]), int.Parse(strs[1]));
  61.                    
  62.                     tmpEnd = info.collider.gameObject;
  63.                     tmpEnd.GetComponent<MeshRenderer>().material.color = Color.blue;
  64.                     list = AStarManger.Getinstance().FindPath(beginPos, endPos);
  65.                     if(list != null)
  66.                     {                       
  67.                         for (int i = 0; i < list.Count; i++)
  68.                         {
  69.                             cubes[list[i].x + "_" + list[i].y].GetComponent<MeshRenderer>().material.color = Color.green;
  70.                         }
  71.                     }
  72.  
  73.                     beginPos= Vector2.right * -1;
  74.                 }
  75.             }
  76.         }
  77.     }
  78.  
  79.     public void Init()
  80.     {
  81.         AStarManger.Getinstance().InitAStarManger(mapW, mapH);
  82.         tmpEnd = null; 
  83.         tmpStart = null;
  84.         list = null;
  85.  
  86.         if(cubes.Count != 0)
  87.         {            
  88.             foreach (var obj in cubes)
  89.             {
  90.                 Destroy(obj.Value.gameObject);
  91.             }
  92.             cubes.Clear();
  93.         }
  94.         for (int i = 0; i < mapW; i++)
  95.         {
  96.             for (int j = 0; j < mapH; j++)
  97.             {
  98.                 GameObject obj = GameObject.CreatePrimitive(PrimitiveType.Cube);
  99.                 obj.transform.position = new Vector3(BeginX + i * offsetX, BeginY + j * offsetY);
  100.                 obj.transform.name = i + "_" + j;
  101.                 
  102.                 cubes.Add(obj.name, obj);
  103.  
  104.                 AStarNode an = AStarManger.Getinstance().nodes[i, j];
  105.                 if (an.type == E_Node_Type.Obstacles)
  106.                 {
  107.                     MeshRenderer mr = obj.GetComponent<MeshRenderer>();
  108.                     mr.material.color = Color.red;
  109.                 }
  110.             }
  111.         }
  112.     }
  113. }

新建一个场景，将测试脚本挂载在任意物体上

新建一个画布，并添加一个按钮。其它ui元素可随意设定

将按钮关联Init方法

实现效果

正常终点可达：

终点不可达情况：

后续优化文章： 

 进一步优化

本文仅为学习阶段的一个总结，按需浏览。存在一定不足的情况

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/94853
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号