🌲树

在看这篇之前，应该已经接触在游戏开发中接触了不少树形结构。

概述

在Unity里应用最广泛的相关树形结构应该就是Transform了（Transform有父节点有子节点），如果接触过UIToolkit，里面的VisualElement也是树形结构，运用树形结构可以方便进行布局管理和事件传递。

Unity的性能优化也有用到树，常见的如四叉树（Quadtree）和八叉树（Octree）等数据结构，它们通过树型结构将空间划分为更小的区块，用于快速的碰撞检测、视锥体剔除（Frustum Culling）等操作。

除此之外，在游戏开发中也会应用到很多自定义的树形结构，比如在地牢生成中，可能会将生成结构以树型的结构表示出来。

涉及到树型结构，就或多或少在开发需要对树进行遍历、查找，而此框架提供了一套通用的查询以及遍历树型结构的工具。

通过接口调用

一种方便的使用方式是将需要操作的树的节点实现接口ITreeNode<T>即可，这样就能方便地使用这些框架内提供的工具函数。

比如，我在规划地牢生成算法，想写一个像以撒的结合/元气骑士/挺进地牢那样的地牢生成，地牢的房间是以树状的形式组织的，那么房间的生成信息显然就是一个树的节点，想要借助框架内的工具函数，需要实现ITreeNode<T>接口，如下：

public class RoomGenerationInfo : ITreeNode<RoomGenerationInfo>
{
    // 父房间生成信息
    // The Room Generation Info of the parent room.
    public RoomGenerationInfo parentRoomInfo { get; init; }

    // 房间的入口信息，表示父房间的方向
    // The entry information of the room, which represents the direction of the parent room.
    public FourTypesDirection2D enterDirection { get; init; }

    // 不同房间的出口对应的相邻房间生成信息
    // FourTypesDirection2D是框架内自带的枚举类型，表示2D空间的四个方向：上、下、左、右
    // The Room Generation Info of the adjacent room corresponding to the exit of different rooms.
    // FourTypesDirection2D is an enumeration type built into the framework,
    // representing the four directions of 2D space: up, down, left, and right.
    private readonly Dictionary<FourTypesDirection2D, RoomGenerationInfo> _childrenRoomDict = new();

    // 这里可能会有一些生成数据
    // 比如坐标、房间深度啥的
    // The data for generating the room, such as coordinates and room depth.

    // 构造函数，初始化入口方向和父房间生成信息
    // The constructor initializes the entry direction and parent room generation information.
    public RoomGenerationInfo(FourTypesDirection2D enterDirection, RoomGenerationInfo parentRoomInfo)
    {
        this.enterDirection = enterDirection;
        this.parentRoomInfo = parentRoomInfo;

        parentRoomInfo.AddChildRoom(enterDirection.Reversed(), this);
    }

    // 构造函数，这样构造表示是根房间，或者说是第一个房间
    // The constructor, which is used to construct the root room or the first room,
    // initializes the entry direction and parent room generation information.
    public RoomGenerationInfo() : this(FourTypesDirection2D.None, null)
    {
    }

    // 添加子房间，这里的子房间是指相邻的房间，出口方向不能与入口方向相同
    // 在生成地牢房间结构时，使用此函数来添加子房间
    // The function is used to add a child room, which is adjacent to the current room,
    // and the exit direction cannot be the same as the entry direction.
    // This function is used to add child rooms when generating the dungeon room structure.
    private void AddChildRoom(FourTypesDirection2D direction, RoomGenerationInfo roomGenerationInfo)
    {
        if (direction == enterDirection)
            // 不能在入口方向添加子房间
            throw new Exception("Cannot add a child room in the same direction as the entry direction.");

        _childrenRoomDict[direction] = roomGenerationInfo;
    }

    #region ITreeNode

    RoomGenerationInfo IParentProvider<RoomGenerationInfo>.GetParent() =>
        parentRoomInfo;

