a*原理 unity3d

2017-01-18 23:13:18 lil_black 阅读数 1096
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

最近赶时间,字以后再码吧 ^_^

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

namespace Astar
{
    public class PathFinder : MonoBehaviour
    {
        List<Node> Open = new List<Node>();
        List<Node> Close = new List<Node>();
        List<Node> All = new List<Node>();

        Node start;
        Node end;

        public static bool LOG { get { return false; } }
        public static float F { get { return 5; } }

        void Start()
        {
            Init();
        }

        //初始化
        void Init()
        {
            Open.Clear();
            Close.Clear();
            for (int x = 0; x < Map.width; x++)
            {
                for (int z = 0; z < Map.deep; z++)
                {
                    All.Add(new Node(x, z));
                }
            }
        }


        void Reset()
        {
            Open.Clear();
            Close.Clear();
            foreach (var node in All)
            {
                node.Reset();
                Open.Add(node);
            }
        }

        public List<IntVector2> Find(IntVector2 from, IntVector2 to)
        {
            Reset();
            if (LOG) Debug.Log("find start.");
            start = GetNode(from);
            start.cost = 0;
            start.f = 0;
            end = GetNode(to);
            int count = 0;
            while (Open.Count != 0)
            {
                var N = GetMinFNode();
                if (LOG) Debug.Log("find step " + count + ":" + N.pos + " , f=" + N.f);
                var dirs = new IntVector2[4] { new IntVector2(0, 1), new IntVector2(0, -1), new IntVector2(1, 0), new IntVector2(-1, 0) };
                foreach (var dir in dirs)
                {
                    bool inclose;
                    var X = GetNode(N.pos + dir, out inclose);
                    //在地图外
                    if (X == null)
                    {
                        continue;
                    }
                    else if (X == end)
                    {
                        X.last = N;
                        List<IntVector2> res = new List<IntVector2>();
                        var cur = end;
                        while (cur.last != null)
                        {
                            res.Add(cur.pos);
                            cur = cur.last;
                        }
                        res.Reverse();
                        return res;
                    }
                    //在Open内
                    //Debug.LogError("运行到这里了");
                    else if (!inclose)
                    {
                        UpdateFValue(N, X);
                        continue;
                    }
                    //在Close内
                    else if (inclose)
                    {
                        bool reOpen = UpdateFValue(N, X);
                        if (reOpen)
                        {
                            Open.Add(X);
                            Close.Remove(X);
                        }
                        continue;
                    }
                }
                Debug.DrawLine((Vector3)N.pos, (Vector3)N.pos + Vector3.up, Color.red, 1);
                Close.Add(N);
                Open.Remove(N);
            }
            return null;
        }


        /// <summary>
        /// 对X的值进行更新。
        /// </summary>
        /// <param name="N">当前正在Close的点</param>
        /// <param name="X">刷新值的点</param>
        /// <returns>返回是否需要重新OPEN</returns>
        bool UpdateFValue(Node N, Node X)
        {
            if (X.cost > N.cost + 1) X.cost = N.cost + 1;
            if (X.left < 0) X.left = Node.distance(end, X);
            var newF = X.cost + X.left * F;
            if (newF < X.f)
            {
                X.f = newF;
                X.last = N;
                return true;
            }
            else return false;
        }


        Node GetNode(IntVector2 v, out bool inClose)
        {
            if (!Map.IsInMap(v))
            {
                inClose = false;
                return null;
            }
            if (!Map.Walkable(v.x, v.z))
            {
                inClose = false;
                return null;
            }
            for (int i = 0; i < Open.Count; i++)
            {
                if (Open[i].pos == v)
                {
                    inClose = false;
                    return Open[i];
                }
            }
            for (int i = 0; i < Close.Count; i++)
            {
                if (Close[i].pos == v)
                {
                    inClose = true;
                    return Close[i];
                }
            }
            Debug.Log("意料之外的情况");
            inClose = false;
            return null;
        }

        Node GetNode(IntVector2 v)
        {
            bool useless;
            return GetNode(v, out useless);
        }

        Node GetMinFNode()
        {
            if (Open.Count == 0) return null;
            Node result = Open[0];
            foreach (var node in Open)
            {
                if (node.f < result.f)
                {
                    result = node;
                }
            }
            return result;
        }

        void Update()
        {
            if (Input.GetKeyDown(KeyCode.F))
            {
                IntVector2 a = (IntVector2)GameObject.Find("a").transform.position;
                IntVector2 b = (IntVector2)GameObject.Find("b").transform.position;
                var path = Find(a, b);
                for (int i = 1; i < path.Count; i++)
                {
                    Debug.DrawLine((Vector3)path[i - 1], (Vector3)path[i], Color.yellow, 3f);
                }
                path = PathFixer.Fix(path, 0.3f);
                for (int i = 1; i < path.Count; i++)
                {
                    Debug.DrawLine((Vector3)path[i - 1] + Vector3.up * 0.2f, (Vector3)path[i] + Vector3.up * 0.2f, Color.red, 3f);
                }
            }
        }
    }
}

2018-10-19 17:54:56 codingriver 阅读数 4174
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

最近发现A*算法忘的一干二净啊,记忆是个好东西,可惜吾没有啊,只能整理一篇文章以备日后翻看
这里只谈A*算法的实现,不谈A算法的优化*
这里的工程是unity版本的,当然理解A*算法是通用的

这里先放上A*算法的unity工程(unity2017.3.1) unity工程(github)

0X01 A*算法基本概念

启发式搜索: 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
IDA*算法: 这种算法被称为迭代加深A算法,可以有效的解决A空间增长带来的问题,甚至可以不用到优先级队列。如果要知道详细:google一下。
搜索区域(The Search Area): 图中的搜索区域被划分为了简单的二维数组,数组每个元素对应一个小方格,当然我们也可以将区域等分成是五角星,矩形等,通常将一个单位的中心点称之为搜索区域节点(Node)。  
开放列表(Open List): 我们将路径规划过程中待检测的节点存放于Open List中,而已检测过的格子则存放于Close List中。
关闭列表(Close List): 我们将路径规划过程中已经检查过的节点放在Close List。
启发函数(Heuristics Function)(估价函数): H为启发函数,也被认为是一种试探,由于在找到唯一路径前,我们不确定在前面会出现什么障碍物,因此用了一种计算H的算法,具体根据实际场景决定。在我们简化的模型中,H采用的是传统的曼哈顿距离(Manhattan Distance)估价函数,也就是横纵向走的距离之和。
F(n) = G + H。F代表当前检查点的总花费,G代表起点到当前检查点的花费,H代表当前检查点到终点的预估花费。
父节点(parent): 在路径规划中用于回溯的节点。
A*算法的特点: A*算法在理论上是时间最优的,但是也有缺点:它的空间增长是指数级别的。

