{"id":1212,"date":"2016-08-18T10:56:15","date_gmt":"2016-08-18T02:56:15","guid":{"rendered":"http:\/\/39.100.100.179\/?p=1212"},"modified":"2017-08-18T11:00:42","modified_gmt":"2017-08-18T03:00:42","slug":"a%e5%af%bb%e8%b7%af%e7%ae%97%e6%b3%95%e5%9c%a8unity%e4%b8%ad%e7%9a%84%e7%ae%80%e5%8d%95%e5%ba%94%e7%94%a8","status":"publish","type":"post","link":"http:\/\/www.u3d8.com\/?p=1212","title":{"rendered":"A*\u5bfb\u8def\u7b97\u6cd5\u5728Unity\u4e2d\u7684\u7b80\u5355\u5e94\u7528"},"content":{"rendered":"
\n

\u524d\u8a00<\/h3>\n

\u5728\u4f7f\u7528Unity\u5f00\u53d1\u6e38\u620f\u9879\u76ee\u65f6\uff0c\u7ecf\u5e38\u4f1a\u9047\u5230\u4e00\u4e9b\u89d2\u8272\u7684\u5bfc\u822a\u9700\u6c42\uff0c\u7136\u800cUnity\u63d0\u4f9b\u7ed9\u6211\u4eec\u7684NavMesh+NavMeshAgent\u5e76\u4e0d\u80fd\u5f88\u597d\u5e2e\u6211\u4eec\u5b9e\u73b0\uff0c\u4e14\u5bfb\u8def\u7f51\u683c\u7684\u70d8\u7119\uff0c\u4ee5\u53ca\u5728\u5bfc\u822a\u8fc7\u7a0b\u4e2d\u5bfb\u8def\u7f51\u683c\u7684\u68c0\u6d4b\uff0c\u90fd\u662f\u975e\u5e38\u6d88\u8017\u6027\u80fd\u7684\uff0c\u56e0\u6b64\u5728\u5f88\u591a\u4f01\u4e1a\u9879\u76ee\u4e2d\uff0c\u4f1a\u81ea\u5df1\u5199\u4e00\u4e0b\u9ad8\u6548\u7684\u5bfb\u8def\u7b97\u6cd5\u6765\u5b8c\u6210\u9700\u6c42\uff0c\u5176\u4e2d\u6709\u4e00\u79cd\u5c31\u662fA*\u5bfb\u8def\u7b97\u6cd5\u3002A*\u5bfb\u8def\u7b97\u6cd5\u662f\u4e00\u79cd\u542f\u53d1\u5f0f\u7b97\u6cd5\uff0c\u4ece\u6240\u6709\u53ef\u4ee5\u884c\u8d70\u7684\u8def\u5f84\u4e2d\u627e\u51fa\u4f30\u91cf\u4ee3\u4ef7\u6700\u5c0f\u7684\uff0c\u9012\u5f52\u6bcf\u6b65\u8fd9\u6837\u7684\u64cd\u4f5c\uff0c\u6700\u7ec8\u5230\u8fbe\u76ee\u6807\u70b9\u3002<\/p><\/blockquote>\n

    \n
  • A*\u5bfb\u8def\u7b97\u6cd5\u7684\u4f30\u91cf\u4ee3\u4ef7<\/strong>
    \n\u5728A*\u7b97\u6cd5\u4e2d\u6838\u5fc3\u7684\u5bfb\u8def\u4f9d\u636e\u5c31\u662f\u4f30\u91cf\u4ee3\u4ef7\uff0c\u5728A*\u4e2d\u901a\u5e38\u7528 F<\/strong> \u8868\u793a\u3002<\/p>\n

    F = G + H<\/strong>
    \n\u5176\u4e2dG<\/strong>\u8868\u793a\u5f53\u524d\u70b9\u5230\u8d77\u59cb\u70b9\u7684\u4f30\u91cf\u4ee3\u4ef7\uff0cH<\/strong>\u8868\u793a\u5f53\u524d\u70b9\u5230\u7ec8\u70b9\u7684\u4ee3\u4ef7\u3002<\/p><\/blockquote>\n<\/li>\n<\/ul>\n

    \"A*\u5bfb\u8def\u7b97\u6cd5\u5728Unity\u4e2d\u7684\u7b80\u5355\u5e94\u7528<\/p>\n
    FGH\u793a\u610f\u56fe<\/div>\n<\/div>\n
                    \u56fe\u4e2d\u683c\u5b50\u5de6\u4e0b\u89d2\u4e3aG\u503c\uff0c\u53f3\u4e0b\u89d2\u4e3aH\u503c\uff0c\u5de6\u4e0a\u89d2\u4e3aF\u503c<\/code><\/pre>\n
    \u56e0\u6b64\u4ece\u5f53\u524d\u683c\u5b50\u5468\u8fb9\u7684\u516b\u4e2a\u683c\u5b50\u4e2d\u627e\u5230\u4e0b\u4e00\u6b65\u6240\u8d70\u7684\u683c\u5b50\uff0c\u4f9d\u636eF\u503c\uff0c\u5f53F\u503c\u76f8\u540c\u65f6\u968f\u673a\u9009\u62e9\u3002<\/em><\/p>\n
    \u5f53\u7136\u5728\u5bfb\u8def\u8fc7\u7a0b\u4e2d\uff0c\u4f1a\u6709\u969c\u788d\uff0c\u4e0d\u80fd\u901a\u8fc7\uff0c\u901a\u8fc7\u53ef\u4ee5\u884c\u8d70\u7684\u683c\u5b50\u8d70\u5230\u7ec8\u70b9\u3002\u4e0b\u56fe\u4e2d\u7eff\u8272\u4e3a\u8d77\u70b9\uff0c\u7ea2\u8272\u4e3a\u7ec8\u70b9\uff0c\u84dd\u8272\u662f\u969c\u788d\uff0c\u6d45\u84dd\u8fb9\u6846\u662f\u53c2\u4e0e\u8ba1\u7b97\u7684\u683c\u5b50\uff0cA*\u5c31\u662f\u901a\u8fc7\u8fd9\u6837\u7684\u4e00\u7cfb\u5217\u8ba1\u7b97\u5b8c\u6210\u7684\u6700\u4f18\u5bfb\u8def\u3002<\/strong><\/p>\n
    \"A*\u5bfb\u8def\u7b97\u6cd5\u5728Unity\u4e2d\u7684\u7b80\u5355\u5e94\u7528<\/p>\n
    A*\u884c\u8d70\u8def\u7ebf<\/div>\n<\/div>\n
    \u4e0b\u9762\u6211\u5199\u4e86\u4e00\u4e2a\u5c0f\u4f8b\u5b50\uff0c\u65b9\u4fbf\u5927\u5bb6\u5b66\u4e60\u3002<\/h5>\n
      \n
    • \u7b80\u5355\u6548\u679c\n
      \"A*\u5bfb\u8def\u7b97\u6cd5\u5728Unity\u4e2d\u7684\u7b80\u5355\u5e94\u7528<\/p>\n
      \u7b80\u5355\u6548\u679c<\/div>\n<\/div>\n<\/li>\n
    • \u9996\u5148\u9700\u8981\u521b\u5efa\u4e00\u4e2a\u683c\u5b50\u7c7bGrid<\/li>\n<\/ul>\n<\/div>\n
      using UnityEngine;\r\nusing System.Collections;\r\nusing System.Collections.Generic;\r\nusing System;\r\n\r\n\/\/\/ <summary>\r\n\/\/\/ \u683c\u5b50\u7c7b\u578b\r\n\/\/\/ <\/summary>\r\npublic enum GridType\r\n{\r\n    \/\/\u6b63\u5e38\u7c7b\u578b\r\n    Normal,\r\n    \/\/\u969c\u788d\u7269\u7c7b\u578b\r\n    Obstacle,\r\n    \/\/\u8d77\u70b9\u7c7b\u578b\r\n    Start,\r\n    \/\/\u7ec8\u70b9\u7c7b\u578b\r\n    End\r\n}\r\n\r\n\/\/\/ <summary>\r\n\/\/\/ \u683c\u5b50\u7c7b\uff08\u5b9e\u73b0IComparable\u65b9\u4fbf\u6392\u5e8f\uff09\r\n\/\/\/ <\/summary>\r\npublic class Grid : IComparable\r\n{\r\n    \/\/\u683c\u5b50\u5750\u6807x-y\r\n    public int x;\r\n    public int y;\r\n    \/\/\u683c\u5b50A*\u4e09\u5c5e\u6027f-g-h\r\n    public int f;\r\n    public int g;\r\n    public int h;\r\n    \/\/\u683c\u5b50\u7c7b\u578b\r\n    public GridType type;\r\n    \/\/\u683c\u5b50\u7684\u5f52\u5c5e\uff08\u7236\u683c\u5b50\uff09\r\n    public Grid parent;\r\n    \/\/\u6784\u9020\u8d4b\u503c\r\n    public Grid (int x, int y)\r\n    {\r\n        this.x = x;\r\n        this.y = y;\r\n    }\r\n\r\n    \/\/\/ <summary>\r\n    \/\/\/ \u5b9e\u73b0\u6392\u5e8f\u63a5\u53e3\u65b9\u6cd5\r\n    \/\/\/ <\/summary>\r\n    \/\/\/ <returns>The to.<\/returns>\r\n    \/\/\/ <param name=\"obj\">Object.<\/param>\r\n    public int CompareTo (object obj)\r\n    {\r\n        Grid grid = (Grid)obj;\r\n        if (this.f < grid.f) {\r\n            \/\/\u5347\u5e8f\r\n            return -1;\r\n        }\r\n        if (this.f > grid.f) {\r\n            \/\/\u964d\u5e8f\r\n            return 1;\r\n        }\r\n        return 0;\r\n    }\r\n}<\/pre>\n
        \n
      • \u7136\u540e\u4e3b\u903b\u8f91AStar\u7c7b<\/li>\n<\/ul>\n
        using UnityEngine;\r\nusing System.Collections;\r\nusing System.Collections.Generic;\r\n\r\npublic class MyAStar : MonoBehaviour\r\n{\r\n    \/\/\/ <summary>\r\n    \/\/\/ \u5355\u4f8b\u811a\u672c\r\n    \/\/\/ <\/summary>\r\n    public static MyAStar instance;\r\n\r\n    \/\/\u53c2\u8003\u7269\u4f53\u9884\u8bbe\u4f53\r\n    public GameObject reference;\r\n    \/\/\u683c\u5b50\u6570\u7ec4\r\n    public Grid[,] grids;\r\n    \/\/\u683c\u5b50\u6570\u7ec4\u5bf9\u5e94\u7684\u53c2\u8003\u7269\uff08\u65b9\u5757\uff09\u5bf9\u8c61\r\n    public GameObject[,] objs;\r\n    \/\/\u5f00\u542f\u5217\u8868\r\n    public ArrayList openList;\r\n    \/\/\u5173\u95ed\u5217\u8868\r\n    public ArrayList closeList;\r\n    \/\/\u76ee\u6807\u70b9\u5750\u6807\r\n    public int targetX;\r\n    public int targetY;\r\n    \/\/\u8d77\u59cb\u70b9\u5750\u6807\r\n    public int startX;\r\n    public int startY;\r\n\r\n    \/\/\u683c\u5b50\u884c\u5217\u6570\r\n    private int row;\r\n    private int colomn;\r\n    \/\/\u7ed3\u679c\u6808\r\n    private Stack<string> parentList;\r\n    \/\/\u57fa\u7840\u7269\u4f53\r\n    private Transform plane;\r\n    private Transform start;\r\n    private Transform end;\r\n    private Transform obstacle;\r\n    \/\/\u6d41\u989c\u8272\u53c2\u6570\r\n    private float alpha = 0;\r\n    private float incrementPer = 0;\r\n\r\n    void Awake ()\r\n    {\r\n        instance = this;\r\n        plane = GameObject.Find (\"Plane\").transform;\r\n        start = GameObject.Find (\"Start\").transform;\r\n        end = GameObject.Find (\"End\").transform;\r\n        obstacle = GameObject.Find (\"Obstacle\").transform;\r\n        parentList = new Stack<string> ();\r\n        openList = new ArrayList ();\r\n        closeList = new ArrayList ();\r\n    }\r\n\r\n    \/\/\/ <summary>\r\n    \/\/\/ \u521d\u59cb\u5316\u64cd\u4f5c\r\n    \/\/\/ <\/summary>\r\n    void Init ()\r\n    {\r\n        \/\/\u8ba1\u7b97\u884c\u5217\u6570\r\n        int x = (int)(plane.localScale.x * 20);\r\n        int y = (int)(plane.localScale.z * 20);\r\n        row = x;\r\n        colomn = y;\r\n        grids = new Grid[x, y];\r\n        objs = new GameObject[x, y];\r\n        \/\/\u8d77\u59cb\u5750\u6807\r\n        Vector3 startPos = \r\n            new Vector3 (plane.localScale.x * -5, 0, plane.localScale.z * -5);\r\n        \/\/\u751f\u6210\u53c2\u8003\u7269\u4f53\uff08Cube\uff09\r\n        for (int i = 0; i < x; i++) {\r\n            for (int j = 0; j < y; j++) {\r\n                grids [i, j] = new Grid (i, j);\r\n                GameObject item = (GameObject)Instantiate (reference, \r\n                                      new Vector3 (i * 0.5f, 0, j * 0.5f) + startPos, \r\n                                      Quaternion.identity);\r\n                item.transform.GetChild (0).GetComponent<Reference> ().x = i;\r\n                item.transform.GetChild (0).GetComponent<Reference> ().y = j;\r\n                objs [i, j] = item;\r\n            }\r\n        }\r\n    }\r\n\r\n    \/\/\/ <summary>\r\n    \/\/\/ A*\u8ba1\u7b97\r\n    \/\/\/ <\/summary>\r\n    IEnumerator Count ()\r\n    {\r\n        \/\/\u7b49\u5f85\u524d\u9762\u64cd\u4f5c\u5b8c\u6210\r\n        yield return new WaitForSeconds (0.1f);\r\n        \/\/\u6dfb\u52a0\u8d77\u59cb\u70b9\r\n        openList.Add (grids [startX, startY]);\r\n        \/\/\u58f0\u660e\u5f53\u524d\u683c\u5b50\u53d8\u91cf\uff0c\u5e76\u8d4b\u521d\u503c\r\n        Grid currentGrid = openList [0] as Grid;\r\n        \/\/\u5faa\u73af\u904d\u5386\u8def\u5f84\u6700\u5c0fF\u7684\u70b9\r\n        while (openList.Count > 0 && currentGrid.type != GridType.End) {\r\n            \/\/\u83b7\u53d6\u6b64\u65f6\u6700\u5c0fF\u70b9\r\n            currentGrid = openList [0] as Grid;\r\n            \/\/\u5982\u679c\u5f53\u524d\u70b9\u5c31\u662f\u76ee\u6807\r\n            if (currentGrid.type == GridType.End) {\r\n                Debug.Log (\"Find\");\r\n                \/\/\u751f\u6210\u7ed3\u679c\r\n                GenerateResult (currentGrid);\r\n            }\r\n            \/\/\u4e0a\u4e0b\u5de6\u53f3\uff0c\u5de6\u4e0a\u5de6\u4e0b\uff0c\u53f3\u4e0a\u53f3\u4e0b\uff0c\u904d\u5386\r\n            for (int i = -1; i <= 1; i++) {\r\n                for (int j = -1; j <= 1; j++) {\r\n                    if (i != 0 || j != 0) {\r\n                        \/\/\u8ba1\u7b97\u5750\u6807\r\n                        int x = currentGrid.x + i;\r\n                        int y = currentGrid.y + j;\r\n                        \/\/\u5982\u679c\u672a\u8d85\u51fa\u6240\u6709\u683c\u5b50\u8303\u56f4\uff0c\u4e0d\u662f\u969c\u788d\u7269\uff0c\u4e0d\u662f\u91cd\u590d\u70b9\r\n                        if (x >= 0 && y >= 0 && x < row && y < colomn\r\n                            && grids [x, y].type != GridType.Obstacle\r\n                            && !closeList.Contains (grids [x, y])) {\r\n                            \/\/\u8ba1\u7b97G\u503c\r\n                            int g = currentGrid.g + (int)(Mathf.Sqrt ((Mathf.Abs (i) + Mathf.Abs (j))) * 10);\r\n                            \/\/\u4e0e\u539fG\u503c\u5bf9\u7167\r\n                            if (grids [x, y].g == 0 || grids [x, y].g > g) {\r\n                                \/\/\u66f4\u65b0G\u503c\r\n                                grids [x, y].g = g;\r\n                                \/\/\u66f4\u65b0\u7236\u683c\u5b50\r\n                                grids [x, y].parent = currentGrid;\r\n                            }\r\n                            \/\/\u8ba1\u7b97H\u503c\r\n                            grids [x, y].h = Manhattan (x, y);\r\n                            \/\/\u8ba1\u7b97F\u503c\r\n                            grids [x, y].f = grids [x, y].g + grids [x, y].h;\r\n                            \/\/\u5982\u679c\u672a\u6dfb\u52a0\u5230\u5f00\u542f\u5217\u8868\r\n                            if (!openList.Contains (grids [x, y])) {\r\n                                \/\/\u6dfb\u52a0\r\n                                openList.Add (grids [x, y]);\r\n                            }\r\n                            \/\/\u91cd\u65b0\u6392\u5e8f\r\n                            openList.Sort ();\r\n                        }\r\n                    }\r\n                }\r\n            }\r\n            \/\/\u5b8c\u6210\u904d\u5386\u6dfb\u52a0\u8be5\u70b9\u5230\u5173\u95ed\u5217\u8868\r\n            closeList.Add (currentGrid);\r\n            \/\/\u4ece\u5f00\u542f\u5217\u8868\u4e2d\u79fb\u9664\r\n            openList.Remove (currentGrid);\r\n            \/\/\u5982\u679c\u5f00\u542f\u5217\u8868\u7a7a\uff0c\u672a\u80fd\u627e\u5230\u8def\u5f84\r\n            if (openList.Count == 0) {\r\n                Debug.Log (\"Can not Find\");\r\n            }\r\n        }\r\n\r\n\r\n    }\r\n\r\n    \/\/\/ <summary>\r\n    \/\/\/ \u751f\u6210\u7ed3\u679c\r\n    \/\/\/ <\/summary>\r\n    \/\/\/ <param name=\"currentGrid\">Current grid.<\/param>\r\n    void GenerateResult (Grid currentGrid)\r\n    {\r\n        \/\/\u5982\u679c\u5f53\u524d\u683c\u5b50\u6709\u7236\u683c\u5b50\r\n        if (currentGrid.parent != null) {\r\n            \/\/\u6dfb\u52a0\u5230\u7236\u5bf9\u8c61\u6808\uff08\u5373\u7ed3\u679c\u6808\uff09\r\n            parentList.Push (currentGrid.x + \"|\" + currentGrid.y);\r\n            \/\/\u9012\u5f52\u83b7\u53d6\r\n            GenerateResult (currentGrid.parent);\r\n        }\r\n    }\r\n\r\n    \/\/\/ <summary>\r\n    \/\/\/ \u663e\u793a\u7ed3\u679c\r\n    \/\/\/ <\/summary>\r\n    \/\/\/ <returns>The result.<\/returns>\r\n    IEnumerator ShowResult ()\r\n    {\r\n        \/\/\u7b49\u5f85\u524d\u9762\u8ba1\u7b97\u5b8c\u6210\r\n        yield return new WaitForSeconds (0.3f);\r\n        \/\/\u8ba1\u7b97\u6bcf\u5e27\u989c\u8272\u503c\u589e\u91cf\r\n        incrementPer = 1 \/ (float)parentList.Count;\r\n        \/\/\u5c55\u793a\u7ed3\u679c\r\n        while (parentList.Count != 0) {\r\n            \/\/\u51fa\u6808\r\n            string str = parentList.Pop ();\r\n            \/\/\u7b490.3\u79d2\r\n            yield return new WaitForSeconds (0.3f);\r\n            \/\/\u62c6\u5206\u83b7\u53d6\u5750\u6807\r\n            string[] xy = str.Split (new char[]{ '|' });\r\n            int x = int.Parse (xy [0]);\r\n            int y = int.Parse (xy [1]);\r\n            \/\/\u5f53\u524d\u989c\u8272\u503c\r\n            alpha += incrementPer;\r\n            \/\/\u4ee5\u989c\u8272\u65b9\u5f0f\u7ed8\u5236\u8def\u5f84\r\n            objs [x, y].transform.GetChild (0).GetComponent<MeshRenderer> ().material.color\r\n            = new Color (1 - alpha, alpha, 0, 1);\r\n        }\r\n    }\r\n\r\n    \/\/\/ <summary>\r\n    \/\/\/ \u66fc\u54c8\u987f\u65b9\u5f0f\u8ba1\u7b97H\u503c\r\n    \/\/\/ <\/summary>\r\n    \/\/\/ <param name=\"x\">The x coordinate.<\/param>\r\n    \/\/\/ <param name=\"y\">The y coordinate.<\/param>\r\n    int Manhattan (int x, int y)\r\n    {\r\n        return (int)(Mathf.Abs (targetX - x) + Mathf.Abs (targetY - y)) * 10;\r\n    }\r\n\r\n    void Start ()\r\n    {\r\n        Init ();\r\n        StartCoroutine (Count ());\r\n        StartCoroutine (ShowResult ());\r\n    }\r\n}<\/pre>\n