四叉树

四叉树Wiki

四叉树是一种树状数据结构，在每一个节点上会有四个子区块。四叉树常应用于二维空间资料的分析与分类。 它将资料区分成为四个象限。资料范围可以是方形或矩形或其他任意形状。这种数据结构是由 拉斐尔·芬科尔(Raphael Finkel) 与 J. L. Bentley 在1974年发展出来 。 类似的资料分割方法也称为 Q-tree。 所有的四叉树法有共同之特点:

1. 可分解成为各自的区块
2. 每个区块都有节点容量。当节点达到最大容量时，节点分裂
3. 树状数据结构依造四叉树法加以区分

根据理论在2D游戏中实际优化到的运用，在几百个单位中搜查，屏幕中的物体代码如下

只要点在区域内就可以插入

using System;
using System.Collections.Generic;

public class TreeRect
{
    public float X { get; private set; }
    public float Y { get; private set; }
    public float W { get; private set; }
    public float H { get; private set; }
    public float HalfW { get; private set; }
    public float HalfH { get; private set; }
    public float XL { get; private set; }
    public float XR{ get; private set; }

    public float YT { get; private set; }
    public float YB { get; private set; }

    /// <summary>
    /// 点
    /// </summary>
    /// <param name="x"></param>
    /// <param name="y"></param>
    public TreeRect(float x, float y)
    {
        SetRect(x, y, 0, 0);
    }
    
    /// <summary>
    /// 四边形
    /// </summary>
    /// <param name="x"></param>
    /// <param name="y"></param>
    /// <param name="w"></param>
    /// <param name="h"></param>
    public TreeRect(float x, float y, float w, float h)
    {
        SetRect(x, y, w, h);
    }
    
    public void SetRect(float x, float y, float w, float h)
    {
        X = x;
        Y = y;
        W = w;
        H = h;

        HalfW = W * 0.5f;
        HalfH = H * 0.5f;

        XL = X - HalfW;
        XR = X + HalfW;
        YB = Y - HalfH;
        YT = Y + HalfH;
    }

    public bool Intersect(TreeRect other)
    {
        return (!(XR < other.XL || XL > other.XR)) && (!(YT < other.YB || YB > other.YT));
    }

    public bool IsCenterIn(TreeRect other)
    {
        return other.X <= XR && other.X >= XL && other.Y <= YT && other.Y >= YB;
    }

    public bool IsIn(TreeRect other)
    {
        return XR <= other.XR  && XL >= other.XL && YT <= other.YT && YB >= other.YB;
    }
    
    
    public override string ToString()
    {
        return $"({X},{Y},{W},{H})";
    }

    public static TreeRect operator *(TreeRect rhs,float lhs)
    {
        rhs.SetRect(rhs.X * lhs, rhs.Y * lhs, rhs.W * lhs,  rhs.H * lhs);
        return rhs;
    }
}


public class TreeObject
{
    /// <summary>
    /// 信息
    /// </summary>
    public TreeRect TreeRect;
    /// <summary>
    /// 属于哪个节点
    /// </summary>
    public MapQuadTree Node ;
    public int Id;
}

public class MapQuadTree
{
    public MapQuadTree Root { get; } //根节点
    public int MaxCount { get; private set; } = 5;
    public int MaxDeep { get; private set; } = 4;
    public int TreeDeep { get; }
    
    public List<MapQuadTree> Childs { get; private set; } 
    public MapQuadTree Parent { get; }

    /// <summary>
    /// </summary>
    public readonly List<TreeObject> TreePointObjs = new List<TreeObject>();

    // public readonly List<TreeObject> BoundTreeObjs = new List<TreeObject>();
    public TreeRect Rect { get; }
    public bool IsLeafNode => Childs == null || Childs.Count == 0;
    public bool IsEmptyLeafNode => TreePointObjs.Count == 0 && IsLeafNode ;

    public MapQuadTree(TreeRect rect)
    {
        Rect = rect;
        TreeDeep = 0;
        Root = this;
    }

    private MapQuadTree(TreeRect rect, int treeDeep, MapQuadTree parent) : this(rect)
    {
        TreeDeep = treeDeep + 1;
        this.Parent = parent;
        Root = parent.Root;
    }

