A*寻路来解决什么问题？

A*寻路来计算玩家行进最短路径

A*基本原理

不停的找周围的点，选出一个点作为起点（这个起点是消耗最小的，将周围的点的消耗排序，取最小的那个），再循环的找，直至找到终点

A*详细原理

1.寻路消耗公式
f（寻路消耗）=g（离起点距离 分为两种 上下左右为1 其他四个角为1.4 根号2）+ h（离终点距离 使用曼哈顿街区的思想）
2.开启列表（所有点的存放）
3.关闭列表（最优点的存放）
每次判断最优点是否为终点 如果是 停止寻路，否则继续寻路
4.格子对象的父对象（用来确定最终的路径）

需求分析

需要一个格子类 寻路管理器（管理所有的格子）
开启列表 关闭列表

格子类
成员变量：
寻路消耗 f g h
父亲格子father
坐标 x y
格子类型 type

方法：
构造函数

寻路管理器类
成员变量：
格子数组 nodes
开启列表 openlist
关闭列表 clostlist
地图的边界 mapx mapy

方法：
初始化地图格子方法
寻找路径方法（起点，终点）

源码

网格类

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


public enum E_node_type
{
    walk,//可以走
    stop//不能走
}

//A*格子类
public class AStarNode
{
    public float f;//寻路消耗
    public float g;//距离起点距离
    public float h;//距离终点距离

    public AStarNode father;//父对象

    //格子对象坐标
    public int x;
    public int y;

    public E_node_type type;

    public AStarNode(int x, int y, E_node_type type)
    {
        //传入坐标和类型
        this.x = x;
        this.y = y;
        this.type = type;
    }

}
//管理器
public class AStarManager:MonoBehaviour
{
    public static AStarManager Instance;

    public AStarNode[,] nodes;//地图相关对象容器
    private List<AStarNode> openList = new List<AStarNode>();//开启列表
    private List<AStarNode> closeList = new List<AStarNode>();//关闭列表

    private int mapx;
    private int mapy;
    //宽高

    private void Awake()
    {
        Instance = this;
    }
    public AStarNode[,] initmapinfo(int x, int y)
    {
        //初始化地图信息
        //根据宽高 创建格子
        this.mapx = x;
        this.mapy = y;

        nodes = new AStarNode[x, y];//声明容器装多少个格子
        for (int i = 0; i < x; i++)
        {
            for (int j = 0; j < y; j++)
            {
                AStarNode node = new AStarNode(i, j, UnityEngine.Random.Range(0, 100) < 20 ? E_node_type.stop : E_node_type.walk);
                //随机阻挡

                nodes[i, j] = node;
            }
        }
        return nodes;
    }


    //寻路方法
    public List<AStarNode> findpath(Vector2 startpos, Vector2 endpos)
    {
        //首先判断传入点是否合法 （不是阻挡点）
        //实际开发需要转换坐标
        if (startpos.x < 0 || startpos.x >= mapx || startpos.y < 0 || startpos.y > mapy ||
            endpos.x < 0 || endpos.x >= mapx || endpos.y < 0 || endpos.y > mapy)
        {
            Debug.LogError("由于在地图边界外");
            return null;//不合法
        }

        AStarNode start = nodes[(int)startpos.x, (int)startpos.y];
        AStarNode end = nodes[(int)endpos.x, (int)endpos.y];
        if (start.type == E_node_type.stop || end.type == E_node_type.stop)
        {
            Debug.LogError("该点是阻挡点");
            return null;//不合法
        }
        openList.Clear();
        closeList.Clear();//清空数据 防止影响

        //把开始点初始化之后放入关闭列表中
        start.father = null;
        start.f = 0;
        start.g = 0;
        start.h = 0;

        closeList.Add(start);

        while (true)
        {
            //寻找周围的所有点
            FindnearNodeToopenList(start.x - 1, start.y - 1, 1.4f, start, end);
            FindnearNodeToopenList(start.x - 1, start.y, 1, start, end);
            FindnearNodeToopenList(start.x - 1, start.y + 1, 1.4f, start, end);

            FindnearNodeToopenList(start.x, start.y - 1, 1f, start, end);
            FindnearNodeToopenList(start.x, start.y + 1, 1f, start, end);

            FindnearNodeToopenList(start.x + 1, start.y - 1, 1.4f, start, end);
            FindnearNodeToopenList(start.x + 1, start.y, 1f, start, end);
            FindnearNodeToopenList(start.x + 1, start.y - 1, 1.4f, start, end);

            if (openList.Count == 0)//开始列表为空 还没有找到终点
            {
                Debug.LogError("死路!");
                return null;
            }


            //开启列表放入上边的八个点
            openList.Sort(sortopenlist);//自定义排序

            //放入关闭列表
            closeList.Add(openList[0]);

            start = openList[0];//找到的这个点变成新的起点 进行新的计算
            openList.RemoveAt(0);//移除

            if (start == end)
            {
                //寻路结束
                List<AStarNode> path = new List<AStarNode>();
                path.Add(end);
                while (end.father != null)
                {
                    path.Add(end.father);
                    end = end.father;
                }
                //翻转一下
                path.Reverse();
                return path;//找到路径
            }
        }

    }
    private int sortopenlist(AStarNode a, AStarNode b)//自定义排序
    {
        if (a.f > b.f)
        {
            return 1;
        }
        else if((a.f < b.f))
        {
            return -1;
        }
        return 0;
    }

