以线性时间绘制非分层整齐树的实践与应用

故事还是要从去年春节说起，当时临近除夕实在闲的蛋疼，随意摩挲着MAC唯一比较舒服的触摸板，突然想起我的行为树乱糟糟的布局，就想着能不能搞个自动布局算法，充分利用空间的同时让行为树更加整洁大方，说干就干

吭哧吭哧3天时间（是的，你没猜错，我猪脑又过载了）终于是写完了一版行为树自动布局工具，当时够用了，于是就没管了

前阵子在给基于行为树的MOBA技能系统：朝花夕拾 · 现代化的动画系统设计与开发开发Playable Debug工具的时候，需求是横向布局对齐，参考了 Reingold-Tilford Algorithm 进行实现

最近我的运行时节点编辑器依旧有自动布局的需求，本来可以直接复用之前写的节点自动布局算法，但由于运行时节点编辑器和NodeGraphProcessor的节点数据结构天差地别，改起来非常折磨，想到后面可能还有什么地方有自动布局的需求，干脆抽离出一个通用的算法库，同时支持 从上到下，从左到右，从右到左，从下到上的树结构自动布局

说起来有4类情况，其实只需要写一个算法，然后对结果进行旋转 + 后处理即可

这次没有再埋头苦干，而是翻阅了大量资料，找到了一个无论是算法理论还是代码示例都很好的文章：[翻译] 树结构自动布局算法，我这里就对着Java版本的实现照葫芦画瓢搞了一版C#的实现，使用起来也非常简单

使用方法

实现INodeForLayoutConvertor

public interface INodeForLayoutConvertor
{
    /// <summary>
    /// 节点间的距离
    /// </summary>
    float SiblingDistance { get; }
    /// <summary>
    /// 自定义的Node实例引用
    /// </summary>
    object PrimRootNode { get; }
    
    /// <summary>
    /// 算法中的Node结构
    /// </summary>
    NodeAutoLayouter.TreeNode LayoutRootNode { get; }
    /// <summary>
    /// 初始化
    /// </summary>
    /// <param name="primRootNode"></param>
    /// <returns></returns>
    INodeForLayoutConvertor Init(object primRootNode);
    
    /// <summary>
    /// 将自定义节点树转换为算法中的节点树
    /// </summary>
    /// <returns></returns>
    NodeAutoLayouter.TreeNode PrimNode2LayoutNode();
    
    /// <summary>
    /// 将算法中的节点树转换为自定义节点树
    /// </summary>
    void LayoutNode2PrimNode();
}

这里以一个常见的从上到下的节点树为例，对于左右布局的节点树，需要将宽高置换，具体代码参考：NewPlayableNodeConvertor.cs

public class RNG_LayoutNodeConvertor : INodeForLayoutConvertor
{
    public float SiblingDistance => 50;
    public float TreeDistance => 80;
    public object PrimRootNode => m_PrimRootNode;
    private object m_PrimRootNode;
    private NodeAutoLayouter.TreeNode m_LayoutRootNode;
    public NodeAutoLayouter.TreeNode LayoutRootNode => m_LayoutRootNode;
    
    public INodeForLayoutConvertor Init(object primRootNode)
    {
        this.m_PrimRootNode = primRootNode;
        return this;
    }
    
    public NodeAutoLayouter.TreeNode PrimNode2LayoutNode()
    {
        NodeView graphNodeViewBase = m_PrimRootNode as NodeView;
        m_LayoutRootNode =
            new NodeAutoLayouter.TreeNode(graphNodeViewBase.View.self.size.x + SiblingDistance,
                graphNodeViewBase.View.self.size.y,
                graphNodeViewBase.View.self.position.y,
                NodeAutoLayouter.CalculateMode.Vertical |
                NodeAutoLayouter.CalculateMode.Positive);
        Convert2LayoutNode(graphNodeViewBase,
            m_LayoutRootNode, graphNodeViewBase.View.self.position.y + graphNodeViewBase.View.self.size.y,
            NodeAutoLayouter.CalculateMode.Vertical |
            NodeAutoLayouter.CalculateMode.Positive);
        return m_LayoutRootNode;
    }
    
    /// <summary>
    /// 上个节点的左下角坐标点.y
    /// </summary>
    /// <param name="rootPrimNode"></param>
    /// <param name="rootLayoutNode"></param>
    /// <param name="lastHeightPoint"></param>
    /// <param name="calculateMode"></param>
    private void Convert2LayoutNode(NodeView rootPrimNode,
        NodeAutoLayouter.TreeNode rootLayoutNode, float lastHeightPoint,
        NodeAutoLayouter.CalculateMode calculateMode)
    {
        if (rootPrimNode.Children != null)
        {
            foreach (var childNode in rootPrimNode.Children)
            {
                NodeAutoLayouter.TreeNode childLayoutNode =
                    new NodeAutoLayouter.TreeNode(childNode.View.self.size.x + SiblingDistance,
                        childNode.View.self.size.y,
                        lastHeightPoint + SiblingDistance, calculateMode);
                rootLayoutNode.AddChild(childLayoutNode);
                Convert2LayoutNode(childNode, childLayoutNode,
                    lastHeightPoint + SiblingDistance + childNode.View.self.size.y,
                    calculateMode);
            }
        }
    }
    
    public void LayoutNode2PrimNode()
    {
        Vector2 calculateRootResult = m_LayoutRootNode.GetPos();
        NodeView root = m_PrimRootNode as NodeView;
        root.BindingContext.NodePos.Value = calculateRootResult;
        Convert2PrimNode(m_PrimRootNode as NodeView, m_LayoutRootNode, root.BindingContext.NodePos.Value);
    }
    
    private void Convert2PrimNode(NodeView rootPrimNode,
        NodeAutoLayouter.TreeNode rootLayoutNode, Vector2 offset)
    {
        if (rootPrimNode.Children != null)
        {
            List<NodeView> children = rootPrimNode.Children.ToList();
            for (int i = 0; i < rootLayoutNode.children.Count; i++)
            {
                Vector2 calculateResult = rootLayoutNode.children[i].GetPos();
                children[i].BindingContext.NodePos.Value = calculateResult;
                Convert2PrimNode(children[i], rootLayoutNode.children[i], offset);
            }
        }
    }
}