    public void Insert(TreeObject treeObj)
    {
        if (!IsInTreeRect(treeObj))
        {
            return;
        }

        treeObj.Node = this;
        if (Childs == null)
        {
            TreePointObjs.Add(treeObj);
            if (TreePointObjs.Count > MaxCount)
            {
                SliceTree();
            }
        }
        else
        {
            for (int i = 0; i < Childs.Count; i++)
            {
                Childs[i].Insert(treeObj);
            }
        }
    }

    private void SliceTree()
    {
        if (TreeDeep >= MaxDeep)
        {
            return;
        }

        // 四分 可根据情况 调整
        // lb, lt, rt, rb  目前与unity recttranform 的 4个 corner 保持一致的分布顺序
        Childs = new List<MapQuadTree>
        {
            new MapQuadTree(new TreeRect(Rect.X - Rect.HalfW * 0.5f, Rect.Y - Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH), TreeDeep, this),
            new MapQuadTree(new TreeRect(Rect.X - Rect.HalfW * 0.5f, Rect.Y + Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH), TreeDeep, this),
            new MapQuadTree(new TreeRect(Rect.X + Rect.HalfW * 0.5f, Rect.Y + Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH), TreeDeep, this),
            new MapQuadTree(new TreeRect(Rect.X + Rect.HalfW * 0.5f, Rect.Y - Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH), TreeDeep, this)
        };

        for (int i = 0; i < TreePointObjs.Count; i++)
        {
            for (int j = 0; j < Childs.Count; j++)
            {
                Childs[j].Insert(TreePointObjs[i]);
            }
        }

        TreePointObjs.Clear();
    }


    public bool Intersect(TreeRect other)
    {
        return Rect.Intersect(other);
    }

    private bool IsInTreeRect(TreeObject treeObj)
    {
        return Rect.IsCenterIn(treeObj.TreeRect);
    }

    public void ClearEmptyNode()
    {
        List<MapQuadTree> emptyLeafNodes = new List<MapQuadTree>();
        ForEachEmptyLeafNode(Root, (t) =>
        {
            emptyLeafNodes.Add(t);
        });
        while (emptyLeafNodes.Count > 0)
        {
            for (int i = 0; i < emptyLeafNodes.Count; i++)
            {
                emptyLeafNodes[i].Parent.RemoveChildNode(emptyLeafNodes[i]);
            }
            emptyLeafNodes.Clear();
            ForEachEmptyLeafNode(Root, (t) =>
            {
                emptyLeafNodes.Add(t);
            });
        }
    }

    private void ForEachEmptyLeafNode(MapQuadTree node, Action<MapQuadTree> treeAction)
    {
        if (node.IsEmptyLeafNode)
        {
            treeAction?.Invoke(node);
            return;
        }

        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachEmptyLeafNode(node.Childs[i],treeAction);
            }
        }
    }
    
    private void ForEachLeafNode(MapQuadTree node, Action<MapQuadTree> treeAction)
    {
        if (node.IsLeafNode)
        {
            treeAction?.Invoke(node);
            return;
        }

        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachLeafNode(node.Childs[i],treeAction);
            }
        }
    }
    
    private void RemoveChildNode(MapQuadTree node)
    {
        if (Childs!=null)
        {
            Childs.Remove(node);
        }
    }
    
    public void ForEach(Action<MapQuadTree> each)
    {
        ForEach(Root, each);
    }

    public void ForEachInRect(TreeRect rect, Action<MapQuadTree> treeAction)
    {
        ForEachAreaTree(Root, rect, treeAction);
    }


    private void ForEachAreaTree(MapQuadTree node, TreeRect rect, Action<MapQuadTree> treeAction)
    {
        if (!node.Rect.Intersect(rect))
        {
            return;
        }

        if (node.IsLeafNode)
        {
            treeAction?.Invoke(node);
            return;
        }

        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachAreaTree(node.Childs[i], rect, treeAction);
            }
        }
    }

    public void ForEachInRect(TreeRect rect, Action<TreeObject> treeAction)
    {
        ForEachAreaTree(Root, rect, treeAction);
    }

    private void ForEachAreaTree(MapQuadTree node, TreeRect rect, Action<TreeObject> treeAction)
    {
        if (!node.Rect.Intersect(rect))
        {
            return;
        }

        if (node.IsLeafNode)
        {
            foreach (var treeObject in node.TreePointObjs)
            {
                treeAction?.Invoke(treeObject);
            }

            return;
        }

        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachAreaTree(node.Childs[i], rect, treeAction);
            }
        }
    }

    private void ForEach(MapQuadTree node, Action<MapQuadTree> each)
    {
        if (node == null)
        {
            return;
        }

        ForEachNodeValues(node, each);
        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachNodeValues(node.Childs[i], each);
                ForEach(node.Childs[i], each);
            }
        }
    }

    private void ForEachNodeValues(MapQuadTree node, Action<MapQuadTree> each)
    {
        each?.Invoke(node);
    }

    public override string ToString()
    {
        return $"Deep :{TreeDeep} : {Rect.ToString()} ,+ {TreePointObjs.Count} ";
    }
}

