unity A星尋路

算法 fCost = gCost + hCost
gCost 是當前節點到移動起始點的消耗，hCost是當前節點到終點的消耗
網格為變成為1的矩形，左右相鄰的兩個網格直接的gCost為1，斜對角相鄰的兩個網格的gCost為1.4
hCost 當前網格到終點網格的水平距離 + 垂直距離
比如當前網格位置是（2，3），終點位置（10，8），則hCost = (10-2) + (8-3)
原始的算法是 fCost = gCost + hCost，均勻計算周圍網格
對于一些比較復雜的散裝障礙物場景，我們可以適當調整gCost和hCost的權重，比如 fCost = gCost x 4 + hCost x 6，這個修改會讓尋路的時候，在消耗相同的網格點上，優先在距離終點位置更近的網格周圍尋路。當我們從（1，1）向（3，10）位置尋路的時候，我們在店（3，1）和點（1，10）兩個位置的 gCost + hCost 是相等的，但是點（1，10）其實距離終點更近一些，用調整過權重的算法，（1，10）我們得出來的的值會小一些，就可以優先從（1，10）位置尋找可移動路徑

代碼如下
尋路節點

using System.Collections;
using System.Collections.Generic;
using UnityEngine;public class AstarNode
{public int gridX;public int gridY;public Vector3 position;public float hCost;public float gCost;public float fCost {get{return gCost + hCost;}}/// <summary>/// 優先處理距離終點近的node/// </summary>public float fCostNew {get{return gCost*4 + hCost*6;}}public bool walkable;public AstarNode parent;public AstarNode(){}public AstarNode(int x, int y, Vector3 pos, bool canWalk){gridX = x;gridY = y;position = pos;walkable = canWalk;}}

地圖網格生成

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using UnityEngine;
using Random = System.Random;
public enum SearchType
{NeighborFour,NeighborEight,
}
public class MapGridsManager : MonoBehaviour
{public int width = 100;public int height = 100;public float cellSize = 1f;public Mesh mesh;private Vector3 originPoint;private AstarNode[,] grids;public AStartManager manager;public AstartMoveTest moveTarget;public bool isUseCache = false;public bool isUseNewCost = false;public SearchType searchType = SearchType.NeighborFour;[Header("障礙物生成范圍") ]public Rect obstacleRect;void Awake(){originPoint = Vector3.zero;mesh = Resources.GetBuiltinResource<Mesh>("Quad.fbx");}private void Start(){grids = new AstarNode[width, height];Dictionary<int, AstarNode> nodeDic = GetCacheData();for (int i = 0; i < width; i++){for (int j = 0; j < height; j++){int keyId = i * 100000 + j;AstarNode node;if (isUseCache && nodeDic.ContainsKey(keyId)){node = nodeDic[keyId];}else{bool isObstacal = UnityEngine.Random.Range(1, 100) > 50;isObstacal = i >= obstacleRect.xMin && i < obstacleRect.xMax && j >= obstacleRect.yMin && j < obstacleRect.yMax  && isObstacal;bool warkAble = !isObstacal;node = new AstarNode(i, j, originPoint + new Vector3(i * cellSize, 0, j * cellSize), warkAble);    }grids[i, j] = node;}}serilizeNode();}void serilizeNode(){StringBuilder sb = new StringBuilder();for (int i = 0; i < width; i++){for (int j = 0; j < height; j++){var node = grids[i, j];int warkState = node.walkable ?1:0;if (i>0 || j > 0){sb.Append("|");}var data = $"{node.gridX}_{node.gridY}_{warkState}_{node.position.x}_{node.position.y}_{node.position.z}";sb.Append(data) ;}}string res = sb.ToString();UnityEngine.PlayerPrefs.SetString("grid_data", res);}Dictionary<int, AstarNode> GetCacheData(){Dictionary<int, AstarNode> nodeDic = new Dictionary<int, AstarNode>(width * height);string data = UnityEngine.PlayerPrefs.GetString("grid_data", "");string[] arr = data.Split("|");for (int i = 0; i < arr.Length; i++){string itemStr = arr[i];string[] itemArr = itemStr.Split("_");if (itemArr.Length < 6){continue;}AstarNode node = new AstarNode();node.gridX = int.Parse(itemArr[0]);node.gridY = int.Parse(itemArr[1]);node.walkable = int.Parse(itemArr[2]) == 1 ? true : false;float positionX = float.Parse(itemArr[3]);float positionY = float.Parse(itemArr[4]);float positionZ = float.Parse(itemArr[5]);node.position = new Vector3(positionX, positionY, positionZ);int keyId = node.gridX * 100000 + node.gridY;nodeDic.Add(keyId, node);}return nodeDic;}public AstarNode GetNode(int x, int y){if (x < 0 || x >= width || y < 0 || y >= height){return null;}return grids[x, y];}public List<AstarNode> GetNeighborNodes(AstarNode node){if (searchType == SearchType.NeighborFour)return GetNeighborFourNodes(node);else{return GetNeighborEightNodes(node);}}public List<AstarNode> GetNeighborFourNodes(AstarNode node){List<AstarNode> nodeList = new List<AstarNode>();int nodeX = node.gridX;int nodeY = node.gridY;for (int i = -1; i <= 1; i++){for (int j = -1; j <= 1; j++){if (i == 0 && j == 0){continue;}if (i == 0 || j == 0){int itemX = nodeX + i;int itemY = nodeY + j;AstarNode itemNode = GetNode(itemX, itemY);if (itemNode != null){nodeList.Add(itemNode);}}}}return nodeList;}public List<AstarNode> GetNeighborEightNodes(AstarNode node){List<AstarNode> nodeList = new List<AstarNode>();int nodeX = node.gridX;int nodeY = node.gridY;for (int i = -1; i <= 1; i++){for (int j = -1; j <= 1; j++){if (i == 0 && j == 0){continue;}int itemX = nodeX + i;int itemY = nodeY + j;AstarNode itemNode = GetNode(itemX, itemY);if (itemNode != null){nodeList.Add(itemNode);}}}return nodeList;}public AstarNode GetByWorldPositionNode(Vector3 pos){int x = Mathf.FloorToInt(pos.x / cellSize);int y = Mathf.FloorToInt(pos.y / cellSize);if (x < 0 || y < 0 || x>=width || y >= height){return null;}return grids[x, y];}void OnDrawGizmos(){Gizmos.color = Color.gray;if (grids != null){for (int i = 0; i < width; i++){for (int j = 0; j < height; j++){AstarNode node = grids[i, j];if (manager != null){if (manager.rodeList.Contains(node)){Gizmos.color = Color.white;}else if(manager.openList.Contains(node)){Gizmos.color = Color.black;}else if (manager.closeList.Contains(node)){Gizmos.color = Color.green;}else{Gizmos.color = node.walkable?  Color.blue: Color.red;}if (manager.moveEndNode != null && manager.moveEndNode == node){Gizmos.color = Color.yellow;}if (manager.moveStartNode != null && manager.moveStartNode == node){Gizmos.color = Color.gray;}}else{Gizmos.color = node.walkable?  Color.blue: Color.red;}// Gizmos.DrawCube(node.position, Vector3.one);var rotation = Quaternion.Euler(new Vector3(90, 0, 0));Gizmos.DrawMesh(mesh, node.position, rotation, Vector3.one);}}}Gizmos.color = Color.black;var halfCellSize = cellSize / 2;for (int i = 0; i <= width; i++){Gizmos.DrawLine(new Vector3(i-halfCellSize,0,0), new Vector3(i-halfCellSize, 0 ,height-halfCellSize));}for (int i = 0; i <= height; i++){Gizmos.DrawLine(new Vector3(0,0,i-halfCellSize), new Vector3(width-halfCellSize, 0 ,i-halfCellSize));}}public void ResetNodeCost(){for (int i = 0; i < width; i++){for (int j = 0; j < height; j++){var node = grids[i, j];node.gCost = 0;node.hCost = 0;}}}public void BeginMove(List<AstarNode> rodeNodeList){moveTarget.BeginMove(rodeNodeList);}
}

尋路

using System;
using System.Collections;
using System.Collections.Generic;
using Unity.VisualScripting;
using UnityEngine;[Serializable]
public class ObstacleRange
{public int x;
}
public class AStartManager : MonoBehaviour
{public MapGridsManager map;public Vector3 from;public Vector3 end;public List<AstarNode> openList = new List<AstarNode>();public List<AstarNode> closeList = new List<AstarNode>();public List<AstarNode> rodeList = new List<AstarNode>();public AstarNode moveStartNode;public AstarNode moveEndNode;private bool isInFindPath = false;//是否正在訓練中void Update(){if (Input.GetKeyUp(KeyCode.A)){StartCoroutine(FindPath(from, end));}else if(Input.GetMouseButtonDown(0)){Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);RaycastHit hit;if (Physics.Raycast(ray, out hit)){var pos = new Vector3(hit.point.x, hit.point.z, 0);Debug.Log($"{pos}--{Input.mousePosition}");var node = map.GetByWorldPositionNode(pos);if (node != null){ from = end;end =  pos;StartCoroutine(FindPath(from, end));}}}}void DoMove(){map.BeginMove(rodeList);}IEnumerator FindPath(Vector3 startPos, Vector3 endPos){if (isInFindPath){yield break;}isInFindPath = true;ResetNodeData();AstarNode startNode = map.GetByWorldPositionNode(startPos);startNode.gCost = 0;startNode.hCost = 0;startNode.parent = null;AstarNode endNode = map.GetByWorldPositionNode(endPos);endNode.gCost = 0;endNode.hCost = 0;endNode.parent = null;openList.Add(startNode);moveStartNode = startNode;moveEndNode = endNode;if (!endNode.walkable){Debug.LogError("終點不可抵達");isInFindPath = false;yield break;}int index = 0;while (openList.Count > 0){var targetNode = openList[0];Debug.Log($"{index}: ({targetNode.gridX} ,{targetNode.gridY})");openList.Remove(targetNode);if (targetNode.gridX == endNode.gridX && targetNode.gridY == endNode.gridY){GenerateRote(targetNode);openList.Clear();break;}AddOpenList(targetNode, endNode);if (map.isUseNewCost){openList.Sort((a, b)=>{return a.fCostNew.CompareTo(b.fCostNew);});}else{openList.Sort((a, b)=>{return a.fCost.CompareTo(b.fCost);});}yield return new WaitForSeconds(0.1f);index++;if (index > 5000){Debug.LogError("循環超出上限");break;}}Debug.Log("尋路循環次數為：" + index);DoMove();isInFindPath = false;}void ResetNodeData(){openList.Clear();closeList.Clear();rodeList.Clear();map.ResetNodeCost();}private bool AddOpenList(AstarNode targetNode, AstarNode endNode){var neighborNodes = map.GetNeighborNodes(targetNode);closeList.Add(targetNode);foreach (var item in neighborNodes){if (item.walkable == false || closeList.Contains(item) || openList.Contains(item)){continue;}float tempGCost = targetNode.gCost + GetDestance(targetNode, item);if (item.gCost <= 0 || tempGCost < item.gCost){item.parent = targetNode;item.gCost = targetNode.gCost + GetDestance(targetNode, item);item.hCost = Mathf.Abs(endNode.gridX - item.gridX) + Mathf.Abs(endNode.gridY - item.gridY);openList.Add(item);}}return false;}List<AstarNode> GenerateRote(AstarNode curNode){rodeList = new List<AstarNode>();rodeList.Add(curNode);while (curNode.parent != null){curNode = curNode.parent;rodeList.Add(curNode);}rodeList.Reverse();return rodeList;}float GetDestance(AstarNode node1, AstarNode node2){float distance  ;if (node1.gridX != node2.gridX && node1.gridY != node2.gridY){distance = 1.4f;}else{distance = 1f;}return distance; }
}

控制對象在路徑點移動

using System.Collections.Generic;
using UnityEngine;public class AstartMoveTest : MonoBehaviour
{public Transform moveTarget;//移動對象private List<AstarNode> rodeNodeList;//行走路徑點private int moveIndex;//當前移動到第幾個點private bool isMoveing = false;//是否正在移動過程中private float miniDistance = 0.1f;private Vector3 endPosition;private Vector3 moveDir;public float speed = 1;// Start is called before the first frame updatevoid Start(){}public void BeginMove(List<AstarNode> rodeNodeList){if (rodeNodeList == null || rodeNodeList.Count < 2){Debug.LogError("路徑點異常，無法開始移動");return;}this.rodeNodeList = rodeNodeList;transform.position = rodeNodeList[0].position;isMoveing = true;moveIndex = 1;endPosition = rodeNodeList[moveIndex].position;moveDir = rodeNodeList[moveIndex].position - rodeNodeList[0].position;moveDir = moveDir.normalized;}// Update is called once per framevoid Update(){if (!isMoveing){return;}float distance = Vector3.Distance(transform.position, endPosition);// Debug.Log("distance = " + distance);if (distance < miniDistance){moveIndex++;if (moveIndex >= rodeNodeList.Count){isMoveing = false;Debug.Log("移動結束");return;}endPosition = rodeNodeList[moveIndex].position;transform.LookAt(endPosition);moveDir = endPosition - transform.position;moveDir = moveDir.normalized;}// transform.position = Vector3.Lerp(transform.position, endPosition, speed*Time.deltaTime);transform.position = transform.position + moveDir * Time.deltaTime * speed;}
}

在這里插入圖片描述