A*寻路算法学习笔记

Unity中实现A星寻路算法

【Unity】简单粗暴 10分钟理解A*寻路算法

理论知识

A*寻路用来计算点到点之间避开阻挡的最短路径

A*基本原理

找自己周围的点，选出一个新的点作为起点再循环的找

详细原理

1.寻路消耗公式：

f（寻路消耗） = g（离起点的距离） + h（离终点的距离）

2.开启列表：存储已经找到的点，记录每个点的父对象，并且每个点对应一个寻路消耗，将寻路消耗最小的第一个点移入关闭列表

3.关闭列表：存储可能的最短路径可能经过的点

4.格子对象的父对象：以A点为起点，找到B点，A点就是B点的父对象

每次从新的点找周围的点时，如果周围的点已经在开启列表或关闭列表中了，就不再考虑这个点

每次向关闭列表中存储点时，都要判断这个点是不是和终点一样

步骤

找到起点周围的点,记录点的父对象为起点,将点放入开启列表中

找到开启列表中f最小的点,将它添加到closelist中

判断该点是否为终点,如果是,则寻路结束,路径为该点以父对象为指针所构成的链表

以之前添加到closelist中的点作为新起点，重复步骤

如果最终开启列表为空,说明是死路,无法到达终点,

A*算法的优缺点

• 优点:
  1. 相比于深搜和广搜,访问的节点更少,更有效率
  2. 可以在不同的地图上运行
• 缺点
  1. 需要占用大量内存
  2. 当遇到动态地图,需要重复搜索
  3. 如果遇到大规模地图,需要搜索的时间可能过长
  4. 可能会陷入局部最优解

程序实现

AStarNode.cs

namespace AStar
{
    public class AStarNode
    {
        // 寻路消耗和李起点和终点的距离
        public float F, G, H;
        
        // 父对象
        public AStarNode Father;

        // 坐标
        public int X, Y;
        
        // 格子的类型
        public NodeType Type;

        public AStarNode(int x, int y, NodeType type)
        {
            X = x;
            Y = y;
            Type = type;
        }
    }
}

AStarManager.cs

using System;
using System.Collections.Generic;
using JKFrame;
using Unity.VisualScripting;
using UnityEngine;
using UnityEngine.PlayerLoop;
using Random = UnityEngine.Random;

namespace AStar
{
    public class AStarManager : SingletonMono<AStarManager>
    {
        private int _mapW;
        private int _mapH;

        private AStarNode[,] _nodes;

        private List<AStarNode> _openList;

        private List<AStarNode> _closeList;

        public void InitMapInfo(int w, int h)
        {
            _mapW = w;
            _mapH = h;
            
            _nodes = new AStarNode[w, h];
            // 这里随机阻挡格子
            for (int i = 0; i < w; i++)
            {
                for (int j = 0; j < h; j++)
                {
                    var node = new AStarNode(i, j, Random.Range(0, 100) < 20 ? NodeType.Stop : NodeType.Walk);
                    _nodes[i, j] = node;
                }
            }
        }

        public List<AStarNode> FindPath(Vector2 startPos, Vector3 endPos)
        {
            // 实际项目中传入的点往往是坐标系中的位置,这里简略看作格子的坐标

            // 首先要判断传入的两个点是否合法
            // 1.要在地图范围内
            // 2.要不是阻挡
            if (startPos.x < 0 || startPos.x >= _mapW ||
                startPos.y < 0 || startPos.y >= _mapH ||
                endPos.x < 0 || endPos.x >= _mapW ||
                endPos.y < 0 || endPos.y >= _mapH)
                return null;

            AStarNode start = _nodes[(int)startPos.x, (int)startPos.y];
            AStarNode end = _nodes[(int)endPos.x, (int)endPos.y];

            if (start.Type == NodeType.Stop|| end.Type == NodeType.Stop)
                return null;

            // 清空开启和关闭列表
            _closeList.Clear();
            _openList.Clear();
            
            // 清空start
            start.Father = null;
            start.F = 0;
            start.G = 0;
            start.H = 0;
            
            // 将起始点放入关闭列表中
            _closeList.Add(start);

            while (true)
            {
                //从起点开始,找周围的点,并放入开启列表中
                FindNearlyNodeToOpenList(start.X-1,start.Y-1,1.4f,start,end);
                FindNearlyNodeToOpenList(start.X-1,start.Y,1f,start,end);
                FindNearlyNodeToOpenList(start.X-1,start.Y+1,1.4f,start,end);
                FindNearlyNodeToOpenList(start.X+1,start.Y-1,1.4f,start,end);
                FindNearlyNodeToOpenList(start.X+1,start.Y,1f,start,end);
                FindNearlyNodeToOpenList(start.X+1,start.Y+1,1.4f,start,end);
                FindNearlyNodeToOpenList(start.X,start.Y+1,1f,start,end);
                FindNearlyNodeToOpenList(start.X,start.Y-1,1f,start,end);
            
                // 死路
                if (_openList.Count == 0)
                {
                    return null;
                }
                
                // 选出f最小的点
                _openList.Sort(SortOpenList);

                //选出开启列表中f最小的点,放入关闭列表中
                _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
            {
                return -1;
            }
        }

        private void FindNearlyNodeToOpenList(int x, int y,float g,AStarNode father,AStarNode end)
        {
            if (x < 0 || x >= _mapW || y < 0 || y >= _mapH) return;
            var node = _nodes[x, y];
            if (node == null || node.Type == NodeType.Stop|| _openList.Contains(node)|| _closeList.Contains(node)) return;

            node.Father = father;
            node.G = father.G + g;
            node.H = Mathf.Abs(end.X - node.X) + Mathf.Abs(end.Y - node.Y);

        }
    }
}