0X02 A*算法寻路过程

  1. 将起点A添加到open列表中(A没有计算花费F是因为当前open列表只有这一个节点)。
  2. 检查open列表,选取花费F最小的节点M(检查M如果为终点是则结束寻路,如果open列表没有则寻路失败,直接结束)。
  3. 对于与M相邻的每一节点N:(下面本来没有序号的,csdn markdown的bug)
    • 如果N是阻挡障碍,那么不管它。
    • 如果N在closed列表中,那么不管它。
    • 如果N不在open列表中:添加它然后计算出它的花费F(n)=G+H。
    • 如果N已在open列表中:当我们使用当前生成的路径时,检查F花费是否更小。如果是,更新它的花费F和它的父节点。
  4. 重复2,3步。

0X03 A*算法寻路详细描述

寻路关键代码:

    /// <summary>
    /// 使用A*算法寻路
    /// </summary>
    /// <param name="start"></param>
    /// <param name="end"></param>
    void FindPath(Vector2 start,Vector2 end)
    {
        //和A*算法无关,只是为了显示使用
        int showFindNum=1;

        //开启列表
        List<Cell> openLs = new List<Cell>();
        //关闭列表
        List<Cell> closeLs = new List<Cell>();

        //起点
        Cell startCell = grid.GetCell(start);
        //终点
        Cell endCell = grid.GetCell(end);
        Debug.LogFormat("寻路开始,start({0}),end({1})!",start,end);

        //将起点作为待处理的点放入开启列表,
        openLs.Add(startCell);

        //如果开启列表没有待处理点表示寻路失败,此路不通
        while(openLs.Count>0)
        {
            //遍历开启列表,找到消费最小的点作为检查点
            Cell cur = openLs[0];
            for (int i = 0; i < openLs.Count; i++)
            {
                if(openLs[i].fCost<cur.fCost&&openLs[i].hCost<cur.hCost)
                {
                    cur = openLs[i];
                }
            }
            Debug.Log("当前检查点:" + cur.ToString()+" 编号:"+showFindNum+"  open列表节点数量:"+openLs.Count);
            //显示在界面,和A*算法无关
            cur.obj.transform.Find("Num").GetComponent<Text>().text=showFindNum.ToString();
            showFindNum++;

            //从开启列表中删除检查点,把它加入到一个“关闭列表”,列表中保存所有不需要再次检查的方格。
            openLs.Remove(cur);
            closeLs.Add(cur);

            //检查是否找到终点
            if(cur==endCell)
            {
                Debug.Log("寻路结束!");
                grid.CreatePath(cur);
                return;
            }

            //根据检查点来找到周围可行走的点
            //1.如果是墙或者在关闭列表中则跳过
            //2.如果点不在开启列表中则添加
            //3.如果点在开启列表中且当前的总花费比之前的总花费小,则更新该点信息
            List<Cell> aroundCells = GetAllAroundCells(cur);
            foreach (var cell in aroundCells)
            {
                
                if (cell.isWall || closeLs.Contains(cell))
                    continue;

                int cost= cur.gCost+ GetDistanceCost(cell, cur);

                if(cost<cell.gCost||!openLs.Contains(cell))
                {
                    cell.gCost = cost;
                    cell.hCost = GetDistanceCost(cell,endCell);
                    cell.parent = cur;
                    Debug.Log("cell:" + cell.ToString() + "  parent:" + cur.ToString() + "  " + cell.PrintCost());
                    if(!openLs.Contains(cell))
                    {
                        openLs.Add(cell);
                    }

                    //显示在界面,和A*算法无关
                    cell.obj.transform.Find("Cost").GetComponent<Text>().text = cell.fCost.ToString();
                }


            }

        }

        Debug.Log("寻路失败!");
    }

根据上面的工程得到这个图:
在这里插入图片描述
圆点说明:黑色是障碍物体,红色是起点,绿色是终点,浅紫色是寻路路径
红色数字:总花费F
蓝色数字:寻路的过程描述

过程描述:

  • 将起点(3,6)放到open列表中。

  • 选择open列表中花费最小的点M(3,6),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算(3,6)相邻的点,一共8个点,并且分别计算花费F(红色数字),都添加到open中
    +在这里插入图片描述

  • 选择open列表中花费最小的点M(4,6),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算(4,6)相邻的点,一共8个点,右侧是障碍物,其它5个点都在open中,分别计算当前路径花费和原来对比,都大,所以没有更新花费和父节点

  • 选择open列表中花费最小的点M(4,5),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算M相邻的点,在下面有三个新节点添加open中,其它五个点要么是障碍要么是已经在open中且花费比原来大,
    在这里插入图片描述

  • 选择open列表中花费最小的点M(4,7),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算M相邻的点,在上面有三个新节点添加open中,其它五个点要么是障碍要么是已经在open中且花费比原来大,
    在这里插入图片描述

  • 选择open列表中花费最小的点M(3,5),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算M相邻的点,在左下有一个新节点添加open中,在正下面有一个点(3,4)的花费比原来小,更新该节点信息,其它的点已经在open中且花费比原来大,
    在这里插入图片描述

  • 选择open列表中花费最小的点M(3,7),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算M相邻的点,在左下有一个新节点添加open中,在正下面有一个点(3,8)的花费比原来小,更新该节点信息,其它的点已经在open中且花费比原来大,
    在这里插入图片描述

  • 选择open列表中花费最小的点M(5,4),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算M相邻的点,有五个新节点添加open中,其它三个点要么是障碍要么是已经在open中且花费比原来大,
    在这里插入图片描述

  • 选择open列表中花费最小的点M(5,8),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算M相邻的点,有五个新节点添加open中,其它三个点要么是障碍要么是已经在open中且花费比原来大,
    在这里插入图片描述

  • 选择open列表中花费最小的点M(6,5),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算M相邻的点,有四个新节点添加open中,其它四个点要么是障碍要么是已经在open中且花费比原来大或者相等,
    在这里插入图片描述

  • 选择open列表中花费最小的点M(6,7),将M从open中移除,添加到closed列表中,后面检查时不再检查该点。

  • 计算M相邻的点,有两个新节点添加open中,其它六个点要么是障碍要么是已经在open中且花费比原来大或者相等,
    在这里插入图片描述

  • 选择open列表中花费最小的点M(7,6),将M从open中移除,添加到closed列表中,和终点对比相等,寻路结束。
    在这里插入图片描述