    //把邻近的点放入开启列表中去
    private void FindnearNodeToopenList(int x, int y, float g, AStarNode father, AStarNode end)
    {
        //边间检测
        if (x < 0 || x >= mapx || y < 0 || y >= mapy)
        {
            return;
        }

        AStarNode node = nodes[x, y];
        //判断是否是边界，阻挡
        if (node == null || node.type == E_node_type.stop || openList.Contains(node) || closeList.Contains(node))
        {
            return;
        }

        //计算f值 f=g+h=起点距离+终点距离
        node.father = father;//记录父对象
        node.g = father.g + g;//父亲离起点距离 + 我离父亲距离=我离起点的距离
        node.h = Mathf.Abs(end.x - node.x) + Mathf.Abs(end.y - node.y);//曼哈顿街区算法
        node.f = node.g + node.h;


        openList.Add(node);//存入开启了列表中

    }
}

表现层

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

public class AStarView : MonoBehaviour
{
    public GameObject item;

    public Button btn;

    private AStarItem[,] object_nodes;

    void Start()
    {
        InitMap(10, 10);

        btn.onClick.AddListener(delegate { startFind(); });
    }

    public void InitMap(int x,int y )
    {
        var nodes = AStarManager.Instance.initmapinfo(x, y);
        object_nodes = new AStarItem[x, y];

        int lenght = 60 * x - 10;
        int height = 60 * y - 10;
        gameObject.GetComponent<RectTransform>().sizeDelta = new Vector2(lenght, height);

       
        for(int i = 0; i <x; i++)
        {
            for (int j = 0; j < y; j++)
            {
                AStarItem AstarItem = Instantiate(item, transform).GetComponent<AStarItem>();
                AstarItem.initColor(nodes[i, j].type);

                object_nodes[i, j] = AstarItem;
            }
        }
    }

    public void startFind()
    {
        Vector2 start = new Vector2(0, 0);
        Vector2 end = new Vector2(9, 9);

        List<AStarNode> path = AStarManager.Instance.findpath(start, end);

        foreach(AStarNode node in path)
        {
            object_nodes[node.x, node.y].changeColor();
        }
    }

}

网格更新

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

public class AStarItem : MonoBehaviour
{
    public Image image;

    public void initColor(E_node_type type)
    {
        image.color = type == E_node_type.walk ? Color.white : Color.red;
    }

    public void changeColor()
    {
        image.color = Color.green;
    }
}

以上代码已测试通过，直接copy即可在untiy中执行
效果如下

2021.3.11更新

在上一场面试中 我和面试官聊到了很多A*算法相关的问题
其中有一个 面试官问 如果地图中有两种地形，一种是草地，一种是沙地
然后有一个角色优先考虑走沙地 问我怎么实现

我当时很快想到的就是 在A*算法中每个格子设置一个值 就作为草地和沙地的权重
优先选择权重较大的 比如设置草地为1 沙地为2 优先选择沙地

然后面试官还问了我一个问题：如何优化A*算法中角色移动的轨迹（使得路径尽量保持类似直线）
当时我没想到好的方法 只想到了将格子扩大 这样可以稍微优化
但是很明显这不是面试官想要的结果
然后面试结束之后 我回想起来 这个问题和上边那个是同理的，每次选择点的时候，给直线的方向和拐弯的方向加上不同的权重，使得方向会影响消耗，就可以实现尽量直线了