wrk3

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

public class QuadTree : MonoBehaviour
{

    public int SubdivideMaxCount = 2; // Max objects in cell, then stop subdividing
    public int SubDepthCount = 10; // Max times it will subdivide

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


    private GameObject BoundingBoxTop;
    private ConstructQuadTree QuadTreeMain = new ConstructQuadTree();
    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 ConstructQuadTree
    {

        public List<Thing> ThingList = new List<Thing>();
        float[] StartBoundingBox = new float[4];

        public void ClearThings()
        {
            this.ThingList.Clear();
        }
        public void InsertThing(Thing NewThing)
        {
           ThingList.Add(NewThing);
        }

        public List<QuadTreeObject> CopyQuadList(List<QuadTreeObject> ToCopyList)
        {
            List<QuadTreeObject> CopiedList = new List<QuadTreeObject>();
            foreach (QuadTreeObject ToCopyObj in ToCopyList)
            {
                QuadTreeObject CopiedObj = new QuadTreeObject(ToCopyObj);
                Debug.Log("HERE");
                CopiedList.Add(CopiedObj);
            }
            return CopiedList;
        }

        public void ConstructTree(float[] BBox, List<float[]> BBShowList, int SubDepthInput, int SubDepth, bool DoDebugDraw)
        {

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

            List<QuadTreeObject> SetSave = new List<QuadTreeObject>();
            //List<List<QuadTreeObject>> SetSave = new List<List<QuadTreeObject>>();
            int SubMaxCountAmnt = SubDepthInput;

            QuadTreeObject newSub = new QuadTreeObject(BBox);
            newSub.SubMaxCount = SubMaxCountAmnt;
            newSub.BoundingBoxSearchObjects = this.ThingList;
            newSub.BoundingBoxParentSearchObjects = this.ThingList;
            newSub.DoSave = false;
            //newSub.DoSub();
            //newSub.DrawBounds();
            CurrentSet.Add(newSub);

            int NewSubCount = 1;

            for (int i = 0; i < SubDepth; i++)
            {

                //int CurrentSetLen = CurrentSet.Count;
                //Debug.Log(CurrentSetLen);

                //for (int y = 0; y < CurrentSetLen; y++)
                int Catcher = 1000;
                foreach(QuadTreeObject CurrentObj in CurrentSet)
                {
                    //Debug.Log(Catcher);
                    if(Catcher == 0)
                    {
                        Debug.Log("Broken! Caught!");
                        break;
                    }
                    else{
                        if (CurrentObj.DoSubActive)
                        {
                            CurrentObj.DoSub();
                            CurrentObj.DoSubActive = false;
                            foreach (QuadTreeObject bbChild in CurrentObj.BoundingBoxChildren)
                            {
                                SetSave.Add(bbChild);
                            }
                        }
                        if (DoDebugDraw && CurrentObj.BBActive)
                        {
                            CurrentObj.DrawBounds();
                        }
                    }
                    Catcher--;
                }


                NewSubCount = 0;
                foreach (QuadTreeObject NewFromSet in SetSave)
                {
                    if (NewFromSet.DoSave)
                    {
                        CurrentSet.Add(NewFromSet);
                        //Debug.Log(NewFromSet);
                        NewFromSet.DrawBounds();
                        NewFromSet.DoSave = false;
                        NewSubCount++;
                    }
                }
                //Debug.Log(NewSubCount);
                //SetSave.Clear();

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

                //CurrentSet = SetSave;
                //List<Book> books_2 = books_1.ConvertAll(book => new Book(book.title));
                //CurrentSet.AddRange(SetSave);
                //targetList.AddRange(sourceList);
                //SetSave.CopyTo(CurrentSet);
                /*

                foreach (QuadTreeObject ss in SetSave)
                {
                    CurrentSet.Add(ss);
                }

                //for (int i = 0; i < SubDepth; i++)
                for (int ii = 0; ii < SetSave.Count; ii++)
                {
                    //CurrentSet.Add(SetSave[ii]);
                }
                */



            }

        }
    }



    class QuadTreeObject//subBB
    {