根据当前代码寻路有个情况就是寻路到终点前临近终点时,可以提前一步结束,这里没有结束,是为了方便演示

参考文章:
A算法完全理解
堪称最好最全的A算法详解(译文)
A星寻路算法介绍
这里的unity工程是参考一篇文章的,是两年前的文章,没有找到,就不放参考链接了

2017-11-03 16:29:18 qq_33747722 阅读数 10583
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

原文地址:blog.liujunliang.com.cn

这里我先引用一篇详细文章来介绍A*算法

本文源码链接:点击打开链接

文章内容如下

简易地图

 

如图所示简易地图, 其中绿色方块的是起点 ( A 表示), 中间蓝色的是障碍物, 红色的方块 ( B 表示) 是目的地. 为了可以用一个二维数组来表示地图, 我们将地图划分成一个个的小方块.

二维数组在游戏中的应用是很多的, 比如贪吃蛇和俄罗斯方块基本原理就是移动方块而已. 而大型

 游戏的地图, 则是将各种"地貌"铺在这样的小方块上.

寻路步骤

1. 从起点开始把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格

 的列表.

2. 寻找起点周围可以到达的方格将它们放入"开启列表", 并设置它们的"父方格" A.

3. 从"开启列表"中删除起点 A, 并将起点加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格

 

图中浅绿色描边的方块表示已经加入 "开启列表" 等待检查. 淡蓝色描边的起点 A 表示已经放入

 "关闭列表" , 它不需要再执行检查.

"开启列表" 中找出相对最靠谱的方块, 什么是最靠谱? 它们通过公式 F=G+H 来计算.

F = G + H 

G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).

 H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以上下左右移动).


我们假设横向移动一个格子的耗费为 10, 为了便于计算, 沿斜方向移动一个格子耗费是 14. 为了

更直观的展示如何运算 FGH, 图中方块的左上角数字表示 F, 左下角表示 G, 右下角表示 H. 看看是否跟你心里想的结果一样?

"开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块), 然后对它进行如下处

:

4. 把它从 "开启列表" 中删除并放到 "关闭列表" .

5. 检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑的方格如果这些方格

还不在 "开启列表" 里的话将它们加入 "开启列表", 计算这些方格的 G, H 值各是多少并设置它们的 "父方格"  C.

6. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过 C 的路径) 到达它的话, G 值是否会更低一些如果新的值更低那就把它的 "父方格" 改为目前选中的方格 C, 然后重新计算它的值和 (H 值不需要重新计算因为对于每个方块, H 值是不变的). 如果新的值比较高就说明经过再到达不是一个明智的选择因为它需要更远的路这时我们什么也不做.

 

如图, 我们选中了 C 因为它的 F 值最小, 我们把它从 "开启列表" 中删除, 并把它加入 "关闭列表". 它右边上下三个都是墙, 所以不考虑它们. 它左边是起始方块, 已经加入到 "关闭列表" , 也不考虑. 所以它周围的候选方块就只剩下 4 . 让我们来看看 C 下面的那个格子, 它目前的 G  14, 

果通过 C 到达它的话, G 将会是 10 + 10, 这比 14 要大, 因此我们什么也不做.

然后我们继续从 "开启列表" 中找出 F 值最小的, 但我们发现 C 上面的和下面的同时为 54, 

时怎么办呢? 这时随便取哪一个都行, 比如我们选择了 C 下面的那个方块 D.


右边已经右上方的都是墙, 所以不考虑, 但为什么右下角的没有被加进 "开启列表" ? 

因为如果 C 下面的那块也不可以走, 想要到达 C 右下角的方块就需要从 "方块的角" 走了, 在程序中设置是否允许这样走. (图中的示例不允许这样走)


就这样, 我们从 "开启列表" 找出 F 值最小的, 将它从 "开启列表" 中移掉, 添加到 "关闭列表".

再继续找出它周围可以到达的方块, 如此循环下去...

那么什么时候停止呢? —— 当我们发现 "开始列表" 里出现了目标终点方块的时候, 说明路径已经

被找到.

如何找回路径


如上图所示, 除了起始方块, 每一个曾经或者现在还在 "开启列表" 里的方块, 它都有一个 "父方块", 通过 "父方块" 可以索引到最初的 "起始方块", 这就是路径.

Unity代码实现

算法类

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

public class AStarAlgorithm 
{
    private const int mGridWidth = 20;    
    private const int mGridHeight = 10;

    //使用二维数组存储点网格    
    public AStarPoint[,] mPointGrid = new AStarPoint[mGridWidth,mGridHeight];
    //存储路径方格子
    public List<AStarPoint> mPathPosList = new List<AStarPoint>();

    private static AStarAlgorithm _instance;
    public static AStarAlgorithm GetInsatnce
    {
        get
        {
            if (_instance == null)
            {
                _instance = new AStarAlgorithm();
            }

            return _instance;
        }
    }

    public AStarAlgorithm()
    {
        InitPoint();
    }

    //在网格上设置点的信息
    private void InitPoint()
    {
        for (int i = 0; i < mGridWidth; i++)
        {
            for (int j = 0; j < mGridHeight; j++)
            {                
                mPointGrid[i, j] = new AStarPoint(i, j);
            }
        }

        //设置障碍物
        mPointGrid[4, 2].mIsObstacle = true;
        mPointGrid[4, 3].mIsObstacle = true;
        mPointGrid[4, 4].mIsObstacle = true;
        mPointGrid[4, 5].mIsObstacle = true;
        mPointGrid[4, 6].mIsObstacle = true;

        //显示障碍物
        for (int x = 0; x < mGridWidth; x++)
        {
            for (int y = 0; y < mGridHeight; y++)
            {
                if (mPointGrid[x, y].mIsObstacle)
                {
                    CreatePath(x, y, Color.blue);
                }
            }
        }
    }

