A*寻路算法

寻路效果.gif

代码实现

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

/// <summary>
/// 格子类型
/// </summary>
public enum ItemType
{
    Normal,
    Obsticle,
    Start,
    End
}

public class AStar : MonoBehaviour
{
    /// <summary>
    /// Item预设体
    /// </summary>
    public GameObject itemPrefab;
    //起点终点坐标
    public int startPointX = 1;
    public int startPointY = 2;
    public int endPointX = 10;
    public int endPointY = 12;
    //自定义偏移量
    public float offset = 0.5f;
    //障碍物出现的概率
    public int obsticleScale = 60;
    //地图格子的长宽
    private int mapX;
    private int mapY;
    //地图偏移量
    private float mapOffsetX;
    private float mapOffsetY;
    //格子数组
    private Item[,] items;
    /// <summary>
    /// 开启列表（将所有计算过FGH值的格子存储）
    /// </summary>
    private List<Item> openList;
    /// <summary>
    /// 关闭列表（将被作为中心计算过的格子）
    /// </summary>
    private List<Item> closeList;
    /// <summary>
    /// 结果路径
    /// </summary>
    private Stack<Item> path;

    void Awake()
    {
        openList = new List<Item>();
        closeList = new List<Item>();
        path = new Stack<Item>();
    }

    void Start()
    {
        MapReady();
        AStarPathFinding();
    }

    /// <summary>
    /// 地图准备
    /// </summary>
    void MapReady()
    {
        //计算地图长宽
        mapX = (int)(transform.localScale.x * 20);
        mapY = (int)(transform.localScale.z * 20);
        //实例数组
        items = new Item[mapX, mapY];
        //计算地图偏移量
        mapOffsetX = -transform.localScale.x * 10 / 2;
        mapOffsetY = -transform.localScale.z * 10 / 2;
        //生成格子
        for (int i = 0; i < mapX; i++)
        {
            for (int j = 0; j < mapY; j++)
            {
                //获取当前格子
                GameObject crtItem = Instantiate(itemPrefab,
                    new Vector3(i / 2f, 0, j / 2f) +
                    new Vector3(mapOffsetX + offset, 0,
                        mapOffsetY + offset),
                    Quaternion.identity);
                //填充数组
                items[i, j] = crtItem.GetComponent<Item>();
                //设置坐标
                items[i, j].SetItemXY(i, j);
                //随机
                int r = Random.Range(1, 101);
                if (r <= obsticleScale)
                {
                    //设置障碍物
                    items[i, j].SetItemType(ItemType.Obsticle);
                }
            }
        }
        //设置起点终点
        items[startPointX, startPointY].SetItemType(ItemType.Start);
        items[endPointX, endPointY].SetItemType(ItemType.End);
    }

    /// <summary>
    /// A*寻路
    /// </summary>
    void AStarPathFinding()
    {
        //起点格子作为当前格子
        Item currentItem = null;
        //添加起点格子到开启列表
        openList.Add(items[startPointX, startPointY]);
        //循环遍历
        while (openList.Count > 0)
        {
            //获取F值最小的格子作为当前格子
            currentItem = openList[0];
            //如果发现了终点
            if (currentItem.GetItemType()
               == ItemType.End)
            {
                //TODO:整理结果路径
                GeneratePath(currentItem);
                return;
            }
            //发现周围的格子
            for (int i = -1; i <= 1; i++)
            {
                for (int j = -1; j <= 1; j++)
                {
                    //越过当前格子
                    if (i == 0 && j == 0)
                        continue;
                    //被发现的格子坐标
                    int p = currentItem.GetItemX() + i;
                    int q = currentItem.GetItemY() + j;
                    if (p < 0 || q < 0 || p >= mapX
                       || q >= mapY ||
                       items[p, q].GetItemType() == ItemType.Obsticle ||
                        closeList.Contains(items[p, q]))
                    {
                        continue;
                    }
                    //计算FGH
                    int g = currentItem.g + (int)(Mathf.Sqrt(i * i + j * j) * 10);
                    //如果该格子的g未被计算，或值太大，覆盖它
                    if (items[p, q].g == 0 || items[p, q].g > g)
                    {
                        items[p, q].g = g;
                        //设置发现者
                        items[p, q].parent = currentItem;
                    }
                    //曼哈顿计算h值
                    items[p, q].h = (Mathf.Abs(p - endPointX)
                        + Mathf.Abs(q - endPointY)) * 10;
                    //计算F
                    items[p, q].f = items[p, q].g + items[p, q].h;
                    //添加到开启列表
                    openList.Add(items[p, q]);
                }
            }
            //For循环结束
            //移除当前格子从开启列表
            openList.Remove(currentItem);
            //放置到关闭列表
            closeList.Add(currentItem);
            //判断
            if (openList.Count == 0)
                Debug.Log("无法到达目标点！");
            //排序
            openList.Sort();
        }
    }

