Wrk

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class QuadTree : MonoBehaviour
{

    public int SubMaxCount = 2;


    public bool DoListUpdate = true;
    public bool DoDebugDraw = true;


    private GameObject BoundingBoxTop;

    private Vector3 BoundingBoxPosition;
    private Vector3 BoudningBoxScale;
    private List<Transform> BBList = new List<Transform>();
    private List<GameObject> BBObjList = new List<GameObject>();
    private List<float[]> BBShowList = new List<float[]>();

    Vector3 ZeroYPosition = Vector3.zero;
    Vector3 ZeroYScale = Vector3.zero;

    private float[] StartBoundingBox = new float[4];
    private float BBX;
    private float BBX_;
    //private float BBY;
    //private float BBY_;
    private float BBZ;
    private float BBZ_;
    //private ConstructTree StartTree = new ConstructTree();

    class MakeQuadTree
    {

        /*
        public MakeQuadTree(float[] BoundingBoxNew, List<Thing> ThingListNew)
        {

        }

        */
        public List<Thing> ThingList = new List<Thing>();
        public void InsertThing(Thing NewThing)
        {
            ThingList.Add(NewThing);
        }
        public void ConstructTree(float[] BoundingBox, List<float[]> BBShowList)
        {

            //
            List<QuadTreeObject> SaveAll = new List<QuadTreeObject>();

            QuadTreeObject newSub = new QuadTreeObject(BoundingBox);
            newSub.DoSub();
            {
                //newSub.ShowSub(BBShowList);// show debug bounds

                BBShowList.Add(newSub.BoundingBox);// Draw top level bounding box

                //return SaveAll;
            }
        }
    }

    class TreeLists
    {
        public List<QuadTreeObject> SaveAll = new List<QuadTreeObject>();
        public List<QuadTreeObject> CurrentSet = new List<QuadTreeObject>();
        public List<QuadTreeObject> LastSet = new List<QuadTreeObject>();
        public List<QuadTreeObject> SetSave = new List<QuadTreeObject>();
        public List<Thing> SearchList = new List<Thing>();
        public List<QuadTreeObject> ShowList = new List<QuadTreeObject>();

        //public List<float[]> test = new List<float[]>();
    }

    class QuadTreeObject//subBB
    {
        // Instance constructo
        public QuadTreeObject(float[] BoundingBoxNew)
        {
            BoundingBox = BoundingBoxNew;
            BoundingBoxCenter.x = (BoundingBoxList[0] + BoundingBoxList[1]) / 2;
            BoundingBoxCenter.z = (BoundingBoxList[2] + BoundingBoxList[3]) / 2;
        }

        public float[] BoundingBox {get; set;}
        public List<QuadTreeObject> BoundingBoxChildren = new List<QuadTreeObject>();
        public List<Thing> BoundingBoxSearchObjects = new List<Thing>();
        public Vector3 BoundingBoxCenter = new Vector3();
        private float[] BoundingBoxList = new float[4];


        public void DoSub()
        {
            List<QuadTreeObject> NewBoundingBoxList = new List<QuadTreeObject>();
            List<Thing> SearchList = new List<Thing>();
            List<QuadTreeObject> AddList = new List<QuadTreeObject>();
            float[] bb = this.BoundingBox;
            float[] NewBBNW = new float[4];// North West box
            NewBBNW[2] = bb[2];// North
            NewBBNW[0] = (bb[0] + bb[1]) / 2;// East, NorthWest
            NewBBNW[1] = bb[1];// West
            NewBBNW[3] = (bb[2] + bb[3]) / 2;// South, SouthWest
            QuadTreeObject NWTreeObject = new QuadTreeObject(NewBBNW);
            NewBoundingBoxList.Add(NWTreeObject);
            float[] NewBBNE = new float[4];// North East box
            NewBBNE[2] = bb[2];
            NewBBNE[0] = (bb[0] + bb[1]) / 2;
            NewBBNE[1] = bb[0];
            NewBBNE[3] = (bb[2] + bb[3]) / 2;
            QuadTreeObject NETreeObject = new QuadTreeObject(NewBBNE);
            NewBoundingBoxList.Add(NETreeObject);
            float[] NewBBSW = new float[4];// South West box
            NewBBSW[2] = (bb[2] + bb[3]) / 2;
            NewBBSW[0] = (bb[0] + bb[1]) / 2;
            NewBBSW[1] = bb[1];
            NewBBSW[3] = bb[3];
            QuadTreeObject SWTreeObject = new QuadTreeObject(NewBBSW);
            NewBoundingBoxList.Add(SWTreeObject);
            float[] NewBBSE = new float[4];// South East box
            NewBBSE[2] = (bb[2] + bb[3]) / 2;
            NewBBSE[0] = bb[0];
            NewBBSE[1] = (bb[1] + bb[0]) / 2;
            NewBBSE[3] = bb[3];
            QuadTreeObject SETreeObject = new QuadTreeObject(NewBBSE);
            NewBoundingBoxList.Add(SETreeObject);

            foreach (QuadTreeObject NewBoundingBox in NewBoundingBoxList)
            {

                AddList.Add(NewBoundingBox);

            }
            this.BoundingBoxChildren = AddList;

            //this.BoundingBoxChildren.Add(NWTreeObject);
        }
        public void ShowSub(List<float[]> BBList)
        {

            foreach (QuadTreeObject child in this.BoundingBoxChildren)
            {
                BBList.Add(child.BoundingBox);
            }

        }
    }


    class Thing
    {
        public Thing(GameObject ThingObjectNew)
        {
            Position = ThingObjectNew.transform.position;
            IsFound = false;
            ThingObject = ThingObjectNew;
        }

        public Vector3 Position { get; set; }
        public bool IsFound { get; set; }
        public GameObject ThingObject { get; set; }
    }


    public float[] GetBounds(List<Transform> BBList)
    {
        BBX = -100000f;
        BBX_ = 100000f;
        //BBY = -100000f;
        //BBY_ = 100000f;
        BBZ = -100000f;
        BBZ_ = 100000f;

        foreach (Transform child in BBList)
        {
            if (child.position.x > BBX) // Bounds x+
            {
                BBX = child.position.x;
            }
            if (child.position.x < BBX_) // Bounds x-
            {
                BBX_ = child.position.x;
            }
            /*
            if (child.position.y > BBY) // Bounds y+
            {
                BBY = child.position.y;
            }
            if (child.position.y < BBY_) // Bounds y-
            {
                BBY_ = child.position.y;
            }
            */
            if (child.position.z > BBZ) // Bounds z+
            {
                BBZ = child.position.z;
            }
            if (child.position.z < BBZ_) // Bounds z-
            {
                BBZ_ = child.position.z;
            }
        }

        StartBoundingBox[0] = BBX;
        StartBoundingBox[1] = BBX_;
        StartBoundingBox[2] = BBZ;
        StartBoundingBox[3] = BBZ_;
        //BoundingBoxList[4] = BBY;
        //BoundingBoxList[5] = BBY_;
        //ConvertBoundsToCube();
        return StartBoundingBox;
    }


    void ConvertBoundsToCube()
    {
        BoundingBoxPosition.x = (StartBoundingBox[0] + StartBoundingBox[1]) / 2;
        BoundingBoxPosition.z = (StartBoundingBox[2] + StartBoundingBox[3]) / 2;
        //BoundingBoxPosition.y = (BoundingBoxList[4] + BoundingBoxList[5]) / 2;
        BoudningBoxScale.x = (StartBoundingBox[0] - StartBoundingBox[1]);
        BoudningBoxScale.z = (StartBoundingBox[2] - StartBoundingBox[3]);
        //BoudningBoxScale.y = (BoundingBoxList[4] - BoundingBoxList[5]);
        //return StartBoundingBox;
    }

    void OnDrawGizmos()
    {
        if (DoDebugDraw)
        {
            foreach(float[] bb in BBShowList)
            {
                ZeroYPosition.x = (bb[0] + bb[1])/2;
                ZeroYPosition.z = (bb[2] + bb[3]) / 2;
                ZeroYScale.x = bb[0] - bb[1];
                ZeroYScale.z = bb[2] - bb[3];
                Gizmos.color = Color.red;
                Gizmos.DrawWireCube(ZeroYPosition, ZeroYScale);
                Gizmos.DrawSphere(ZeroYPosition, .1f);
            }
        }
    }
    void UpdadateBBList()
    {
        BBList.Clear();
        foreach (GameObject child in GameObject.FindGameObjectsWithTag("InOctree"))
        {
            BBList.Add(child.transform);
        }
        DoListUpdate = false;
    }
    void Start()
    {
        //TreeLists TreeListsMain = new TreeLists();
        MakeQuadTree QuadTree = new MakeQuadTree();

        foreach (GameObject child in GameObject.FindGameObjectsWithTag("InOctree"))
         {
            Thing NewThing = new Thing(child);
            QuadTree.InsertThing(NewThing);
            //TreeListsMain.SearchList.Add(NewThing);
            //QuadTreeObject test = new QuadTreeObject(child.transform.position);
            //test.BoundingBoxCenter = child.transform.position;
            //BBList.Add(child.transform);
            //BBObjList.Add(child);
        }
        StartBoundingBox = GetBounds(BBList); // starting bounding box
        //StartTree.BuildTree(BoundingBoxList, BBShowList);

    }

    void Update()
    {
        if (DoListUpdate)
        {
            UpdadateBBList();
        }
        StartBoundingBox = GetBounds(BBList);
        BBShowList.Clear();
        //ConstructTree(StartBoundingBox, BBShowList);

        //BBShowList.Add(BoundingBoxList);


    }
}