    public void ClearGrid()
    {
        for (int x = 0; x < mGridWidth; x++)
        {
            for (int y = 0; y < mGridHeight; y++)
            {
                if (!mPointGrid[x, y].mIsObstacle)
                {
                    if (mPointGrid[x, y].mGameObject != null)
                    {
                        GameObject.Destroy(mPointGrid[x, y].mGameObject);
                        mPointGrid[x, y].mGameObject = null;

                        //重新设置父节点
                        mPointGrid[x, y].mParentPoint = null;
                    }
                }
            }
        }
    }

    //寻路
    public List<AStarPoint> FindPath(AStarPoint mStartPoint, AStarPoint mEndPoint)
    {
        if (mEndPoint.mIsObstacle || mStartPoint.mPosition == mEndPoint.mPosition)
        {
            return  null;
        }

        //开启列表
        List<AStarPoint> openPointList = new List<AStarPoint>();
        //关闭列表
        List<AStarPoint> closePointList = new List<AStarPoint>();

        openPointList.Add(mStartPoint);

        while (openPointList.Count > 0)
        {
            //寻找开启列表中最小预算值的表格
            AStarPoint minFPoint = FindPointWithMinF(openPointList);
            //将当前表格从开启列表移除 在关闭列表添加
            openPointList.Remove(minFPoint);
            closePointList.Add(minFPoint);
            //找到当前点周围的全部点
            List<AStarPoint> surroundPoints = FindSurroundPoint(minFPoint);            
            //在周围的点中,将关闭列表里的点移除掉
            SurroundPointsFilter(surroundPoints, closePointList);
            //寻路逻辑
            foreach (var surroundPoint in surroundPoints)
            {
                if (openPointList.Contains(surroundPoint))
                {
                    //计算下新路径下的G值(H值不变的,比较G相当于比较F值)
                    float newPathG = CalcG(surroundPoint, minFPoint);
                    if (newPathG < surroundPoint.mG)
                    {
                        surroundPoint.mG = newPathG;
                        surroundPoint.mF = surroundPoint.mG + surroundPoint.mH;
                        surroundPoint.mParentPoint = minFPoint;
                    }
                }
                else
                {
                    //将点之间的
                    surroundPoint.mParentPoint = minFPoint;
                    CalcF(surroundPoint, mEndPoint);
                    openPointList.Add(surroundPoint);
                }
            }

            //如果开始列表中包含了终点,说明找到路径
            if (openPointList.IndexOf(mEndPoint) > -1)
            {
                break;
            }
        }

        return ShowPath(mStartPoint, mEndPoint);
    }

    private List<AStarPoint> ShowPath(AStarPoint start, AStarPoint end)
    {
        mPathPosList.Clear();

        AStarPoint temp = end;
        while (true)
        {
            mPathPosList.Add(temp);

            Color c = Color.white;
            if (temp == start)
            {
                c = Color.green;
            }
            else if (temp == end)
            {
                c = Color.red;
            }
            CreatePath(temp.mPositionX, temp.mPositionY, c);

            if (temp.mParentPoint == null)
                break;
            temp = temp.mParentPoint;
        }

        return mPathPosList;
    }

    private void CreatePath(int x, int y, Color color)
    {
        GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
        go.transform.position = new Vector3(x, y, 0);
        go.GetComponent<Renderer>().material.color = color;
        go.transform.SetParent(GameObject.Find("Path").transform);

        if (mPointGrid[x, y].mGameObject != null)
        {
            GameObject.Destroy(mPointGrid[x, y].mGameObject);             
        }
        mPointGrid[x, y].mGameObject = go;
    }

    //寻找预计值最小的格子
    private AStarPoint FindPointWithMinF(List<AStarPoint> openPointList)
    {
        float f = float.MaxValue;
        AStarPoint temp = null;
        foreach (AStarPoint p in openPointList)
        {
            if (p.mF < f)
            {
                temp = p;
                f = p.mF;
            }
        }
        return temp;
    }

    //寻找周围的全部点
    private List<AStarPoint> FindSurroundPoint(AStarPoint point)
    {
        List<AStarPoint> list = new List<AStarPoint>();

        ////////////判断周围的八个点是否在网格内/////////////
        AStarPoint up = null, down = null, left = null, right = null;
        AStarPoint lu = null, ru = null, ld = null, rd = null;
        if (point.mPositionY < mGridHeight - 1)
        {
            up = mPointGrid[point.mPositionX, point.mPositionY + 1];
        }
        if (point.mPositionY > 0)
        {
            down = mPointGrid[point.mPositionX, point.mPositionY - 1];
        }
        if (point.mPositionX > 0)
        {
            left = mPointGrid[point.mPositionX - 1, point.mPositionY];
        }
        if (point.mPositionX < mGridWidth - 1)
        {
            right = mPointGrid[point.mPositionX + 1, point.mPositionY];
        }
        if (up != null && left != null)
        {
            lu = mPointGrid[point.mPositionX - 1, point.mPositionY + 1];
        }
        if (up != null && right != null)
        {
            ru = mPointGrid[point.mPositionX + 1, point.mPositionY + 1];
        }
        if (down != null && left != null)
        {
            ld = mPointGrid[point.mPositionX - 1, point.mPositionY - 1];
        }
        if (down != null && right != null)
        {
            rd = mPointGrid[point.mPositionX + 1, point.mPositionY - 1];
        }
        

        /////////////将可以经过的表格添加到开启列表中/////////////
        if (down != null && down.mIsObstacle == false)
        {
            list.Add(down);
        }
        if (up != null && up.mIsObstacle == false)
        {
            list.Add(up);
        }
        if (left != null && left.mIsObstacle == false)
        {
            list.Add(left);
        }
        if (right != null && right.mIsObstacle == false)
        {
            list.Add(right);
        }
        if (lu != null && lu.mIsObstacle == false && left.mIsObstacle == false && up.mIsObstacle == false)
        {
            list.Add(lu);
        }
        if (ld != null && ld.mIsObstacle == false && left.mIsObstacle == false && down.mIsObstacle == false)
        {
            list.Add(ld);
        }
        if (ru != null && ru.mIsObstacle == false && right.mIsObstacle == false && up.mIsObstacle == false)
        {
            list.Add(ru);
        }
        if (rd != null && rd.mIsObstacle == false && right.mIsObstacle == false && down.mIsObstacle == false)
        {
            list.Add(rd);
        }

        return list;
    }

    //将关闭带你从周围点列表中关闭
    private void SurroundPointsFilter(List<AStarPoint> surroundPoints, List<AStarPoint> closePoints)
    {
        foreach (var closePoint in closePoints)
        {
            if (surroundPoints.Contains(closePoint))
            {
                Debug.Log("将关闭列表的点移除");
                surroundPoints.Remove(closePoint);
            }
        }
    }

