A星算法--Unity

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarManager : MonoBehaviour
{
    private void Awake()
    {
        for (int i = 0; i < 100; i++)
        {
            for (int j = 0; j < 100; j++)
            {
                var p = new Vector2(i, j);
                mapPathData.Add(p, new AStarNode(p));
            }
        }

        var start = new Vector2(Random.Range(0, 100), Random.Range(0, 100));
        var end = new Vector2(Random.Range(0, 100), Random.Range(0, 100));
        var list = FindPath(start, end);
        Debug.Log(start);
        Debug.Log(end);
        Debug.Log(list);
    }

    static public Dictionary<Vector2, AStarNode> mapPathData = new Dictionary<Vector2, AStarNode>();

    static public List<Vector2> FindPath(Vector2 startPos, Vector2 endPos)
    {
        if (!mapPathData.ContainsKey(startPos) || !mapPathData.ContainsKey(endPos)) return null;

        List<AStarNode> openPath = new List<AStarNode>();
        AStarNode startNode = mapPathData[startPos];
        AStarNode endNode = mapPathData[endPos];
        List<AStarNode> openNode = new List<AStarNode>();
        List<AStarNode> closeNode = new List<AStarNode>();
        openNode.Add(startNode);
        startNode.parent = null;
        while (openNode.Count > 0)
        {
            AStarNode currentNode = openNode[0];

            for (int i = 0; i < openNode.Count; i++)
            {
                if (openNode[i].fValue <= currentNode.fValue && openNode[i].hValue < currentNode.hValue)
                {
                    currentNode = openNode[i];
                }
            }
            openNode.Remove(currentNode);
            closeNode.Add(currentNode);
            if (currentNode == endNode)
            {
                List<Vector2> path = new List<Vector2>();
                while (currentNode.parent != null)
                {
                    path.Add(currentNode.mapGird);
                    currentNode = currentNode.parent;
                }
                path.Reverse();
                return path;
            }
            openPath.Add(currentNode);

            if (closeNode.Count > 1000)
            {
                Debug.Log("关闭列表过大   //临时解决 寻路造成的性能问题");
                return null;
            }

            List<AStarNode> OpenNodeList = GetOpenAroundNode(currentNode, closeNode, mapPathData);
            foreach (var node in OpenNodeList)
            {
                float newCode = currentNode.gValue + GetDistanceToPos(currentNode, node);
                if (!openNode.Contains(node) || node.gValue > newCode)
                {
                    node.gValue = newCode;
                    node.hValue = GetDistanceToPos(node, endNode);
                    node.parent = currentNode;
                    if (!openNode.Contains(node))
                    {
                        openNode.Add(node);
                    }
                }
            }
        }
        return null;
    }

    static public float GetDistanceToPos(AStarNode StartNode, AStarNode EndNode)
    {
        float d = Vector2.Distance(StartNode.mapGird, EndNode.mapGird);
        return d;
    }

    static private List<AStarNode> GetOpenAroundNode(AStarNode currentNode, List<AStarNode> closeNode, Dictionary<Vector2, AStarNode> pathData)
    {
        List<AStarNode> OpenNodeList = new List<AStarNode>();

        Vector2 pos1 = new Vector2(currentNode.mapGird.x - 1, currentNode.mapGird.y);
        Vector2 pos2 = new Vector2(currentNode.mapGird.x + 1, currentNode.mapGird.y);
        Vector2 pos3 = new Vector2(currentNode.mapGird.x, currentNode.mapGird.y - 1);
        Vector2 pos4 = new Vector2(currentNode.mapGird.x, currentNode.mapGird.y + 1);

        Vector2 pos5 = new Vector2(currentNode.mapGird.x - 1, currentNode.mapGird.y + 1);
        Vector2 pos6 = new Vector2(currentNode.mapGird.x - 1, currentNode.mapGird.y - 1);
        Vector2 pos7 = new Vector2(currentNode.mapGird.x + 1, currentNode.mapGird.y + 1);
        Vector2 pos8 = new Vector2(currentNode.mapGird.x + 1, currentNode.mapGird.y - 1);

        if (pathData.ContainsKey(pos1) && !closeNode.Contains(pathData[pos1]))
        {
            OpenNodeList.Add(pathData[pos1]);
        }

        if (pathData.ContainsKey(pos2) && !closeNode.Contains(pathData[pos2]))
        {
            OpenNodeList.Add(pathData[pos2]);
        }

        if (pathData.ContainsKey(pos3) && !closeNode.Contains(pathData[pos3]))
        {
            OpenNodeList.Add(pathData[pos3]);
        }

        if (pathData.ContainsKey(pos4) && !closeNode.Contains(pathData[pos4]))
        {
            OpenNodeList.Add(pathData[pos4]);
        }

        if (pathData.ContainsKey(pos5) && pathData.ContainsKey(pos1) && pathData.ContainsKey(pos4) && !closeNode.Contains(pathData[pos5]))
        {
            OpenNodeList.Add(pathData[pos5]);
        }

        if (pathData.ContainsKey(pos6) && pathData.ContainsKey(pos1) && pathData.ContainsKey(pos3) && !closeNode.Contains(pathData[pos6]))
        {
            OpenNodeList.Add(pathData[pos6]);
        }

        if (pathData.ContainsKey(pos7) && pathData.ContainsKey(pos2) && pathData.ContainsKey(pos4) && !closeNode.Contains(pathData[pos7]))
        {
            OpenNodeList.Add(pathData[pos7]);
        }

        if (pathData.ContainsKey(pos8) && pathData.ContainsKey(pos2) && pathData.ContainsKey(pos3) && !closeNode.Contains(pathData[pos8]))
        {
            OpenNodeList.Add(pathData[pos8]);
        }

        return OpenNodeList;
    }

}

public class AStarNode
{
    public Vector2 mapGird;
    public float gValue;
    public float hValue;

    public int i;
    public int index;

    public float fValue
    {
        get
        {
            return gValue + hValue;
        }
    }
    public AStarNode parent;

    public AStarNode(Vector2 grid)
    {
        mapGird = grid;
    }
}
上一篇:矩阵游戏[NOI2013]


下一篇:Unity屏幕坐标(Input.mousePosition)转换UI坐标