        public QuadTreeObject(QuadTreeObject lastQuad)
        {
            BoundingBox = lastQuad.BoundingBox;
            BoundingBoxSearchObjects = lastQuad.BoundingBoxSearchObjects;
            //BoundingBoxChildren = lastQuad.BoundingBoxChildren;
            BBIsInObjs = lastQuad.BBIsInObjs;
            BoundingBoxCenter = lastQuad.BoundingBoxCenter;
            BoundingBoxList = lastQuad.BoundingBoxList;
            BBActive = lastQuad.BBActive;
            SubMaxCount = lastQuad.SubMaxCount;
            DoSubActive = lastQuad.DoSubActive;
        }

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


        public float[] BoundingBox { get; set; }
        public List<Thing> BoundingBoxSearchObjects = new List<Thing>();//{ get; set; }
        public List<Thing> BoundingBoxParentSearchObjects { get; set; }
        public List<QuadTreeObject> BoundingBoxChildren = new List<QuadTreeObject>();
        public List<Thing> BBIsInObjs = new List<Thing>();
        public Vector3 BoundingBoxCenter = new Vector3();
        private float[] BoundingBoxList = new float[4];
        public bool BBActive = false;
        public bool DoSubActive = true;
        public int SubMaxCount = 0;
        public bool DoSave = true;

        public void DoSub()
        {
            //this.DoSubActive = false;
            //this.BoundingBoxChildren.Clear();
            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);
            //Debug.Log(NWTreeObject.BoundingBoxSearchObjects.Count);
            //NWTreeObject.BoundingBox = NewBBNW;

            NewBoundingBoxList.Add(NWTreeObject);

            //this.BoundingBoxChildren.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);
            //NETreeObject.BoundingBox = NewBBNE;

            NewBoundingBoxList.Add(NETreeObject);

            //this.BoundingBoxChildren.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);
           // SWTreeObject.BoundingBox = NewBBSW;

            NewBoundingBoxList.Add(SWTreeObject);

            //this.BoundingBoxChildren.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);
            //SETreeObject.BoundingBox = NewBBSE;

            NewBoundingBoxList.Add(SETreeObject);

            //this.BoundingBoxChildren.Add(SETreeObject);

            List<QuadTreeObject> addList = new List<QuadTreeObject>();
            foreach (QuadTreeObject NewBoundingBox in NewBoundingBoxList)
            {
                NewBoundingBox.BoundingBoxParentSearchObjects = this.BoundingBoxSearchObjects;
                NewBoundingBox.SubMaxCount = this.SubMaxCount;
                //NewBoundingBox.BoundingBoxSearchObjects = this.BoundingBoxSearchObjects;
                //Debug.Log(this.BoundingBoxSearchObjects.Count);
                //foreach(Thing SearchThing in this.BoundingBoxSearchObjects)
                //{
                //    NewBoundingBox.BoundingBoxSearchObjects.Add(SearchThing);
                //}
                NewBoundingBox.IsIn();

                //NewBoundingBox.DrawBounds();
                //this.BoundingBoxChildren.Add(NewBoundingBox);
                if (NewBoundingBox.BBActive == true)
                {

                    this.BoundingBoxChildren.Add(NewBoundingBox);

                    //NewBoundingBox.BoundingBoxChildren = this.BoundingBoxChildren;
                }
            }
            //this.BoundingBoxChildren = new List<QuadTreeObject>();

        }

        public void IsIn()
        {
            List<Thing> IsInList = new List<Thing>();
            float[] BB = this.BoundingBox;
            bool doAdd = false;

            //this.DrawBounds();

            int ListLen = this.BoundingBoxParentSearchObjects.Count;
            //Debug.Log(ListLen);
            for (int x = 0; x < ListLen; x++)
            {
                Vector3 objPos = this.BoundingBoxParentSearchObjects[x].Position;

                //if (objPos.x < BB[1] || objPos.x > BB[0] || objPos.z < BB[3] || objPos.z > BB[2])
                if (objPos.x <= BB[0] && objPos.x >= BB[1] && objPos.z <= BB[2] && objPos.z >= BB[3])
                {
                    //if (objPos.x <= BB[1] || objPos.x >= BB[0] || objPos.z <= BB[3] || objPos.z >= BB[2])

                    doAdd = true;
                }
                if (doAdd == true)
                {
                    //this.BBIsInObjs.Add(this.BoundingBoxParentSearchObjects[x]);
                    //this.BoundingBoxSearchObjects.Add(this.BoundingBoxParentSearchObjects[x]);
                    this.BoundingBoxSearchObjects.Add(this.BoundingBoxParentSearchObjects[x]);

                    //Debug.Log("ListLen");
                    Debug.Log(ListLen);
                    if (ListLen <= this.SubMaxCount)
                    {
                        this.BBActive = false;

                    }
                    else
                    {
                        this.BBActive = true;
                    }

                }
            }
            this.BoundingBoxSearchObjects = new List<Thing>(IsInList);
            //this.BoundingBoxSearchObjects.Clear();

            /*
            for (int iii = 0; iii < IsInList.Count; iii++)
            {
                //this.BoundingBoxSearchObjects.Add(IsInList[iii]);
            }
            */
        }