    //计算最小预算值点G值
    private float CalcG(AStarPoint surround, AStarPoint minFPoint)
    {
        return Vector3.Distance(surround.mPosition, minFPoint.mPosition) + minFPoint.mG;
    }

    //计算该点到终点的F值
    private void CalcF(AStarPoint now, AStarPoint end)
    {
        //F = G + H
        float h = Mathf.Abs(end.mPositionX - now.mPositionX) + Mathf.Abs(end.mPositionY - now.mPositionY);
        float g = 0;
        if (now.mParentPoint == null)
        {
            g = 0;
        }
        else
        {
            g = Vector2.Distance(new Vector2(now.mPositionX, now.mPositionY), new Vector2(now.mParentPoint.mPositionX, now.mParentPoint.mPositionY)) + now.mParentPoint.mG;
        }
        float f = g + h;
        now.mF = f;
        now.mG = g;
        now.mH = h;
    }
}


其中AStarPoint是存储点的信息(位置、父格子、实体对象)

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


/// <summary>
/// 存储寻路点信息
/// </summary>
public class AStarPoint
{
    //父“格子”
    public AStarPoint mParentPoint { get; set; }
    //格子显示对象
    public GameObject mGameObject { get; set; }

    public float mF { get; set; }
    public float mG { get; set; }
    public float mH { get; set; }
    //点的位置
    public Vector2 mPosition { get; set; }
    public int mPositionX { get; set; }
    public int mPositionY { get; set; }
    //该点是否处于障碍物
    public bool mIsObstacle { get; set; }

    public AStarPoint(int positionX,int positionY)
    {
        this.mPositionX = positionX;
        this.mPositionY = positionY;
        this.mPosition = new Vector2(mPositionX, mPositionY);
        this.mParentPoint = null;
    }
}


寻路模拟

创建一个DoPlayer测试类,用于模仿一个物体的寻路
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class DoPlayer : MonoBehaviour
{
    private GameObject mCubeParent;

    //存储路径点
    private List<AStarPoint> mPathPosList;

    //网格大小
    private const int mGridWidth = 20;
    private const int mGridHeight = 10;

    private AStarPoint[,] mPointGrid;

    private AStarPoint mStartPos;
    private AStarPoint mEndPos { get; set; }

    //每一秒发生位移
    private float mTime = 0.7f;
    private float mTimer = 0.0f;

    //目标点
    private int mTargetX { get; set; }
    private int mTargetY { get; set; }

    private void Start()
    {
        mCubeParent = GameObject.Find("Plane");

        mPointGrid = AStarAlgorithm.GetInsatnce.mPointGrid;
        mStartPos = mPointGrid[0, 0];

        InitBG();
    }

    private void Update()
    {
        mTimer += Time.deltaTime;
        if (mTimer >= mTime)
        {
            mTimer = 0;
            Walk();
        }
    }

    private void Walk()
    {     
        if (mPathPosList != null && mPathPosList.Count > 1)
        {
            mStartPos = mPathPosList[mPathPosList.Count - 1];
            Color color = mStartPos.mGameObject.GetComponent<Renderer>().material.color;
            mPathPosList.Remove(mStartPos);
            Destroy(mStartPos.mGameObject);
            mStartPos.mGameObject = null;
            
            mStartPos = mPathPosList[mPathPosList.Count - 1];
            mStartPos.mGameObject.GetComponent<Renderer>().material.color = color;
            
        }
    }

    private void InitBG()
    {
        for (int i = 0; i < mGridWidth; i++)
        {
            for (int j = 0; j < mGridHeight; j++)
            {
                CreateCube(i, j, Color.gray);
            }
        }
    }


    private void CreateCube(int x, int y, Color color)
    {
        GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
        go.transform.SetParent(mCubeParent.transform);
        go.transform.position = new Vector3(x, y, 0);
        go.transform.localScale = new Vector3(0.9f, 0.9f, 0.9f);
        go.GetComponent<Renderer>().material.color = color;

        go.AddComponent<Cube>().FindPath = FindPath;
    }

    public void FindPath(int mTargetX, int mTargetY)
    {
        if (mPathPosList != null)
        {
            mPathPosList.Clear();
        }
        AStarAlgorithm.GetInsatnce.ClearGrid();

        //网格点对象重新刷新了  需要使用网格来索引到点 mPathPosList存储的点是之前的AStarPoint
        this.mEndPos = mPointGrid[mTargetX, mTargetY];
        this.mStartPos = mPointGrid[mStartPos.mPositionX, mStartPos.mPositionY];

        mPathPosList = AStarAlgorithm.GetInsatnce.FindPath(this.mStartPos, mEndPos);
    }
}

其中创建的Cube网格类代码如下
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Cube : MonoBehaviour
{
    public delegate void VoidDelegate(int x, int y);
    public VoidDelegate FindPath;

    private void OnMouseDown()
    {
        if (FindPath != null)
        {
            FindPath((int)this.transform.position.x, (int)this.transform.position.y);
        }
    }
}

效果展示

效果显示正常,绿色方块代表主角位置,红色方块代表目标点,白色方块代表路径




原文地址:blog.liujunliang.com.cn


2017-05-15 14:31:24 jxw167 阅读数 2609
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

笔者介绍:姜雪伟,IT公司技术合伙人,IT高级讲师,CSDN社区专家,特邀编辑,畅销书作者,国家专利发明人;已出版书籍:《手把手教你架构3D游戏引擎》电子工业出版社和《Unity3D实战核心技术详解》电子工业出版社等。

CSDN视频网址:http://edu.csdn.net/lecturer/144

A*寻路算法通常是应用于大型网络游戏中,A*算法通常应用在服务器中,在移动端游戏开发中,A*算法也可以在Unity端实现,下面给读者介绍一个插件A* PathFindingProject,它的下载地址:https://arongranberg.com/astar/download#,可以直接导入到Unity工程中,它目前支持直接寻路和网格寻路。在官网上有免费的版本和收费的版本,作为学习者可以下载免费的版本原理是一样的。下面通过它们提供的Demo,给读者介绍一下:

在导入到Unity工程后,使用时首选建立一个空的GameObject,然后将AstarPath脚本挂接上去。如下图所示:


