Unity系列研究

Unity-基于路径点寻路算法的研究(四)代码实现

在上一篇文章中Unity-基于路径点寻路算法的研究(三)我向大家介绍了如何寻找到一条寻路路径的解决思路。先来看一下上篇文章中的一张图

20160817180628

红线表示的路径就是要走的路径,我们以哪种方式行走呢,从V点走到T点,再从T点走到S点,再从S点走到P点,再从P点走到Q点?

显然这样的一条行走路径并不是一条最短路径,再来看一张图

20160817184103

上图中由点V->W->Z->A1->Q构成的紫色路径,是重新规划后的路径,我们发现紫色的路径与红色路径(V->T->S->P->Q)构成了三个三角形,而且每个三角形中紫色路径都只占了一条边,也就是说紫色路径就是基于V->T->S->P->Q路径点的一条最短路径。

我来简单介绍一下如何得出这条路径。先从V点起,AI向自己能直接到达的点T移动,同时也会判断是否能直接到达下一个寻路点S。当移动到W点时,AI通过判断发现自己能直接到达点S,这时开始向S点移动,并判断自己是否能直接到达下一个点P点。当AI移动到点Z时发现自己能直接到达点P,这时开始向P点移动,并判断自己是否能直接到达下一个点Q。当AI移动到点A1时发现自己能直接到达目标点Q,这时便直接移动至目标点。

好了,到此所有问题的解决思路都有了,接下来就来看看代码的简单实现

首先是上一篇文章的寻路树。


// 寻路树节点
public class NavTreeNode {

    public Vector3 value;
    public List<NavTreeNode> parents = new List<NavTreeNode>();
    public NavTreeNode(Vector3 value) {
        this.value = value;
    }
    public List<NavTreeNode> nodeList = new List<NavTreeNode>();
    public void AddNode(NavTreeNode node) {
        if(!node.parents.Contains(this))
            node.parents.Add(this);
        nodeList.Add(node);
    }

    public void RemoveNode(NavTreeNode node) {
        nodeList.Remove(node);
    }


    public bool HasNextNode (){
        if (nodeList.Count > 0)
            return true;

        return false;
    }
}

上面的NavTreeNode类用来描述寻路树节点

///<summary>
/// 寻路树
/// </summary>
public class NavTree{

    ///<summary>
    /// 所有的寻路节点
    /// </summary>
    private List<NavTreeNode> m_all_NavNode = new List<NavTreeNode>();

    ///<summary>
    /// 所有的障碍点
    ///</summary>
    private List<Vector3> obstaclePoint;

    ///<summary>
    /// 导航路径点
    ///</summary>
    private List<Vector3> m_navPoint;

    ///<summary>
    /// 目标节点
    ///</summary>
    private NavTreeNode targetNode;
    ///<summary>
    /// 当前目标点位置
    ///</summary>
    private Vector3 navPosition; 

    ///<summary>
    /// 寻路树根节点
    ///</summary>
    private NavTreeNode rootNode;

    ///<summary>
    /// 最佳路径
    ///</summary>
    private List<Vector3> bestPath = new List<Vector3>();

    ///<summary>
    /// 下一个移动点
    ///</summary>
    public Vector3 nextPoint;

    public NavTree(NavTreeNode targetNode,List<Vector3> obstaclePoint) {
        SetTargetNode(targetNode);
        this.obstaclePoint = obstaclePoint;
    }

    public NavTree(NavTreeNode targetNode, List<Vector3> obstaclePoint, List<Vector3> navPoint)
    {
        this.obstaclePoint = obstaclePoint;
        SetTargetNode(targetNode);
        InitNavNode(navPoint);
        
    }

    public NavTree(List<Vector3> obstaclePoint, List<Vector3> navPoint)
    {
        this.obstaclePoint = obstaclePoint;
        InitNavNode(navPoint);
        
    }

    ///<summary>
    /// 设置或更新寻路目标
    /// </summary>
    /// <param name="target">目标节点</param>
    private void SetTargetNode(NavTreeNode target) {
        if (target == null) {
            Debug.LogError("NavTree->>SetTargetNode->params target is null");
            return; }

        //清空以前的目标节点
        if(m_all_NavNode.Count>0&&m_all_NavNode.Contains(targetNode))
            m_all_NavNode.Remove(targetNode);
        //更新目标节点
        targetNode = target;
        m_all_NavNode.Add(targetNode);
    }

    ///<summary>
    /// 设置新的寻路目标
    /// </summary>
    /// <param name="target"></param>
    public void SetTargetNode(Vector3 target) {


        //如果新的目标点与原先一致则无需更新
        if (targetNode!=null&&target == targetNode.value)
        {
            //Debug.Log("一样不跟新");
            return;
        }
        SetTargetNode(new NavTreeNode(target));

    }