只要点和边框必须在区域内就可以插入

using System;
using System.Collections.Generic;


public class BoundTreeObject
{
    public TreeRect TreeRect;
    public MapQuadBoundTree Node;
    public int Id;
}

public class MapQuadBoundTree
{
    public MapQuadBoundTree Root { get; } //根节点
    public int MaxCount { get; private set; } = 5;
    public int MaxDeep { get; private set; } = 5;
    public int TreeDeep { get; }
    public List<MapQuadBoundTree> Childs { get; private set; }
    public MapQuadBoundTree Parent { get; }
    private TreeRect[] _treeChildRects = new TreeRect[4];
    public readonly List<BoundTreeObject> TreePointObjs = new List<BoundTreeObject>();

    public readonly List<BoundTreeObject> BoundTreeObjs = new List<BoundTreeObject>();
    public TreeRect Rect { get; }
    public bool IsLeafNode => Childs == null || Childs.Count == 0;
    public bool IsEmptyLeafNode => BoundTreeObjs.Count == 0 && TreePointObjs.Count == 0 && IsLeafNode;

    public MapQuadBoundTree(TreeRect rect)
    {
        Rect = rect;
        TreeDeep = 0;
        Root = this;
        _treeChildRects[0] =
            new TreeRect(Rect.X - Rect.HalfW * 0.5f, Rect.Y - Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH);
        _treeChildRects[1] =
            new TreeRect(Rect.X - Rect.HalfW * 0.5f, Rect.Y + Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH);
        _treeChildRects[2] =
            new TreeRect(Rect.X + Rect.HalfW * 0.5f, Rect.Y + Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH);
        _treeChildRects[3] =
            new TreeRect(Rect.X + Rect.HalfW * 0.5f, Rect.Y - Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH);
    }

    private MapQuadBoundTree(TreeRect rect, int treeDeep, MapQuadBoundTree parent) : this(rect)
    {
        TreeDeep = treeDeep + 1;
        this.Parent = parent;
        Root = parent.Root;
    }

    public void Insert(BoundTreeObject treeObj)
    {
        if (!IsInTreeRect(treeObj))
        {
            return;
        }

        treeObj.Node = this;
        if (IsAllInsert(treeObj))
        {
            BoundTreeObjs.Add(treeObj);
            return;
        }

        if (Childs == null)
        {
            TreePointObjs.Add(treeObj);
            if (TreePointObjs.Count > MaxCount)
            {
                SliceTree();
            }
        }
        else
        {
            for (int i = 0; i < Childs.Count; i++)
            {
                Childs[i].Insert(treeObj);
            }
        }
    }

    private bool IsAllInsert(BoundTreeObject treeObj)
    {
        int count = 0;
        for (int i = 0; i < _treeChildRects.Length; i++)
        {
            if (_treeChildRects[i].Intersect(treeObj.TreeRect))
            {
                if (count > 0)
                {
                    return true;
                }

                count++;
            }
        }

        return false;
    }

    private void SliceTree()
    {
        if (TreeDeep >= MaxDeep)
        {
            return;
        }

        // lb, lt, rt, rb  目前与unity recttranform 的 4个 corner 保持一致的分布顺序
        Childs = new List<MapQuadBoundTree>
        {
            new MapQuadBoundTree(
                new TreeRect(Rect.X - Rect.HalfW * 0.5f, Rect.Y - Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH), TreeDeep,
                this),
            new MapQuadBoundTree(
                new TreeRect(Rect.X - Rect.HalfW * 0.5f, Rect.Y + Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH), TreeDeep,
                this),
            new MapQuadBoundTree(
                new TreeRect(Rect.X + Rect.HalfW * 0.5f, Rect.Y + Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH), TreeDeep,
                this),
            new MapQuadBoundTree(
                new TreeRect(Rect.X + Rect.HalfW * 0.5f, Rect.Y - Rect.HalfH * 0.5f, Rect.HalfW, Rect.HalfH), TreeDeep,
                this)
        };

        for (int i = 0; i < TreePointObjs.Count; i++)
        {
            for (int j = 0; j < Childs.Count; j++)
            {
                Childs[j].Insert(TreePointObjs[i]);
            }
        }

        TreePointObjs.Clear();
    }