这个AstarPath是整个A*寻路的核心组件,它计算了整个地面的寻路路径以及保存信息,它保存的是二进制文件格式,操作如下所示:

该类提供了保存,加载等函数,详情可以查看类AstarPathEditor,函数接口如下所示:

void DrawSerializationSettings () {
			serializationSettingsArea.Begin();
			GUILayout.BeginHorizontal();

			if (GUILayout.Button("Save & Load", level0LabelStyle)) {
				serializationSettingsArea.open = !serializationSettingsArea.open;
			}

			if (script.data.cacheStartup && script.data.file_cachedStartup != null) {
				GUIUtilityx.PushTint(Color.yellow);
				GUILayout.Label("Startup cached", thinHelpBox, GUILayout.Height(15));
				GUILayout.Space(20);
				GUIUtilityx.PopTint();
			}

			GUILayout.EndHorizontal();

			// This displays the serialization settings
			if (serializationSettingsArea.BeginFade()) {
				script.data.cacheStartup = EditorGUILayout.Toggle(new GUIContent("Cache startup", "If enabled, will cache the graphs so they don't have to be scanned at startup"), script.data.cacheStartup);

				script.data.file_cachedStartup = EditorGUILayout.ObjectField(script.data.file_cachedStartup, typeof(TextAsset), false) as TextAsset;

				if (script.data.cacheStartup && script.data.file_cachedStartup == null) {
					EditorGUILayout.HelpBox("No cache has been generated", MessageType.Error);
				}

				if (script.data.cacheStartup && script.data.file_cachedStartup != null) {
					EditorGUILayout.HelpBox("All graph settings will be replaced with the ones from the cache when the game starts", MessageType.Info);
				}

				GUILayout.BeginHorizontal();

				if (GUILayout.Button("Generate cache")) {
					var serializationSettings = new Pathfinding.Serialization.SerializeSettings();
					serializationSettings.nodes = true;

					if (EditorUtility.DisplayDialog("Scan before generating cache?", "Do you want to scan the graphs before saving the cache.\n" +
							"If the graphs have not been scanned then the cache may not contain node data and then the graphs will have to be scanned at startup anyway.", "Scan", "Don't scan")) {
						MenuScan();
					}

					// Save graphs
					var bytes = script.data.SerializeGraphs(serializationSettings);

					// Store it in a file
					script.data.file_cachedStartup = SaveGraphData(bytes, script.data.file_cachedStartup);
					script.data.cacheStartup = true;
				}

				if (GUILayout.Button("Load from cache")) {
					if (EditorUtility.DisplayDialog("Are you sure you want to load from cache?", "Are you sure you want to load graphs from the cache, this will replace your current graphs?", "Yes", "Cancel")) {
						script.data.LoadFromCache();
					}
				}

				GUILayout.EndHorizontal();

				if (script.data.data_cachedStartup != null && script.data.data_cachedStartup.Length > 0) {
					EditorGUILayout.HelpBox("Storing the cached starup data on the AstarPath object has been deprecated. It is now stored " +
						"in a separate file.", MessageType.Error);

					if (GUILayout.Button("Transfer cache data to separate file")) {
						script.data.file_cachedStartup = SaveGraphData(script.data.data_cachedStartup);
						script.data.data_cachedStartup = null;
					}
				}

				GUILayout.Space(5);

				GUILayout.BeginHorizontal();
				if (GUILayout.Button("Save to file")) {
					string path = EditorUtility.SaveFilePanel("Save Graphs", "", "graph.bytes", "bytes");

					if (path != "") {
						var serializationSettings = Pathfinding.Serialization.SerializeSettings.Settings;
						if (EditorUtility.DisplayDialog("Include node data?", "Do you want to include node data in the save file. " +
								"If node data is included the graph can be restored completely without having to scan it first.", "Include node data", "Only settings")) {
							serializationSettings.nodes = true;
						}

						if (serializationSettings.nodes && EditorUtility.DisplayDialog("Scan before saving?", "Do you want to scan the graphs before saving? " +
								"\nNot scanning can cause node data to be omitted from the file if the graph is not yet scanned.", "Scan", "Don't scan")) {
							MenuScan();
						}

						uint checksum;
						var bytes = SerializeGraphs(serializationSettings, out checksum);
						Pathfinding.Serialization.AstarSerializer.SaveToFile(path, bytes);

						EditorUtility.DisplayDialog("Done Saving", "Done saving graph data.", "Ok");
					}
				}

				if (GUILayout.Button("Load from file")) {
					string path = EditorUtility.OpenFilePanel("Load Graphs", "", "");

					if (path != "") {
						byte[] bytes;
						try {
							bytes = Pathfinding.Serialization.AstarSerializer.LoadFromFile(path);
						} catch (System.Exception e) {
							Debug.LogError("Could not load from file at '"+path+"'\n"+e);
							bytes = null;
						}

						if (bytes != null) DeserializeGraphs(bytes);
					}
				}

				GUILayout.EndHorizontal();
			}

			serializationSettingsArea.End();
		}

该函数调用了JsonSerializer类中的两个函数如下所示:

		public static void SaveToFile (string path, byte[] data) {
#if NETFX_CORE
			throw new System.NotSupportedException("Cannot save to file on this platform");
#else
			using (var stream = new FileStream(path, FileMode.Create)) {
				stream.Write(data, 0, data.Length);
			}
#endif
		}

		/** Load the specified data from the specified path */
		public static byte[] LoadFromFile (string path) {
#if NETFX_CORE
			throw new System.NotSupportedException("Cannot load from file on this platform");
#else
			using (var stream = new FileStream(path, FileMode.Open)) {
				var bytes = new byte[(int)stream.Length];
				stream.Read(bytes, 0, (int)stream.Length);
				return bytes;
			}
#endif
		}

场景通过AstarPath脚本布置完后,接下来开始寻路了,需要挂接如下的脚本:


其中AI脚本是用于查询物体的,它会调用Seeker脚本中的函数,同时Seeker会对场景做一些标识操作,这样AI寻路基本完成,其中AI脚本是继承AIPath类,非常方便我们自己编写,扩展功能,它是通过递归的方式进行路径查询,锁定目标的,它运行的效果如下所示:






2018-08-11 17:35:13 liaoshengg 阅读数 2874
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

前言


