深度优先及广度优先在Unity中的应用

说明:

简单总结一下深度优先算法和广度优先算法在Unity中最直观和最常见的使用。这里我所举的例子是应用到Unity中3D 人物的所有骨骼关键的遍历，推广开就是可以对所有物体的层级关系进行简单的遍历。。。

数据结构中的树的遍历在Unity中最直观的表现就是对某物体的所有子物体的遍历关系。

如下所示就是对Unity所有子物体层级的转换出的数据结构（树）

深度优先遍历：

深度优先遍历是按照树（图）的深度遍历的一种遍历算法。主要是基于深度优先，既是从某一节点V作为起始节点开始进行遍历，当V的的某一边里所有都遍历过后，回溯到起始节点V，然后继续对另一条边进行遍历，直至所有节点被遍历完成为止。

如上图所示的树，深度优先的遍历方式为：

1. A作为Root结点，第一个被访问，然后依次访问B、E、K，当这条路走完后，接着访问L，然后访问F，这样就代表第一条边被访问完成；
2. 然后回溯到A，依次访问C、G
3. 最后在回溯到A，依次访问D、H、M、I、J

在Unity中深度遍历所有子物体如下所示：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 深度优先
/// </summary>
public class DepthFirst : MonoBehaviour
{
    //用于存储所遍历到的物体
    List<Transform> DepthFirstList = new List<Transform>();
    
    void Start()
    {
        DepthFirst_0(transform);
        //打印序列
        foreach (var item in DepthFirstList)
        {
            Debug.Log(item);
        }
    }

    void DepthFirst_0(Transform tran)
    {
        foreach (Transform item in tran)
        {
            DepthFirstList.Add(item);
            //判断是否存在子物体
            if (item.childCount != 0)
            {
                DepthFirst_0(item);
            }
        }
    }
}

打印结果如下所示：

广度优先遍历

广度优先遍历是按照树（图）的广度遍历的一种遍历算法（又称为层次遍历）。主要是基于广度优先，既是某一节点V作为起始节点开始进行遍历，沿着树（图）的层次进行依次遍历，当第N层被遍历完成后，进行第N+1层遍历，当所有节点都比访问后，遍历完成。

如上图所示的树，广度优先的遍历方式为：

1. A作为Root结点，作为第一层被访问，当第一层访问完成，切到第二层
2. 然后依次访问第二层：B、C、D，第二层访问完成
3. 然后依次访问第三层：E、F、G、H、I、J，第三层访问完成
4. 然后依次访问第四层：K、L、M
5. 没有第4+1层，遍历完成

在Unity中广度遍历所有子物体如下所示：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 获取所有关键
/// </summary>
public class BreathFirst : MonoBehaviour
{
    List<Transform> BreadthFirstList = new List<Transform>();//层次遍历所得到的List

    /// <summary>
    /// 首先把物体的第一层子物体放入一个List，便于之后使用
    /// </summary>
    void Start()
    {
        List<Transform> joinsList = new List<Transform>();
        foreach (Transform itemJoins in transform)
        {
            joinsList.Add(itemJoins);
        }
        BreadthFirst_1(joinsList);

        foreach (var item in BreadthFirstList)
        {
            Debug.Log(item);
        }
    }

    /// <summary>
    /// 递归遍历每一层
    /// </summary>
    /// <param name="joins"></param>
    void BreadthFirst_1(List<Transform> joins)
    {
        List<Transform> joinsChildListss = new List<Transform>();
        foreach (Transform item in joins)
        {
            BreadthFirstList.Add(item);//将每一层依次放入列表中
            if (item.childCount != 0)//判断每一次的序列项是否存在子物体，存在就将所有子物体放入一个新的List
            {
                foreach (Transform itemss in item)
                {
                    joinsChildListss.Add(itemss);
                }
            }
        }
        if (joinsChildListss != null && joinsChildListss.Count != 0)//判断是否是最后一层
            BreadthFirst_1(joinsChildListss);
    }
}

打印结果如下所示：

深度优先算法结合广度优先算法获取物体所有节点关系

深度优先算法是对物体的深度上进行的遍历，广度优先算法是对物体广度上的遍历，如果当我们想要得到物体的层级关系（如：文件件的所有层级关系，3D 人物的骨骼关键关系等）时，我们可以将深度优先结合广度优先即可得到整个层级关系——通过深度优先遍历获取得到每个节点的深度信息，通过广度优先遍历获取到每个节点的广度信息。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 获取所有关键
/// </summary>
public class ListOfJoints : MonoBehaviour
{
    public Transform HumModel;
    int numCount = 0;
    List<Transform> BreadthFirstList = new List<Transform>();
    Dictionary<Transform, int> BreathFirstDic = new Dictionary<Transform, int>();
    List<Transform> DepthFirstList = new List<Transform>();
    IEnumerator Start()
    {
        yield return new WaitForEndOfFrame();
        DepthFirst_0(HumModel);
        BreadthFirst_0(HumModel);
        yield return new WaitForEndOfFrame();
        foreach (var item in DepthFirstList)
        {
            if (BreathFirstDic.ContainsKey(item))
            {
                string str = "";
                for (int i = 0; i < BreathFirstDic[item]; i++)
                {
                    str += "           ";
                }
                Debug.Log(str + item);
            }
        }
    }
    void BreadthFirst_0(Transform tran)
    {
        List<Transform> joinsList = new List<Transform>();
        foreach (Transform itemJoins in HumModel)
        {
            joinsList.Add(itemJoins);
        }
        BreadthFirst_1(joinsList);
    }
    void BreadthFirst_1(List<Transform> joins)
    {
        numCount++;//层数
        List<Transform> joinsChildListss = new List<Transform>();
        foreach (Transform item in joins)//打印子物体
        {
            BreadthFirstList.Add(item);
            BreathFirstDic.Add(item, numCount);
            if (item.childCount != 0)
            {
                foreach (Transform itemss in item)
                {
                    joinsChildListss.Add(itemss);
                }
            }
        }
        if (joinsChildListss != null && joinsChildListss.Count != 0)
            BreadthFirst_1(joinsChildListss);
    }
    void DepthFirst_0(Transform tran)
    {
        foreach (Transform item in tran)
        {
            DepthFirstList.Add(item);
            if (item.childCount != 0)
            {
                DepthFirst_0(item);
            }
        }
    }


}