using UnityEngine;

using System.Collections.Generic;

public class Map

{

    /// <summary>

    /// 初始化地图

    /// </summary>

    /// <returns></returns>

    public static Dictionary<string, MapInfo> GetMap()

    {

        Dictionary<string, MapInfo> temp = new Dictionary<string, MapInfo>();

        for (int i = ; i < ; i++)

        {

            string s = "";

            for (int j = ; j < ; j++)

            {

                int tt = ;

                if (i >  && i <  && j == )

                {

                    tt = ;

                }

                MapInfo mi = new MapInfo(i, j, tt);

                temp.Add(i + "-" + j, mi);

                s += mi.tag + " ";

            }

            Debug.Log(s);

        }

        return temp;

    }

}

/// <summary>

/// 地图节点

/// </summary>

public class MapInfo

{

    /// <summary>

    /// X

    /// </summary>

    public int x;

    /// <summary>

    /// Y

    /// </summary>

    public int y;

    /// <summary>

    /// 是否可行走

    /// </summary>

    public int tag;

    /// <summary>

    /// G

    /// </summary>

    public int gValue;

    /// <summary>

    /// H

    /// </summary>

    public int hValue;

    /// <summary>

    /// 父节点

    /// </summary>

    public MapInfo parent;

    public MapInfo()

    { }

    /// <summary>

    /// 构造

    /// </summary>

    /// <param name="x"></param>

    /// <param name="y"></param>

    /// <param name="tag"></param>

    public MapInfo(int x, int y,int tag)

    {

        this.x = x;

        this.y = y;

        this.tag = tag;

        this.gValue = ;

        this.hValue = ;

        this.parent = null;

    }

}

using UnityEngine;

using System.Collections.Generic;

public class AStar : MonoBehaviour

{

    /// <summary>

    /// 地图

    /// </summary>

    Dictionary<string, MapInfo> map;

    /// <summary>

    /// open列表

    /// </summary>

    Dictionary<string, MapInfo> openList = new Dictionary<string, MapInfo>();

    /// <summary>

    /// close列表

    /// </summary>

    Dictionary<string, MapInfo> closeList = new Dictionary<string, MapInfo>();

    /// <summary>

    /// 当前点

    /// </summary>

    MapInfo currentV;

    /// <summary>

    /// 当前点的相邻节点列表

    /// </summary>

    Dictionary<string, MapInfo> adjancentMap;

    // Use this for initialization

    void Start ()

    {

        map = Map.GetMap();

        MapInfo st = map["5-2"];//start

        MapInfo end = map["6-8"];//end

        FindPath(st, end);

    }

    /// <summary>

    /// 寻路

    /// </summary>

    /// <param name="start">起点</param>

    /// <param name="end">终点</param>

    public void FindPath(MapInfo start,MapInfo end)

    {

        openList.Add(start.x + "-" + start.y, start);

        do

        {

            currentV = GetTheLowestFrom(openList);

            closeList.Add(currentV.x + "-" + currentV.y, currentV);

            openList.Remove(currentV.x + "-" + currentV.y);

            if (closeList.ContainsKey(end.x + "-" + end.y))

            {

                Debug.Log("FindPath");

                PrintThePath(end);

                break;

            }

            adjancentMap = AdjacentList(currentV);

            foreach (string k in adjancentMap.Keys)

            {

                if (closeList.ContainsKey(k))

                {

                    continue;

                }

                if (!openList.ContainsKey(k))

                {

                    adjancentMap[k].parent = currentV;

                    adjancentMap[k].gValue = currentV.gValue + ;

                    adjancentMap[k].hValue = GetManhattanDistance(adjancentMap[k], end);

                    openList.Add(k, adjancentMap[k]);

                }

                else

                {

                    int g = currentV.gValue + ;

                    if (g < adjancentMap[k].gValue)

                    {

                        adjancentMap[k].gValue = g;

                        adjancentMap[k].parent = currentV;

                    }

                }

            }

        } while (openList.Count > );

    }

    /// <summary>

    /// 获取openlist中F最小的节点

    /// </summary>

    /// <param name="open"></param>

    /// <returns></returns>

    public MapInfo GetTheLowestFrom(Dictionary<string, MapInfo> open)

    {

        MapInfo result=null;

        int min = ;

        foreach (MapInfo m in open.Values)

        {

            if (m.gValue + m.hValue < min)

            {

                result = m;

                min = m.gValue + m.hValue;

            }

        }

        return result;

    }

    /// <summary>

    /// 获取当前节点的相邻节点

    /// </summary>

    /// <param name="m">当前节点</param>

    /// <returns></returns>

    public Dictionary<string, MapInfo> AdjacentList(MapInfo m)

    {

        Dictionary<string, MapInfo> resultDic=new Dictionary<string,MapInfo>();

        string left = (m.x - ) + "-" + m.y;

        string right = (m.x + ) + "-" + m.y;

        string top = m.x + "-" + (m.y - );

        string bot = m.x + "-" + (m.y + );

        if (map.ContainsKey(left))

        {

            if(map[left].tag==)

                resultDic.Add(left, map[left]);

        }

        if (map.ContainsKey(right))

        {

            if (map[right].tag == )

                resultDic.Add(right, map[right]);

        }

        if (map.ContainsKey(top))

        {

            if (map[top].tag == )

                resultDic.Add(top, map[top]);

        }

        if (map.ContainsKey(bot))

        {

            if (map[bot].tag == )

                resultDic.Add(bot, map[bot]);

        }

        return resultDic;

    }

    /// <summary>

    /// 获得两个点的曼哈顿距离

    /// 作为估值函数

    /// </summary>

    /// <param name="st"></param>

    /// <param name="end"></param>

    /// <returns></returns>

    public int GetManhattanDistance(MapInfo st, MapInfo end)

    {

        int result = ;

        result = Mathf.Abs(st.x - end.x) + Mathf.Abs(st.y - end.y);

        return result;

    }

    /// <summary>

    /// 输出路径

    /// </summary>

    /// <param name="end">终点</param>

    public void PrintThePath(MapInfo end)

    {

        string s = "";

        MapInfo m = end;

        while (m.parent != null)

        {

            s += "("+m.parent.x + "," + m.parent.y + ")->";

            m = m.parent;

        }

        Debug.Log(s);

    }

}