在两个物体之间寻找最短有效路径

  1. 学习A*思想
  2. 其他算法,计算机估计距离
  3. 曼哈顿(城市街区算法、直来直去)
  4. 几何法(对角线,勾股定理)
  5. 估算法(先对角线,再直线)本文使用估算法计算距离
  6. GHF
  7. G : 从开始到当前位置的移动步数
  8. H : 从当前位置到目标位置的距离,使用上面3种算法获得
  9. F :G + H 的总和
  10. OpenList 和 CloseList
  11. OpenList :被考虑最短有效路径的位置集合
  12. CloseList : 不被考虑最短语效路径的位置集合
  13. 寻路思想:知道F = G + H 且知道如何计算得出,知道OpenList 和CloseList并知道如何得出

F G H 分别表示什么,有什么用,如何计算机它们?


  1. 首先得G表示的是从起始结点走到下一个结点(下下…下个)的距离,因此这个G是每走一格就会叠加一次并赋值给新的结点,从而累计得到从当前结点到下下下..个结点的距离
    newCostg = gCost + GetDistance()
    nodeCell.gCost = newCostg; //移动步数
  2. 其次是H,它表示从当前结点到终点结点的最短距离
  3. F 就是 G + H 得到的估算值

再根据百度百科的解释做个比较或许更容易理解:

f(n)=g(n)+h(n)
f(n) 是从初始状态经由状态n到目标状态的代价估计,
g(n) 是在状态空间中从初始状态到状态n的实际代价,
h(n) 是从状态n到目标状态的最佳路径的估计代价。
(对于路径搜索问题,状态就是图中的节点,代价就是距离)

这里需要写一个两点之间的距离估算方法,来计算得出G H 从而得出F
注意最好避免小数计算,
因为计算机计算机浮点的效率较低
而这里的x表示长 y表示高 可以通过画图理解,x = y 就是正方形,两点距离就是1.4 ,避免小数计算乘10 就是14整数了

    //计算距离 ,这里是因为NodeItem是嵌套类,在Grid里面 
    public int GetDistance(Grid.NodeItem a,Grid.NodeItem b) {
        //估算法
        int x = Mathf.Abs (a.x - b.x);
        int y = Mathf.Abs (a.y - b.y);
        //根号2 = 1.4  然后都扩大10倍 去除小数计算,这里返回值都放大了10倍
        if (x > y) {
            return 14 * y + 10 * (x - y);  
        }else{
            return 14 * x + 10 * (y - x);
        }
    //也可以用曼哈顿得到距离
    //return Mathf.Abs (a.x-b.x)+Mathf.Abs(a.y-b.y);//得到正数,但是可能是浮点数
    }

OpenList和CloseList是什么,可以用来做什么?


OpenList :被考虑最短有效路径的位置集合
CloseList : 不被考虑最短语效路径的位置集合

1、从第一个结点开始,放入OpenList容器,然后这个结点获取全部周围符合条件(1)的结点;
2、把符合条件的结点全部放入OpenList容器;
3、并且还要对周围符合条件(2)的每个结点进行更新他们的G值和H值,记录这个当前结点为它们的父结点;
4、然后把这第一个结点放入CloseList容器里 这是第一次循环

5、随后进入第二次循环,
此时就从OpenList容器找到符合条件(3)的当前结点,
当前结点是要在OpenList容器中H值最小,且F值最小的;
6、找到后就获取这个当前结点的周围结点,然后重新进入第2步骤到第5步骤;
7、此时它会慢慢接近终点,直到发现当前结点==最终结点;
8、最终结点找到后根据最终结点的父结点一个一个返回(类似数据结构的链表)找到开始结点;
9、此时用一个容器(List容器、Stack容器等)来接收这些结点,这些结点的Position就是最短路径

介绍符合条件:
第一个符合条件(1)是对周围结点的判断,该结点如果是标有墙类标记、或不可走标记就是不符合条件的,
第二个符合条件(2)是在满足第一个条件的前提下,在CloseList容器下遍历过,或更新后的G值比原来G值还要大的结点,2者不满足一个就是不满足条件,不能更新该结点的G,H值
第三个符合条件(3)就是存储在OpenList容器中的结点中,找一个H值最小,且, F值最小的结点,找到这个H值且F值最小的结点后,就把这个结点设置为当前结点。

当前结点在这里指为离终点结点的最短距离估计点。这个点其实并不会太智能,一下就找到最短路径。
而是根据OpenList里的全部结点来判断找到离终点最短估计值最小的结点,让周围的结点加入OpenList。然后就放入CloseList容器这个最短估计值最小的结点以后不再做任何判断。

CS脚本代码

结点类
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarNode {

    public bool isWall;
    public int posX;
    public int posY;
    public int posZ;

    public Vector3 pos;
    public AStarNode parentNode;

    public int costG;
    public int costH;

    public int CostF{
        get{ return costG + costH; }
    }

    public AStarNode(bool _isWall,Vector3 _pos,int _z,int _x){
        this.isWall = _isWall;
        this.pos = _pos;
        this.posX = _x;
        this.posZ = _z;
    }
}

结点地图生成类
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStarMAP : MonoBehaviour {

    public AStarNode [,] AllNodeGroup; 

    public LayerMask wallLayer;
    public int xWidth;
    public int zHeight;
    private float nodeRange = 0.4f;

    public GameObject nodeWallPrefabs;

    void Awake(){
        Init();
    }

    void Init(){

        zHeight = 40;
        xWidth = 40;
        AllNodeGroup = new AStarNode[zHeight, xWidth];
        //初始化所有结点,把结点node存入二维数组里
        for (int i = 0; i < zHeight; i++) {
            for (int j = 0; j < xWidth; j++) {

                Vector3 nodePos =new Vector3 (j,0,i);
                nodePos += new Vector3 (0.5f, 0, 0.5f); 
                bool isWall = Physics.CheckSphere (nodePos, nodeRange, wallLayer);
                AStarNode nd = new AStarNode (isWall, nodePos,i,j);

                if (isWall) {
                    GameObject obj = GameObject.Instantiate (nodeWallPrefabs, nodePos, Quaternion.identity) as GameObject;

                }
                AllNodeGroup[i,j] = nd;

            }
        }
    }

    public List<AStarNode> GetAroundNodes(AStarNode curNode){

        List<AStarNode> retGroup = new List<AStarNode> ();
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                int z = curNode.posZ + i;
                int x = curNode.posX + j;

                if (x >= 0 && x < xWidth && z >= 0 && z < zHeight) {
                    retGroup.Add (AllNodeGroup [z, x]);
                }
            }
        }
        return retGroup;

    }

    public AStarNode GetItem(Vector3 pos){
        int x = Mathf.RoundToInt (pos.x - 0.5f);
        int z = Mathf.RoundToInt (pos.z - 0.5f);
        x = Mathf.Clamp (x, 0, xWidth - 1);
        z = Mathf.Clamp (z, 0, zHeight - 1);
        return AllNodeGroup [z, x];
    }
}
找最短路径类

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

