IndieGame/client/Assets/Scripts/System/AStar/AStar.cs


using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using static UnityEngine.UI.Image;

namespace Ether
{
    public class AStar
    {
        private AStarNode[,] gridNode;

        private int gridWidth;
        private int gridHeight;

        private Vector2Int origin;

        public AStar(int gridWidth, int gridHeight, List<Vector2Int> obstacleList, Vector2Int origin = default)
        {
            this.gridWidth = gridWidth;
            this.gridHeight = gridHeight;
            this.origin = origin;

            SetData(gridWidth, gridHeight);

            foreach (var obstaclePos in obstacleList)
            {
                AStarNode node = GetGridNode(obstaclePos.x - origin.x, obstaclePos.y - origin.x);
                node.isObstacle = true;
            }
        }

        private void SetData(int gridWidth, int gridHeight)
        {
            gridNode = new AStarNode[gridWidth, gridHeight];

            for (int x = 0; x < gridWidth; x++)
            {
                for (int y = 0; y < gridHeight; y++)
                {
                    gridNode[x, y] = new AStarNode(new Vector2Int(x, y));
                }
            }
        }

        public AStarNode GetGridNode(int xPos, int yPos)
        {
            if (xPos < gridWidth && yPos < gridHeight)
            {
                return gridNode[xPos, yPos];
            }
            Debug.Log("超出寻路网格范围");
            return null;
        }

        public void Reset(int gridWidth, int gridHeight, List<Vector2Int> obstacleList)
        {
            this.gridWidth = gridWidth;
            this.gridHeight = gridHeight;

            SetData(gridWidth, gridHeight);

            foreach (var obstaclePos in obstacleList)
            {
                AStarNode node = GetGridNode(obstaclePos.x, obstaclePos.y);
                node.isObstacle = true;
            }
        }

        private List<AStarNode> openNodeList = new List<AStarNode>();    //当前选中Node周围的8个点
        private HashSet<AStarNode> closedNodeList = new HashSet<AStarNode>();   //所有被选中的点

        private bool isPathFound;

        private AStarNode startNode;
        private AStarNode targetNode;

        public void BuildPath(Vector2Int startPos, Vector2Int endPos, Stack<Vector2Int> stepStack)
        {
            openNodeList.Clear();
            closedNodeList.Clear();
            isPathFound = false;

            startNode = GetGridNode(startPos.x - origin.x, startPos.y - origin.y);

            targetNode = GetGridNode(endPos.x - origin.x, endPos.y - origin.y);

            if (startNode == null || targetNode == null)
            {
                string str = (startNode == null && targetNode == null) ? startPos + "和" + endPos.x :
                    (startNode == null ? startPos.ToString() : endPos.ToString());
                Debug.LogError($"找不到对应的网格点:{str}");
                return;
            }

            //查找最短路径
            if (FindShortestPath() && stepStack != null)
            {
                AStarNode nextNode = targetNode;

                while (nextNode != null)
                {
                    stepStack.Push(nextNode.gridPosition + origin);
                    nextNode = nextNode.parentNode;
                }
            }
        }

        private bool FindShortestPath()
        {
            //添加起点
            openNodeList.Add(startNode);

            while (openNodeList.Count > 0)
            {
                //节点排序，Node内涵比较函数
                openNodeList.Sort();

                AStarNode closeNode = openNodeList[0];

                openNodeList.RemoveAt(0);
                closedNodeList.Add(closeNode);

                if (closeNode == targetNode)
                {
                    isPathFound = true;
                    break;
                }

                //计算周围8个Node补充到OpenList
                EvaluateNeighbourNodes(closeNode);
            }

            return isPathFound;
        }

        /// <summary>
        /// 评估周围8个点，并生成对应消耗值
        /// </summary>
        /// <param name="currentNode"></param>
        private void EvaluateNeighbourNodes(AStarNode currentNode)
        {
            Vector2Int currentNodePos = currentNode.gridPosition;
            AStarNode validNeighbourNode;

            for (int x = -1; x <= 1; x++)
            {
                for (int y = -1; y <= 1; y++)
                {
                    if (x == 0 && y == 0)
                        continue;

                    validNeighbourNode = GetValidNeighbourNode(currentNodePos.x + x, currentNodePos.y + y);

                    if (validNeighbourNode != null)
                    {
                        if (!openNodeList.Contains(validNeighbourNode))
                        {
                            validNeighbourNode.gCost = currentNode.gCost + GetDistance(currentNode, validNeighbourNode);
                            validNeighbourNode.hCost = GetDistance(validNeighbourNode, targetNode);
                            //链接父节点
                            validNeighbourNode.parentNode = currentNode;
                            openNodeList.Add(validNeighbourNode);
                        }
                    }
                }
            }
        }


        /// <summary>
        /// 找到有效的Node,非障碍，非已选择
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        private AStarNode GetValidNeighbourNode(int x, int y)
        {
            if (x >= gridWidth || y >= gridHeight || x < 0 || y < 0)
                return null;

            AStarNode neighbourNode = GetGridNode(x, y);

            if (neighbourNode.isObstacle || closedNodeList.Contains(neighbourNode))
                return null;
            else
                return neighbourNode;
        }


        /// <summary>
        /// 返回两点距离值
        /// </summary>
        /// <param name="nodeA"></param>
        /// <param name="nodeB"></param>
        /// <returns>14的倍数+10的倍数</returns>
        private int GetDistance(AStarNode nodeA, AStarNode nodeB)
        {
            int xDistance = Mathf.Abs(nodeA.gridPosition.x - nodeB.gridPosition.x);
            int yDistance = Mathf.Abs(nodeA.gridPosition.y - nodeB.gridPosition.y);

            if (xDistance > yDistance)
            {
                return 14 * yDistance + 10 * (xDistance - yDistance);
            }
            return 14 * xDistance + 10 * (yDistance - xDistance);
        }

    }
}