    ///<summary>
    /// 重新生成寻路树
    ///</summary>
    ///<param name="root"></param>
    public void UpdateNavTree(Vector3 root)
    {
        //如果能直接到达
        if (!Tools.PolygonLineIsCross(root, targetNode.value, obstaclePoint)) {
            //Debug.Log("直接到达");
            nextPoint = targetNode.value;
            return;
        }
        //当目标位置改变时更新寻路树并重新计算路径
        if (navPosition == null || navPosition != targetNode.value)
        {
            //Debug.Log("重新构造");
            rootNode = new NavTreeNode(root);
            ClearParentNode();
            //生成寻路树
            UpdateNavTree(rootNode);
            //计算最短路径
            CreateBestPath();
            
        }
        navPosition = targetNode.value;

        Cal_NextNavPoint(root);
    }

    ///<summary>
    /// 清除寻路树的节点之间的父子关系
    ///</summary>
    private void ClearParentNode() {

        for (int i = 0; i < m_all_NavNode.Count; i++) {
            m_all_NavNode[i].parents.Clear();
        }

    }

    ///<summary>
    /// 更新寻路树
    ///</summary>
    ///<param name="root"></param>
    private void UpdateNavTree(NavTreeNode root)
    {
        
        if (targetNode == null)
        {
            Debug.LogError("NavTree->Please init targetNode! targetNode is null");
            return;
        }
        //找到相连通的节点
        List<NavTreeNode> nodes = FindConnectedPoint(root);

        if (nodes.Count==0) {
            Debug.LogError("找不到寻路点!!!!");
        }

        //Debug.Log(nodes.Count+"->"+root.value);
        for (int i = 0; i < nodes.Count; i++) { // Debug.Log("值->" + nodes[i].value);
        }
        for (int i = 0; i < nodes.Count; i++)
        {
            //不是自己的父节点
            if (!root.parents.Contains(nodes[i]))
            {
               // Debug.Log("--");
                root.AddNode(nodes[i]);
            }
            else {
               // Debug.Log("++");
            }
        }
        for (int i = 0; i < nodes.Count; i++) {
            if (!root.parents.Contains(nodes[i]))
            {
               UpdateNavTree(nodes[i]);
            }
            
        }
    }


    ///<summary>
    /// 初始化寻路节点
    ///</summary>
    public void InitNavNode(List<Vector3> all_NavPoint)
    {
        for (int i = 0; i < all_NavPoint.Count; i++)
        {

            m_all_NavNode.Add(new NavTreeNode(all_NavPoint[i]));
        }
    }

    ///<summary>
    /// 获取一个点的所有连通点
    ///</summary>
    ///<param name="vec"></param>
    /// <returns></returns>
    public List<NavTreeNode> FindConnectedPoint(NavTreeNode node)
    {

        List<NavTreeNode> connectedPoints = new List<NavTreeNode>();
        //Debug.Log("node数量:"+m_all_NavNode.Count);
        for (int i = 0; i < m_all_NavNode.Count; i++)
        {
            //跳过自身节点
            if (m_all_NavNode[i]==node)
            {
                continue;
            }
            //如果两点连通
            if (!Tools.PolygonLineIsCross(node.value, m_all_NavNode[i].value, obstaclePoint))
            {

                connectedPoints.Add(m_all_NavNode[i]);
            }

        }
        return connectedPoints;
    }

    ///<summary>
    /// 从根节点开始查找目标节点(递归)
    /// </summary>
    /// <param name="root"></param>
    /// <param name="target"></param>
    private void FindNode(NavTreeNode root,Vector3 target)
    {
        if (root == null) {
            return ;
        }
        if (root.value == target)
        {
            targetNode = root;
        }
        for(int i =0;i<root.nodeList.Count;i++)
        {
          FindTarget(root.nodeList[i],target);
        }

    }

    ///<summary>
    /// 获取目标节点
    /// </summary>
    /// <param name="root"></param>
    /// <param name="target"></param>
    /// <returns></returns>
    public NavTreeNode FindTarget(NavTreeNode root, Vector3 target) {
        targetNode = null;
        FindNode(root,target);
        return targetNode;
    }

    ///<summary>
    /// 构建最短路径
    /// </summary>
    /// <param name="startNode">起始节点</param>
    /// <returns></returns>
    public List<Vector3> CreateBestPath() {

        //bestPath = new List<Vector3>();
        
        if (targetNode==null)
        {
            return null;
        }
        bestPath.Clear();
        FindBestPath(targetNode);
        bestPath.Reverse();   //取反路径
        
       
        
        return bestPath;
    }