    [ShowInInspector]
    IEnumerable<RoomGenerationInfo> IChildrenProvider<RoomGenerationInfo>.GetChildren() =>
        _childrenRoomDict.Values;

    #endregion
}

实现了ITreeNode<T>接口后，就可以用框架里的工具函数了，还是以这个RoomGenerationInfo为例：

public class RoomGeneratorTest : MonoBehaviour
{
    private void Start()
    {
        var info1 = new RoomGenerationInfo();
        var info2 = new RoomGenerationInfo(FourTypesDirection2D.Down, info1);
        var info3 = new RoomGenerationInfo(FourTypesDirection2D.Left, info1);
        var info4 = new RoomGenerationInfo(FourTypesDirection2D.Right, info2);

        // 获取根房间，这里root就是info1
        var root = info4.GetRoot();

        // 判断info4是否是info2的子节点，这里返回true
        var hasParentInfo2 = info4.HasParent(info2, false);

        foreach (var info in info4.TraverseToRoot(true))
        {
            // 遍历info4到根节点的路径，这里会依次遍历info4、info2、info1
            // TraverseToRoot方法的参数表示是否包含自身节点
            // 如果为false，则不包含自身节点，只会遍历info2、info1
        }

        foreach (var info in info1.PreorderTraverse(true))
        {
            // 前序遍历info1的子树，这里会依次遍历info1、info2、info4、info3
            // PreorderTraverse方法的参数表示是否包含自身节点，与TraverseToRoot方法类似
        }

        foreach (var info in info1.PostorderTraverse(true))
        {
            // 后序遍历info1的子树，这里会依次遍历info4、info2、info3、info1
            // PostorderTraverse方法的参数表示是否包含自身节点，与TraverseToRoot方法类似
        }

        foreach (var info in info1.LevelOrderTraverse(true))
        {
            // 层序遍历info1的子树，这里会依次遍历info1、info2、info3、info4
            // LevelOrderTraverse方法的参数表示是否包含自身节点，与TraverseToRoot方法类似
        }

        // 获取info1的所有子节点，这里会返回info2、info3、info4
        // 如果想要包含info1，可以将参数设为true
        List<RoomGenerationInfo> allChildren = info1.PreorderTraverse(false).ToList();

        // 获取info1的所有叶子节点，这里会返回info3、info4
        List<RoomGenerationInfo> allLeaves = info1.GetAllLeaves(false).ToList();

        // 判断info4是否是info1的子节点，这里返回true
        var hasChildInfo4 = info1.HasChild(info4, false);


        transform.GetComponentInChildren<SpriteRenderer>();

        List<Transform> allParents = transform.TraverseToRoot(true, t => t.parent).ToList();
    }
}

常用的用法已经列在上面，全部的函数请参考框架里的TreeUtility.cs代码文件。

通用方法调用

上面的通过接口调用有一个问题，如果是Unity里已有的东西没法扩展接口该如何使用这些工具函数？比如Transform、VisualElement等等。

比如如何实现获取一个transform的所有父节点（包括自身）？可以给通过TraverseToRoot传入获取父节点的Lambda表达式来实现：

List<Transform> allParents = transform.TraverseToRoot(true, t => t.parent).ToList();

其他工具函数也有类似的使用方法。

这里再列举一个实用的例子，比如从某一个二维坐标(Vector2Int类型)开始向外进行优先广度搜索(BFS)：

//起始坐标
var startPoint = Vector2Int.zero;
//最大搜索次数，防止死循环
int maxSearchCount = 100;
//这里GetFourDirectionsNearPoints是框架内自带的函数，
//用来获取一个Vector2Int坐标的上下左右四个方向相邻坐标，
//比如给这个函数传入(1,1)，会依次返回(1,2)、(1,0)、(0,1)、(2,1)
foreach (var point in startPoint.LevelOrderTraverse(true,
             point => point.GetFourDirectionsNearPoints()))
{
    Debug.Log(point);

    maxSearchCount--;
    if (maxSearchCount <= 0) break;
}