    public bool Intersect(TreeRect other)
    {
        return Rect.Intersect(other);
    }

    private bool IsInTreeRect(BoundTreeObject treeObj)
    {
        return Rect.IsCenterIn(treeObj.TreeRect);
    }

    public void ClearEmptyNode()
    {
        // TODO  清除空节点 只需从叶节点删除
        List<MapQuadBoundTree> emptyLeafNodes = new List<MapQuadBoundTree>();
        ForEachEmptyLeafNode(Root, (t) => { emptyLeafNodes.Add(t); });
        while (emptyLeafNodes.Count > 0)
        {
            for (int i = 0; i < emptyLeafNodes.Count; i++)
            {
                emptyLeafNodes[i].Parent.RemoveChildNode(emptyLeafNodes[i]);
            }

            emptyLeafNodes.Clear();
            ForEachEmptyLeafNode(Root, (t) => { emptyLeafNodes.Add(t); });
        }
    }

    private void ForEachEmptyLeafNode(MapQuadBoundTree node, Action<MapQuadBoundTree> treeAction)
    {
        if (node.IsEmptyLeafNode)
        {
            treeAction?.Invoke(node);
            return;
        }

        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachEmptyLeafNode(node.Childs[i], treeAction);
            }
        }
    }

    private void RemoveChildNode(MapQuadBoundTree node)
    {
        if (Childs != null)
        {
            Childs.Remove(node);
        }
    }


    public void ForEach(Action<MapQuadBoundTree> each)
    {
        ForEach(Root, each);
    }

    public void ForEachInRect(TreeRect rect, Action<MapQuadBoundTree> treeAction)
    {
        ForEachAreaTree(Root, rect, treeAction);
    }


    private void ForEachAreaTree(MapQuadBoundTree node, TreeRect rect, Action<MapQuadBoundTree> treeAction)
    {
        if (!node.Rect.Intersect(rect))
        {
            return;
        }

        if (node.IsLeafNode)
        {
            treeAction?.Invoke(node);
            return;
        }

        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachAreaTree(node.Childs[i], rect, treeAction);
            }
        }
    }

    public void ForEachInRect(TreeRect rect, Action<BoundTreeObject> treeAction)
    {
        ForEachAreaTree(Root, rect, treeAction);
    }

    private void ForEachAreaTree(MapQuadBoundTree node, TreeRect rect, Action<BoundTreeObject> treeAction)
    {
        if (!node.Rect.Intersect(rect))
        {
            return;
        }

        foreach (var boundTreeObj in node.BoundTreeObjs)
        {
            if (boundTreeObj.TreeRect.Intersect(rect))
            {
                treeAction?.Invoke(boundTreeObj);
            }
        }

        if (node.IsLeafNode)
        {
            foreach (var boundTreeObj in node.TreePointObjs)
            {
                if (boundTreeObj.TreeRect.Intersect(rect))
                {
                    treeAction?.Invoke(boundTreeObj);
                }
            }

            return;
        }

        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachAreaTree(node.Childs[i], rect, treeAction);
            }
        }
    }

    private void ForEach(MapQuadBoundTree node, Action<MapQuadBoundTree> each)
    {
        if (node == null)
        {
            return;
        }

        ForEachNodeValues(node, each);
        if (node.Childs != null)
        {
            for (int i = 0; i < node.Childs.Count; i++)
            {
                ForEachNodeValues(node.Childs[i], each);
                ForEach(node.Childs[i], each);
            }
        }
    }

    private void ForEachNodeValues(MapQuadBoundTree node, Action<MapQuadBoundTree> each)
    {
        each?.Invoke(node);
    }

    public override string ToString()
    {
        return $"Deep :{TreeDeep} : {Rect.ToString()} ,+ {TreePointObjs.Count} ";
    }
}