    ///<summary>
    /// 获取下一个寻路点
    /// </summary>
    /// <returns></returns>
    public Vector3 Cal_NextNavPoint(Vector3 selfPoint) {



        if (bestPath == null) {
            Debug.LogError("bestPath is null,请先执行UpdateNavTree");
            return Vector3.zero;
        }
        //如果能直接到达下一个寻路点  则跳过当前寻路点
        if (bestPath.Count > 2 && !Tools.PolygonLineIsCross(selfPoint, bestPath[2], obstaclePoint))
        {
            Debug.Log("移除点");
            bestPath.RemoveAt(1);
        }
        else {
            //Debug.Log("看不见下一个点");
 
                nextPoint = bestPath[1];

        }
          //下标0是当前位置  1为下一个位置
        return nextPoint;
    }

    ///<summary>
    /// 查找一条最佳路径(递归)
    /// </summary>
    /// <param name="node"></param>
    private void FindBestPath(NavTreeNode node)
    {
        if (node == null)
            return;
        bestPath.Add(node.value);

        if(node.parents==null)
        {
            return;
        }

        if (node.parents.Count == 1)
        {

            
            FindBestPath(node.parents[0]);
        }
        //对分叉路径点的判断
        else {
            for (int i = 0; i < node.parents.Count; i++)
            {
                bool isbestPoint = true;
                for (int j = 0; j < node.parents.Count&&j!=i; j++)
                {
                    if (node.parents[j].parents.Contains(node.parents[i]))
                    {
                        isbestPoint = true;
                    }
                    else {
                        isbestPoint = false;
                    }
                }
                if (isbestPoint) {

                    FindBestPath(node.parents[i]);
                }
            }
        }

    }
}

上面的NavTree类涵盖了AI寻路中需要的基本的操作,如最优路径的计算,下一个移动位置等。
NavTree中使用了Unity-基于路径点寻路算法的研究(二)中的PolygonLineIsCross方法用来判断AI是否能直接到达某一个点(注:NavTree中用到HData类中包含了静态的PolygonLineIsCross方法)。
虽然NavTree中使用了大量的递归运算(毕竟是对树的操作),但这些递归方法只会在需要的时候调用一次,所以不会影响整体效率。

好了,所有的东西都有了,我们来用Unity做一个简单的示例吧

首先是构建场景,简单做成下图的样子

20160818192841

蓝色线框表示可以移动的范围,黄色点构成寻路路径点(这里只需要三个寻路点就能满足整个寻路需求,当然了也可以添加更多的路径点来达到一个更好的寻路效果),橘色方块为我们要移动的对象。

20160818193224

NavObject里存放了寻路点和障碍点的信息

20160818193250

cube添加了CharacterController组件便于我们控制,AutoNav就是用来自动寻路的脚本。

public class AutoNav : MonoBehaviour {

    ///<summary>
    /// 所以障碍点和寻路点的信息
    ///</summary>
    public NavObject navObject;

    ///<summary>
    /// 角色控制器
    ///</summary>
    public CharacterController controller;

    ///<summary>
    /// 表示点击位置的小球
    ///</summary>
    private GameObject mousePoint;

    ///<summary>
    /// 目标位置
    ///</summary>
    private Vector3 target;

    ///<summary>
    /// 寻路树
    ///</summary>
    private NavTree navTree;
    // Use this for initialization
    void Start()
    {
        //这里使用的是带障碍点和寻路点的构造方法
        navTree = new NavTree(navObject.m_obstacleWall.obstacle_point, navObject.m_Nav_Point.m_navPoint);
        mousePoint = GameObject.CreatePrimitive(PrimitiveType.Sphere);
        target = transform.position;

    }

    void Update()
    {
        //与目标距离小于0.5时停止寻路
        if (Vector3.Distance(target, transform.position) > 0.5f)
        {
            //更新寻路树
            navTree.UpdateNavTree(transform.position);
            controller.Move((navTree.nextPoint-transform.position).normalized*Time.deltaTime*5);

        }

        //点击鼠标左键开始寻路
        if (Input.GetMouseButtonDown(0))
        {
            Vector3 _target = GetTargetPoint();
            if (Tools.PolygonIsContainPoint(_target, navObject.m_obstacleWall.obstacle_point)) 
            {
               //print("移动");
                target = _target;
                mousePoint.transform.position = target;
                //设置新的目标
                navTree.SetTargetNode(target);

            }else{
                print("无法移动到该点!");
            }
        }
    }

    //获取鼠标点击位置
    public Vector3 GetTargetPoint() {

        Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
        RaycastHit hit;
        Physics.Raycast(ray, out hit);
        return hit.point;
    }

}

在AutoNav脚本中使用了unity中判断一个点是否在多边形范围内中的PolygonIsContainPoint方法来判断用户是否点击的正确位置。
下面来一张最终效果图

20160818193250

演示案例下载:链接:https://pan.baidu.com/s/1i43q4Hf 密码:z0ag

(2)

本文由 树莓屋 作者:Berry贝锐 发表,转载请注明来源!

关键词:,

热评文章

发表评论