        public void ShowSub(List<float[]> BBList)
        {
            BBList.Add(this.BoundingBox);
            /*
            foreach (QuadTreeObject child in this.BoundingBoxChildren)
            {
                BBList.Add(child.BoundingBox);
            }
            */

        }
        public Vector3 ConvertBoundsToCube(float[] BoundsList)
        {
            Vector3 BoxPos = Vector2.zero;
            BoxPos.x = (BoundsList[0] + BoundsList[1]) / 2;
            BoxPos.z = (BoundsList[2] + BoundsList[3]) / 2;
            //BoundingBoxPosition.y = (BoundingBoxList[4] + BoundingBoxList[5]) / 2;
            BoxPos.x = (BoundsList[0] - BoundsList[1]);
            BoxPos.z = (BoundsList[2] - BoundsList[3]);
            //BoudningBoxScale.y = (BoundingBoxList[4] - BoundingBoxList[5]);
            return BoxPos;
        }
        public void DrawBounds()
        {
            float Offset = 0;
            float[] bb = this.BoundingBox;
            Vector3 NorthWLine = new Vector3(bb[1] - Offset, 0, bb[2] + Offset);
            Vector3 NorthELine = new Vector3(bb[0] + Offset, 0, bb[2] + Offset);
            Vector3 SouthELine = new Vector3(bb[0] + Offset, 0, bb[3] - Offset);
            Vector3 SouthWLine = new Vector3(bb[1] - Offset, 0, bb[3] - Offset);
            Debug.DrawLine(NorthWLine, NorthELine, Color.red);// NorthLine
            Debug.DrawLine(NorthELine, SouthELine, Color.green);
            Debug.DrawLine(SouthELine, SouthWLine, Color.blue);
            Debug.DrawLine(SouthWLine, NorthWLine, Color.yellow);
        }


    }

    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 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, .01f);
            }
        }
    }
    void UpdadateBBList()
    {
        BBList.Clear();

        foreach (GameObject child in GameObject.FindGameObjectsWithTag("InOctree"))
        {
            BBList.Add(child.transform);
        }
        DoListUpdate = false;
    }
    void UpdateTreeList()
    {
        QuadTreeMain.ClearThings();
        foreach (GameObject child in GameObject.FindGameObjectsWithTag("InOctree"))
        {
            Thing NewThing = new Thing(child);
            QuadTreeMain.InsertThing(NewThing);
        }
        DoListUpdate = false;

    }
    void Start()
    {
        //TreeLists TreeListsMain = new TreeLists();


        foreach (GameObject child in GameObject.FindGameObjectsWithTag("InOctree"))
         {
            Thing NewThing = new Thing(child);
            QuadTreeMain.InsertThing(NewThing);
            BBObjList.Add(child);
            BBList.Add(child.transform);
            //TreeListsMain.SearchList.Add(NewThing);
            //QuadTreeObject test = new QuadTreeObject(child.transform.position);
            //test.BoundingBoxCenter = child.transform.position;
            //BBList.Add(child.transform);

        }
        StartBoundingBox = GetBounds(BBList); // starting bounding box

        //StartTree.BuildTree(BoundingBoxList, BBShowList);

    }

    void Update()
    {
        if (DoListUpdate)
        {
            UpdadateBBList();
            UpdateTreeList();
        }
        BBShowList.Clear();
        StartBoundingBox = GetBounds(BBList);
        QuadTreeMain.ConstructTree(StartBoundingBox, BBShowList, SubdivideMaxCount, SubDepthCount, DoDebugDraw);

        //ConstructTree(StartBoundingBox, BBShowList);

        //BBShowList.Add(BoundingBoxList);


    }
}