    /// <summary>
    /// 生成路径
    /// </summary>
    void GeneratePath(Item item)
    {
        if (item.parent != null)
        {
            //压栈
            path.Push(item.parent);
            //递归寻址
            GeneratePath(item.parent);
        }
        else
        {
            //输出结果
            StartCoroutine(ShowPath());
        }
    }

    /// <summary>
    /// 展示结果
    /// </summary>
    /// <param name="item">Item.</param>
    IEnumerator ShowPath()
    {
        while (path.Count > 0)
        {
            //出栈
            Item item = path.Pop();
            if (item.GetItemType() != ItemType.Start)
            {
                //标记
                item.SetColor(Color.black);
            }
            yield return new WaitForSeconds(0.2f);
        }
    }

    void Update()
    {
        if (Input.GetKeyDown(KeyCode.Space))
        {
            UnityEngine.SceneManagement.SceneManager.LoadScene(0);
        }
    }
}

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

public class Item : MonoBehaviour, System.IComparable
{

    //格子类型
    private ItemType itemType;
    //格子坐标
    private int x;
    private int y;
    //寻路估量代价值
    public int f;
    public int g;
    public int h;
    //当前格子的发现者
    public Item parent;

    private MeshRenderer meshRenderer;

    void Awake()
    {
        meshRenderer = GetComponent<MeshRenderer>();
    }
    /// <summary>
    /// 设置格子类型
    /// </summary>
    /// <param name="t">T.</param>
    public void SetItemType(ItemType t)
    {
        //设置
        itemType = t;
        switch (t)
        {
            case ItemType.Start:
                meshRenderer.material.color = Color.red;
                break;
            case ItemType.End:
                meshRenderer.material.color = Color.green;
                break;
            case ItemType.Obsticle:
                meshRenderer.material.color = Color.blue;
                break;
            default:
                meshRenderer.material.color = Color.white;
                break;
        }
    }

    /// <summary>
    /// 获取格子类型
    /// </summary>
    /// <returns>The item type.</returns>
    public ItemType GetItemType()
    {
        return itemType;
    }

    public int GetItemX()
    {
        return x;
    }

    public int GetItemY()
    {
        return y;
    }

    /// <summary>
    /// 设置坐标
    /// </summary>
    /// <param name="x">The x coordinate.</param>
    /// <param name="y">The y coordinate.</param>
    public void SetItemXY(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    /// <summary>
    /// 上色
    /// </summary>
    /// <param name="col">Col.</param>
    public void SetColor(Color col)
    {
        meshRenderer.material.color = col;
    }

    /// <summary>
    /// 排序规则
    /// </summary>
    /// <returns>The to.</returns>
    /// <param name="obj">Object.</param>
    public int CompareTo(object obj)
    {
        //新的Item
        Item newItem = obj as Item;
        if (newItem.f > this.f)
        {
            return -1;
        }
        else if (newItem.f < this.f)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}