public class AStarFindPath : MonoBehaviour {

    private AStarMAP aStarMap;

    public List<Vector3> peoplePath;
    public List<AStarNode> peopleNodePath;

    void Start(){
        aStarMap = GetComponent<AStarMAP> ();
    }

    private int GetDistance(AStarNode startNode,AStarNode endNode){
        int x = Mathf.Abs (startNode.posX - endNode.posX);
        int z = Mathf.Abs (startNode.posZ - endNode.posZ);
        if (x > z) {
            return 10 * (x - z) + 14 * z;
        } else {
            return 10 * (z - x) + 14 * x;
        }
    }


    //根据开始和结束点来查找最优路径
    private void toFindPath(Vector3 startPos,Vector3 endPos) {

        //根据位置获取到NodeItem
        AStarNode start = aStarMap.GetItem (startPos);
        AStarNode end = aStarMap.GetItem (endPos);

        List<AStarNode> openList = new List<AStarNode> ();
        List<AStarNode> closeList = new List<AStarNode> ();

        openList.Add (start);
        //从开始点开始判断
        while (openList.Count > 0) {
            AStarNode curNode = openList [0];
            for (int i = 0; i < openList.Count; i++) {
                //h是估算法的距离  f是估算法加实际格子的距离g
                if (openList [i].CostF < curNode.CostF && openList [i].costH < curNode.costH) {
                    curNode = openList [i];
                }
            }

            openList.Remove (curNode);
            closeList.Add (curNode);

            //已经找到结束点
            if (curNode == end) {
                Debug.Log (">>");
                GetPathWithPos (startPos, endPos);
                return;
            }
            // 获取当前点的周围点
            List<AStarNode> nodeItemGroup =  aStarMap.GetAroundNodes(curNode);

            //遍历当前点周围的NodeItem 对其进行
            foreach (AStarNode nodeCell in nodeItemGroup) {
                //先过滤: 墙 closeList
                if (nodeCell.isWall || closeList.Contains (nodeCell)) {
                    continue;
                }

                //计算 G H F 进行赋值
                int newCostg = curNode.costG + GetDistance (curNode, nodeCell);

                if (newCostg <= nodeCell.costG || !openList.Contains (nodeCell)) {
                    //刷新g h
                    nodeCell.costG = newCostg; //移动步数距离
                    nodeCell.costH = GetDistance (nodeCell, end);//到该结点到终点的距离
                    //设置中心点为父亲
                    nodeCell.parentNode = curNode;
                    if (!openList.Contains (nodeCell)) {
                        openList.Add (nodeCell);
                    }
                }
            }
        }
    }

    //获取路径
    private void GetPathWithPos(Vector3 startPos,Vector3 endNodePos){
        //此处可以优化GC内存
        peopleNodePath = new List<AStarNode> ();
        peoplePath = new List<Vector3> ();

        AStarNode endNode = aStarMap.GetItem (endNodePos);
        AStarNode startNode = aStarMap.GetItem (startPos);

        if (endNode != null) {

            AStarNode temp = endNode;

            while (temp != startNode) {
                peoplePath.Add (temp.pos);
                peopleNodePath.Add (temp);
                temp = temp.parentNode;
            }
            peopleNodePath.Reverse ();
            peoplePath.Reverse ();
        }
    }
    //提供给人物移动类使用
    public List<Vector3> PeopleGoTo(Vector3 startpos,Vector3 endpos){
        toFindPath (startpos, endpos);
        return peoplePath;
    }

    public List<AStarNode> PeopleGoToWithNode(Vector3 startpos,Vector3 endpos){
        toFindPath (startpos, endpos);
        return peopleNodePath;
    }
}
人物移动实现类

这里是我以前实现了一个有点简单AI的A*移动,现在看起来有点丑,,还可以做优化,
实现的时候也可以发现:
A*算法可以做出接口来用的,不过需要根据需求情况设置一些值。
开始结点,最终点结点的位置(可自动获取开始结点位置,鼠标点击获取终点结点位置)
生成地图的大小,结点的大小,地图、结点坐标设计需要考虑
找到后的路径结点容器该怎么优化,实现是也是要考虑的

这里我使用了协程来写。

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

public class PlayerTest : MonoBehaviour {

    AStarFindPath astarFindPath;
    public Vector3 endPos = new Vector3(12.5f,0,0.5f);
    RaycastHit hit;
    Ray ray;

    AStarNode currentNode;
    public bool isGO = true;
    List<AStarNode> pathGroupNode;
    void Awake(){
        astarFindPath = GetComponent<AStarFindPath> ();
    }
    void Start () {
        pathGroupNode = new List<AStarNode> ();
    }
    void Update(){
        peopleCtrl ();
    }
    void peopleCtrl(){
        if (Input.GetMouseButtonDown (0)) {
            ray = Camera.main.ScreenPointToRay (Input.mousePosition);
            if (Physics.Raycast (ray, out hit)) {
                endPos = hit.point;
                pathGroupNode.Clear ();
                i = 1;
                //执行A*算法
                pathGroupNode = astarFindPath.PeopleGoToWithNode (transform.position, endPos);
                if (pathGroupNode.Count <= 1) {
                    Debug.Log ("不需要走");
                    return;
                }
                currentNode = pathGroupNode [1];
                StopAllCoroutines ();
                StartCoroutine (pahtGo ());

            } else {
                Debug.Log ("重新点击");
            }
        }
    }
    IEnumerator pahtGo(){
        while (true) {
            if (Vector3.Distance (transform.position, currentNode.pos) <= 0.5f) {
                currentNode = pathGroupNode[i++];
                if (currentNode == null) {
                    Debug.Log ("到终点了...");
                    yield break;
                }   
                if (i >= pathGroupNode.Count) {
                    Debug.Log ("到达目的地");
                    yield break;
                }
            } else {
                transform.LookAt (currentNode.pos);
                transform.Translate (Vector3.forward * 2f * Time.deltaTime, Space.Self);
            }
            yield return new WaitForEndOfFrame ();
        }
    }
}