using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using Microsoft.Xna.Framework;

using AtriLib3.Interfaces;

​

namespace AtriLib3.Utility

{

    public class QuadTree

    {

        private int _level;

        private List<IWorldObject> _objects;

        private Rectangle _bounds;

        private QuadTree[] nodes;

​

        public QuadTree(int level, Rectangle bounds)

        {

            _level = level;

            _bounds = bounds;

            _objects = new List<IWorldObject>();

            nodes = new QuadTree[4];

        }

​

        /// <summary>

        /// Clear the QuadTree

        /// </summary>

        public void Clear()

        {

            _objects.Clear();

​

            for(int i = 0; i < nodes.Length; i++)

            {

                if(nodes[i] != null)

                {

                    nodes[i].Clear();

                    nodes[i] = null;

                }

            }

        }

​

        /// <summary>

        /// Split the node into 4 subnodes

        /// </summary>

        private void Split()

        {

            int subWidth = _bounds.Width / 2;

            int subHeight = _bounds.Height / 2;

            int x = _bounds.X;

            int y = _bounds.Y;

​

            nodes[0] = new QuadTree(_level + 1, new Rectangle(x + subWidth, y, subWidth, subHeight));

            nodes[1] = new QuadTree(_level + 1, new Rectangle(x, y, subWidth, subHeight));

            nodes[2] = new QuadTree(_level + 1, new Rectangle(x, y + subHeight, subWidth, subHeight));

            nodes[3] = new QuadTree(_level + 1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));

        }

​

        private int GetIndex(Rectangle rect)

        {

            int idx = -1;

            double verticalMidpoint = _bounds.X + (_bounds.Width / 2);

            double horizontalMidpoint = _bounds.Y + (_bounds.Height / 2);

​

            bool topQuadrant = (rect.Y < horizontalMidpoint && rect.Y + rect.Height < horizontalMidpoint);

            bool bottomQuadrant = (rect.Y > horizontalMidpoint);

​

            // Object can fit within the left quadrants

            if(rect.X < verticalMidpoint && rect.X + rect.Width < verticalMidpoint)

            {

                if(topQuadrant)

                {

                    idx = 1;

                }

                else if(bottomQuadrant)

                {

                    idx = 2;

                }

            }

            // Object can fit within the right quadrants

            else if(rect.X > verticalMidpoint)

            {

                if(topQuadrant)

                {

                    idx = 0;

                }

                else if(bottomQuadrant)

                {

                    idx = 3;

                }

            }

​

            return idx;

        }

​

        public List<IWorldObject> GetObjects(Rectangle rect)

        {

            int index = GetIndex(rect);

            List<IWorldObject> _retList = new List<IWorldObject>();

​

            if(index != -1 && nodes[index] != null)

            {

                nodes[index].GetObjects(rect);

            }

​

            for(int i = 0; i < _objects.Count; i++)

            {

                _retList.Add(_objects[i]);

            }

​

            return _retList;

        }

​

        /// <summary>

        /// Add an object to the QuadTree

        /// </summary>

        /// <param name="rect">Object Rectangle</param>

        public void Add(IWorldObject iWorldObj)

        {

            if(nodes[0] != null)

            {

                int index = GetIndex(iWorldObj.ObjectRectangle);

​

                if(index != -1)

                {

                    nodes[index].Add(iWorldObj);

​

                    return;

                }

            }

​

            _objects.Add(iWorldObj);

​

            if(_objects.Count > Constants.QUADTREE_MAX_OBJECTS && _level < Constants.QUADTREE_MAX_LEVELS)

            {

                if(nodes[0] == null)

                {

                    Split();

                }

​

                int i = 0;

​

                while(i < _objects.Count)

                {

                    int index = GetIndex(_objects[i].ObjectRectangle);

​

                    if(index != -1)

                    {

                        var qt = _objects[i];

                        _objects.RemoveAt(i);

                        nodes[index].Add(qt);

                    }

                    else

                    {

                        i++;

                    }

                }

            }

        }

    }

}

​