+ plugins project

12 files changed, 1060 insertions, 0 deletions

diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/CollisionComponent.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/CollisionComponent.cs
new file mode 100644
index 0000000..51467d9
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/CollisionComponent.cs
@@ -0,0 +1,341 @@
+using System;
+using System.Collections.Generic;
+using System.Data;
+using System.Diagnostics;
+using System.Linq;
+using Microsoft.Xna.Framework;
+using MonoGame.Extended.Collisions.Layers;
+using MonoGame.Extended.Collisions.QuadTree;
+
+namespace MonoGame.Extended.Collisions
+{
+    /// <summary>
+    /// Handles basic collision between actors.
+    /// When two actors collide, their OnCollision method is called.
+    /// </summary>
+    public class CollisionComponent : SimpleGameComponent
+    {
+        public const string DEFAULT_LAYER_NAME = "default";
+
+        private Dictionary<string, Layer> _layers = new();
+
+        /// <summary>
+        /// List of collision's layers
+        /// </summary>
+        public IReadOnlyDictionary<string, Layer> Layers => _layers;
+
+        private HashSet<(Layer, Layer)> _layerCollision = new();
+
+        /// <summary>
+        /// Creates component with default layer, which is a collision tree covering the specified area (using <see cref="QuadTree"/>.
+        /// </summary>
+        /// <param name="boundary">Boundary of the collision tree.</param>
+        public CollisionComponent(RectangleF boundary)
+        {
+            SetDefaultLayer(new Layer(new QuadTreeSpace(boundary)));
+        }
+
+        /// <summary>
+        /// Creates component with specifies default layer.
+        /// If layer is null, method creates component without default layer.
+        /// </summary>
+        /// <param name="layer">Default layer</param>
+        public CollisionComponent(Layer layer = null)
+        {
+            if (layer is not null)
+                SetDefaultLayer(layer);
+        }
+
+        /// <summary>
+        /// The main layer has the name from <see cref="DEFAULT_LAYER_NAME"/>.
+        /// The main layer collision with itself and all other layers.
+        /// </summary>
+        /// <param name="layer">Layer to set default</param>
+        public void SetDefaultLayer(Layer layer)
+        {
+            if (_layers.ContainsKey(DEFAULT_LAYER_NAME))
+                Remove(DEFAULT_LAYER_NAME);
+            Add(DEFAULT_LAYER_NAME, layer);
+            foreach (var otherLayer in _layers.Values)
+                AddCollisionBetweenLayer(layer, otherLayer);
+        }
+
+        /// <summary>
+        /// Update the collision tree and process collisions.
+        /// </summary>
+        /// <remarks>
+        /// Boundary shapes are updated if they were changed since the last
+        /// update.
+        /// </remarks>
+        /// <param name="gameTime"></param>
+        public override void Update(GameTime gameTime)
+        {
+            foreach (var layer in _layers.Values)
+                layer.Reset();
+
+            foreach (var (firstLayer, secondLayer) in _layerCollision)
+            foreach (var actor in firstLayer.Space)
+            {
+                var collisions = secondLayer.Space.Query(actor.Bounds.BoundingRectangle);
+                foreach (var other in collisions)
+                    if (actor != other && actor.Bounds.Intersects(other.Bounds))
+                    {
+                        var penetrationVector = CalculatePenetrationVector(actor.Bounds, other.Bounds);
+
+                        actor.OnCollision(new CollisionEventArgs
+                        {
+                            Other = other,
+                            PenetrationVector = penetrationVector
+                        });
+                        other.OnCollision(new CollisionEventArgs
+                        {
+                            Other = actor,
+                            PenetrationVector = -penetrationVector
+                        });
+                    }
+
+            }
+        }
+
+        /// <summary>
+        /// Inserts the target into the collision tree.
+        /// The target will have its OnCollision called when collisions occur.
+        /// </summary>
+        /// <param name="target">Target to insert.</param>
+        public void Insert(ICollisionActor target)
+        {
+            var layerName = target.LayerName ?? DEFAULT_LAYER_NAME;
+            if (!_layers.TryGetValue(layerName, out var layer))
+            {
+                throw new UndefinedLayerException(layerName);
+            }
+
+            layer.Space.Insert(target);
+        }
+
+        /// <summary>
+        /// Removes the target from the collision tree.
+        /// </summary>
+        /// <param name="target">Target to remove.</param>
+        public void Remove(ICollisionActor target)
+        {
+            if (target.LayerName is not null)
+                _layers[target.LayerName].Space.Remove(target);
+            else
+                foreach (var layer in _layers.Values)
+                    if (layer.Space.Remove(target))
+                        return;
+        }
+
+        #region Layers
+
+        /// <summary>
+        /// Add the new layer. The name of layer must be unique.
+        /// </summary>
+        /// <param name="name">Name of layer</param>
+        /// <param name="layer">The new layer</param>
+        /// <exception cref="ArgumentNullException"><paramref name="name"/> is null</exception>
+        public void Add(string name, Layer layer)
+        {
+            if (string.IsNullOrWhiteSpace(name))
+                throw new ArgumentNullException(nameof(name));
+
+            if (!_layers.TryAdd(name, layer))
+                throw new DuplicateNameException(name);
+
+            if (name != DEFAULT_LAYER_NAME)
+                AddCollisionBetweenLayer(_layers[DEFAULT_LAYER_NAME], layer);
+        }
+
+        /// <summary>
+        /// Remove the layer and all layer's collisions.
+        /// </summary>
+        /// <param name="name">The name of the layer to delete</param>
+        /// <param name="layer">The layer to delete</param>
+        public void Remove(string name = null, Layer layer = null)
+        {
+            name ??= _layers.First(x => x.Value == layer).Key;
+            _layers.Remove(name, out layer);
+            _layerCollision.RemoveWhere(tuple => tuple.Item1 == layer || tuple.Item2 == layer);
+        }
+
+        public void AddCollisionBetweenLayer(Layer a, Layer b)
+        {
+            _layerCollision.Add((a, b));
+        }
+
+        public void AddCollisionBetweenLayer(string nameA, string nameB)
+        {
+            _layerCollision.Add((_layers[nameA], _layers[nameB]));
+        }
+
+        #endregion
+
+        #region Penetration Vectors
+
+        /// <summary>
+        /// Calculate a's penetration into b
+        /// </summary>
+        /// <param name="a">The penetrating shape.</param>
+        /// <param name="b">The shape being penetrated.</param>
+        /// <returns>The distance vector from the edge of b to a's Position</returns>
+        private static Vector2 CalculatePenetrationVector(IShapeF a, IShapeF b)
+        {
+            return a switch
+                {
+                    CircleF circleA when b is CircleF circleB => PenetrationVector(circleA, circleB),
+                    CircleF circleA when b is RectangleF rectangleB => PenetrationVector(circleA, rectangleB),
+                    CircleF circleA when b is OrientedRectangle orientedRectangleB => PenetrationVector(circleA, orientedRectangleB),
+
+                    RectangleF rectangleA when b is CircleF circleB => PenetrationVector(rectangleA, circleB),
+                    RectangleF rectangleA when b is RectangleF rectangleB => PenetrationVector(rectangleA, rectangleB),
+                    RectangleF rectangleA when b is OrientedRectangle orientedRectangleB => PenetrationVector(rectangleA, orientedRectangleB),
+
+                    OrientedRectangle orientedRectangleA when b is CircleF circleB => PenetrationVector(orientedRectangleA, circleB),
+                    OrientedRectangle orientedRectangleA when b is RectangleF rectangleB => PenetrationVector(orientedRectangleA, rectangleB),
+                    OrientedRectangle orientedRectangleA when b is OrientedRectangle orientedRectangleB => PenetrationVector(orientedRectangleA, orientedRectangleB),
+
+                    _ => throw new ArgumentOutOfRangeException(nameof(a))
+                };
+        }
+
+        private static Vector2 PenetrationVector(CircleF circ1, CircleF circ2)
+        {
+            if (!circ1.Intersects(circ2))
+            {
+                return Vector2.Zero;
+            }
+
+            var displacement = Point2.Displacement(circ1.Center, circ2.Center);
+
+            Vector2 desiredDisplacement;
+            if (displacement != Vector2.Zero)
+            {
+                desiredDisplacement = displacement.NormalizedCopy() * (circ1.Radius + circ2.Radius);
+            }
+            else
+            {
+                desiredDisplacement = -Vector2.UnitY * (circ1.Radius + circ2.Radius);
+            }
+
+
+            var penetration = displacement - desiredDisplacement;
+            return penetration;
+        }
+
+        private static Vector2 PenetrationVector(CircleF circ, RectangleF rect)
+        {
+            var collisionPoint = rect.ClosestPointTo(circ.Center);
+            var cToCollPoint = collisionPoint - circ.Center;
+
+            if (rect.Contains(circ.Center) || cToCollPoint.Equals(Vector2.Zero))
+            {
+                var displacement = Point2.Displacement(circ.Center, rect.Center);
+
+                Vector2 desiredDisplacement;
+                if (displacement != Vector2.Zero)
+                {
+                    // Calculate penetration as only in X or Y direction.
+                    // Whichever is lower.
+                    var dispx = new Vector2(displacement.X, 0);
+                    var dispy = new Vector2(0, displacement.Y);
+                    dispx.Normalize();
+                    dispy.Normalize();
+
+                    dispx *= (circ.Radius + rect.Width / 2);
+                    dispy *= (circ.Radius + rect.Height / 2);
+
+                    if (dispx.LengthSquared() < dispy.LengthSquared())
+                    {
+                        desiredDisplacement = dispx;
+                        displacement.Y = 0;
+                    }
+                    else
+                    {
+                        desiredDisplacement = dispy;
+                        displacement.X = 0;
+                    }
+                }
+                else
+                {
+                    desiredDisplacement = -Vector2.UnitY * (circ.Radius + rect.Height / 2);
+                }
+
+                var penetration = displacement - desiredDisplacement;
+                return penetration;
+            }
+            else
+            {
+                var penetration = circ.Radius * cToCollPoint.NormalizedCopy() - cToCollPoint;
+                return penetration;
+            }
+        }
+
+        private static Vector2 PenetrationVector(CircleF circleA, OrientedRectangle orientedRectangleB)
+        {
+            var rotation = Matrix2.CreateRotationZ(orientedRectangleB.Orientation.Rotation);
+            var circleCenterInRectangleSpace = rotation.Transform(circleA.Center - orientedRectangleB.Center);
+            var circleInRectangleSpace = new CircleF(circleCenterInRectangleSpace, circleA.Radius);
+            var boundingRectangle = new BoundingRectangle(new Point2(), orientedRectangleB.Radii);
+
+            var penetrationVector = PenetrationVector(circleInRectangleSpace, boundingRectangle);
+            var inverseRotation = Matrix2.CreateRotationZ(-orientedRectangleB.Orientation.Rotation);
+            var transformedPenetration = inverseRotation.Transform(penetrationVector);
+
+            return transformedPenetration;
+        }
+
+        private static Vector2 PenetrationVector(RectangleF rect, CircleF circ)
+        {
+            return -PenetrationVector(circ, rect);
+        }
+
+        private static Vector2 PenetrationVector(RectangleF rect1, RectangleF rect2)
+        {
+            var intersectingRectangle = RectangleF.Intersection(rect1, rect2);
+            Debug.Assert(!intersectingRectangle.IsEmpty,
+                "Violation of: !intersect.IsEmpty; Rectangles must intersect to calculate a penetration vector.");
+
+            Vector2 penetration;
+            if (intersectingRectangle.Width < intersectingRectangle.Height)
+            {
+                var d = rect1.Center.X < rect2.Center.X
+                    ? intersectingRectangle.Width
+                    : -intersectingRectangle.Width;
+                penetration = new Vector2(d, 0);
+            }
+            else
+            {
+                var d = rect1.Center.Y < rect2.Center.Y
+                    ? intersectingRectangle.Height
+                    : -intersectingRectangle.Height;
+                penetration = new Vector2(0, d);
+            }
+
+            return penetration;
+        }
+
+        private static Vector2 PenetrationVector(RectangleF rectangleA, OrientedRectangle orientedRectangleB)
+        {
+            return PenetrationVector((OrientedRectangle)rectangleA, orientedRectangleB);
+        }
+
+        private static Vector2 PenetrationVector(OrientedRectangle orientedRectangleA, CircleF circleB)
+        {
+            return -PenetrationVector(circleB, orientedRectangleA);
+        }
+
+        private static Vector2 PenetrationVector(OrientedRectangle orientedRectangleA, RectangleF rectangleB)
+        {
+            return -PenetrationVector(rectangleB, orientedRectangleA);
+        }
+
+        private static Vector2 PenetrationVector(OrientedRectangle orientedRectangleA, OrientedRectangle orientedRectangleB)
+        {
+            return OrientedRectangle.Intersects(orientedRectangleA, orientedRectangleB)
+                .MinimumTranslationVector;
+        }
+
+        #endregion
+    }
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/CollisionEventArgs.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/CollisionEventArgs.cs
new file mode 100644
index 0000000..ca401df
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/CollisionEventArgs.cs
@@ -0,0 +1,26 @@
+using System;
+using Microsoft.Xna.Framework;
+
+namespace MonoGame.Extended.Collisions
+{
+    /// <summary>
+    /// This class holds data on a collision. It is passed as a parameter to
+    /// OnCollision methods.
+    /// </summary>
+    public class CollisionEventArgs : EventArgs
+    {
+        /// <summary>
+        /// Gets the object being collided with.
+        /// </summary>
+        public ICollisionActor Other { get; internal set; }
+
+        /// <summary>
+        /// Gets a vector representing the overlap between the two objects.
+        /// </summary>
+        /// <remarks>
+        /// This vector starts at the edge of <see cref="Other"/> and ends at
+        /// the Actor's location.
+        /// </remarks>
+        public Vector2 PenetrationVector { get; internal set; }
+    }
+}
\ No newline at end of file
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/ICollisionActor.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/ICollisionActor.cs
new file mode 100644
index 0000000..6a05592
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/ICollisionActor.cs
@@ -0,0 +1,27 @@
+using System;
+
+namespace MonoGame.Extended.Collisions
+{
+    /// <summary>
+    /// An actor that can be collided with.
+    /// </summary>
+    public interface ICollisionActor
+    {
+        /// <summary>
+        /// A name of layer, which will contains this actor.
+        /// If it equals null, an actor will insert into a default layer
+        /// </summary>
+        string LayerName { get => null; }
+
+        /// <summary>
+        /// A bounds of an actor. It is using for collision calculating
+        /// </summary>
+        IShapeF Bounds { get; }
+
+        /// <summary>
+        /// It will called, when collision with an another actor fires
+        /// </summary>
+        /// <param name="collisionInfo">Data about collision</param>
+        void OnCollision(CollisionEventArgs collisionInfo);
+    }
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/ISpaceAlgorithm.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/ISpaceAlgorithm.cs
new file mode 100644
index 0000000..a95f737
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/ISpaceAlgorithm.cs
@@ -0,0 +1,40 @@
+using System.Collections.Generic;
+
+namespace MonoGame.Extended.Collisions;
+
+/// <summary>
+/// Interface, which split space for optimization of collisions.
+/// </summary>
+public interface ISpaceAlgorithm
+{
+    /// <summary>
+    /// Inserts the actor into the space.
+    /// The actor will have its OnCollision called when collisions occur.
+    /// </summary>
+    /// <param name="actor">Actor to insert.</param>
+    void Insert(ICollisionActor actor);
+
+    /// <summary>
+    /// Removes the actor into the space.
+    /// </summary>
+    /// <param name="actor">Actor to remove.</param>
+    bool Remove(ICollisionActor actor);
+
+    /// <summary>
+    /// Removes the actor into the space.
+    /// The actor will have its OnCollision called when collisions occur.
+    /// </summary>
+    /// <param name="actor">Actor to remove.</param>
+    IEnumerable<ICollisionActor> Query(RectangleF boundsBoundingRectangle);
+
+    /// <summary>
+    /// for foreach
+    /// </summary>
+    /// <returns></returns>
+    List<ICollisionActor>.Enumerator GetEnumerator();
+
+    /// <summary>
+    /// Restructure the space with new positions.
+    /// </summary>
+    void Reset();
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/Layers/Layer.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/Layers/Layer.cs
new file mode 100644
index 0000000..6e97ac8
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/Layers/Layer.cs
@@ -0,0 +1,39 @@
+using System;
+
+namespace MonoGame.Extended.Collisions.Layers;
+
+/// <summary>
+/// Layer is a group of collision's actors.
+/// </summary>
+public class Layer
+{
+    /// <summary>
+    /// If this property equals true, layer always will reset collision space.
+    /// </summary>
+    public bool IsDynamic { get; set; } = true;
+
+
+    /// <summary>
+    /// The space, which contain actors.
+    /// </summary>
+    public readonly ISpaceAlgorithm Space;
+
+    /// <summary>
+    /// Constructor for layer
+    /// </summary>
+    /// <param name="spaceAlgorithm">A space algorithm for actors</param>
+    /// <exception cref="ArgumentNullException"><paramref name="spaceAlgorithm"/> is null</exception>
+    public Layer(ISpaceAlgorithm spaceAlgorithm)
+    {
+        Space = spaceAlgorithm ?? throw new ArgumentNullException(nameof(spaceAlgorithm));
+    }
+
+    /// <summary>
+    /// Restructure a inner collection, if layer is dynamic, because actors can change own position
+    /// </summary>
+    public virtual void Reset()
+    {
+        if (IsDynamic)
+            Space.Reset();
+    }
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/Layers/UndefinedLayerException.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/Layers/UndefinedLayerException.cs
new file mode 100644
index 0000000..a27b5b6
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/Layers/UndefinedLayerException.cs
@@ -0,0 +1,18 @@
+namespace MonoGame.Extended.Collisions.Layers;
+
+using System;
+
+/// <summary>
+/// Thrown when the collision system has no layer defined with the specified name
+/// </summary>
+public class UndefinedLayerException : Exception
+{
+    /// <summary>
+    /// Thrown when the collision system has no layer defined with the specified name
+    /// </summary>
+    /// <param name="layerName">The undefined layer name</param>
+    public UndefinedLayerException(string layerName)
+        : base($"Layer with name '{layerName}' is undefined")
+    {
+    }
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/MonoGame.Extended.Collisions.csproj b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/MonoGame.Extended.Collisions.csproj
new file mode 100644
index 0000000..bd0729c
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/MonoGame.Extended.Collisions.csproj
@@ -0,0 +1,12 @@
+<Project Sdk="Microsoft.NET.Sdk">
+
+  <PropertyGroup>
+    <Description>Collisions to make MonoGame more awesome.</Description>
+    <PackageTags>monogame collisions</PackageTags>
+  </PropertyGroup>
+
+  <ItemGroup>
+    <ProjectReference Include="..\MonoGame.Extended\MonoGame.Extended.csproj" />
+  </ItemGroup>
+
+</Project>
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTree.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTree.cs
new file mode 100644
index 0000000..a46699a
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTree.cs
@@ -0,0 +1,310 @@
+using System;
+using System.Collections.Generic;
+
+namespace MonoGame.Extended.Collisions.QuadTree
+{
+    /// <summary>
+    /// Class for doing collision handling with a quad tree.
+    /// </summary>
+    public class QuadTree
+    {
+        /// <summary>
+        /// The default maximum depth.
+        /// </summary>
+        public const int DefaultMaxDepth = 7;
+
+        /// <summary>
+        /// The default maximum objects per node.
+        /// </summary>
+        public const int DefaultMaxObjectsPerNode = 25;
+
+        /// <summary>
+        /// Contains the children of this node.
+        /// </summary>
+        protected List<QuadTree> Children = new List<QuadTree>();
+
+        /// <summary>
+        /// Contains the data for this node in the quadtree.
+        /// </summary>
+        protected HashSet<QuadtreeData> Contents = new HashSet<QuadtreeData>();
+
+        /// <summary>
+        /// Creates a quad tree with the given bounds.
+        /// </summary>
+        /// <param name="bounds">The bounds of the new quad tree.</param>
+        public QuadTree(RectangleF bounds)
+        {
+            CurrentDepth = 0;
+            NodeBounds = bounds;
+        }
+
+        /// <summary>
+        /// Gets or sets the current depth for this node in the quadtree.
+        /// </summary>
+        protected int CurrentDepth { get; set; }
+        /// <summary>
+        /// Gets or sets the maximum depth of the quadtree.
+        /// </summary>
+        protected int MaxDepth { get; set; } = DefaultMaxDepth;
+        /// <summary>
+        /// Gets or sets the maximum objects per node in this quadtree.
+        /// </summary>
+        protected int MaxObjectsPerNode { get; set; } = DefaultMaxObjectsPerNode;
+
+        /// <summary>
+        /// Gets the bounds of the area contained in this quad tree.
+        /// </summary>
+        public  RectangleF NodeBounds { get; protected set; }
+
+        /// <summary>
+        /// Gets whether the current node is a leaf node.
+        /// </summary>
+        public bool IsLeaf => Children.Count == 0;
+
+        /// <summary>
+        /// Counts the number of unique targets in the current Quadtree.
+        /// </summary>
+        /// <returns>Returns the targets of objects found.</returns>
+        public int NumTargets()
+        {
+            List<QuadtreeData> dirtyItems = new List<QuadtreeData>();
+            var objectCount = 0;
+
+            // Do BFS on nodes to count children.
+            var process = new Queue<QuadTree>();
+            process.Enqueue(this);
+            while (process.Count > 0)
+            {
+                var processing = process.Dequeue();
+                if (!processing.IsLeaf)
+                {
+                    foreach (var child in processing.Children)
+                    {
+                        process.Enqueue(child);
+                    }
+                }
+                else
+                {
+                    foreach (var data in processing.Contents)
+                    {
+                        if (data.Dirty == false)
+                        {
+                            objectCount++;
+                            data.MarkDirty();
+                            dirtyItems.Add(data);
+                        }
+                    }
+                }
+            }
+            foreach (var quadtreeData in dirtyItems)
+            {
+                quadtreeData.MarkClean();
+            }
+            return objectCount;
+        }
+
+        /// <summary>
+        /// Inserts the data into the tree.
+        /// </summary>
+        /// <param name="data">Data being inserted.</param>
+        public void Insert(QuadtreeData data)
+        {
+            var actorBounds = data.Bounds;
+
+            // Object doesn't fit into this node.
+            if (!NodeBounds.Intersects(actorBounds))
+            {
+                return;
+            }
+
+            if (IsLeaf && Contents.Count >= MaxObjectsPerNode)
+            {
+                Split();
+            }
+
+            if (IsLeaf)
+            {
+                AddToLeaf(data);
+            }
+            else
+            {
+                foreach (var child in Children)
+                {
+                    child.Insert(data);
+                }
+            }
+        }
+
+        /// <summary>
+        /// Removes data from the Quadtree
+        /// </summary>
+        /// <param name="data">The data to be removed.</param>
+        public void Remove(QuadtreeData data)
+        {
+            if (IsLeaf)
+            {
+                data.RemoveParent(this);
+                Contents.Remove(data);
+            }
+            else
+            {
+                throw new InvalidOperationException($"Cannot remove from a non leaf {nameof(QuadTree)}");
+            }
+        }
+
+        /// <summary>
+        /// Removes unnecessary leaf nodes and simplifies the quad tree.
+        /// </summary>
+        public void Shake()
+        {
+            if (IsLeaf)
+            {
+                return;
+            }
+
+            List<QuadtreeData> dirtyItems = new List<QuadtreeData>();
+
+            var numObjects = NumTargets();
+            if (numObjects == 0)
+            {
+                Children.Clear();
+            }
+            else if (numObjects < MaxObjectsPerNode)
+            {
+                var process = new Queue<QuadTree>();
+                process.Enqueue(this);
+                while (process.Count > 0)
+                {
+                    var processing = process.Dequeue();
+                    if (!processing.IsLeaf)
+                    {
+                        foreach (var subTree in processing.Children)
+                        {
+                            process.Enqueue(subTree);
+                        }
+                    }
+                    else
+                    {
+                        foreach (var data in processing.Contents)
+                        {
+                            if (data.Dirty == false)
+                            {
+                                AddToLeaf(data);
+                                data.MarkDirty();
+                                dirtyItems.Add(data);
+                            }
+                        }
+                    }
+                }
+                Children.Clear();
+            }
+
+            foreach (var quadtreeData in dirtyItems)
+            {
+                quadtreeData.MarkClean();
+            }
+        }
+
+        private void AddToLeaf(QuadtreeData data)
+        {
+            data.AddParent(this);
+            Contents.Add(data);
+        }
+
+        /// <summary>
+        /// Splits a quadtree into quadrants.
+        /// </summary>
+        public void Split()
+        {
+            if (CurrentDepth + 1 >= MaxDepth) return;
+
+            var min = NodeBounds.TopLeft;
+            var max = NodeBounds.BottomRight;
+            var center = NodeBounds.Center;
+
+            RectangleF[] childAreas =
+            {
+                RectangleF.CreateFrom(min, center),
+                RectangleF.CreateFrom(new Point2(center.X, min.Y), new Point2(max.X, center.Y)),
+                RectangleF.CreateFrom(center, max),
+                RectangleF.CreateFrom(new Point2(min.X, center.Y), new Point2(center.X, max.Y))
+            };
+
+            for (var i = 0; i < childAreas.Length; ++i)
+            {
+                var node = new QuadTree(childAreas[i]);
+                Children.Add(node);
+                Children[i].CurrentDepth = CurrentDepth + 1;
+            }
+
+            foreach (QuadtreeData contentQuadtree in Contents)
+            {
+                foreach (QuadTree childQuadtree in Children)
+                {
+                    childQuadtree.Insert(contentQuadtree);
+                }
+            }
+            Clear();
+        }
+
+        /// <summary>
+        /// Clear current node and all children
+        /// </summary>
+        public void ClearAll()
+        {
+            foreach (QuadTree childQuadtree in Children)
+                childQuadtree.ClearAll();
+            Clear();
+        }
+
+        private void Clear()
+        {
+            foreach (QuadtreeData quadtreeData in Contents)
+            {
+                quadtreeData.RemoveParent(this);
+            }
+            Contents.Clear();
+        }
+
+        /// <summary>
+        /// Queries the quadtree for targets that intersect with the given area.
+        /// </summary>
+        /// <param name="area">The area to query for overlapping targets</param>
+        /// <returns>A unique list of targets intersected by area.</returns>
+        public List<QuadtreeData> Query(ref RectangleF area)
+        {
+            var recursiveResult = new List<QuadtreeData>();
+            QueryWithoutReset(ref area, recursiveResult);
+            foreach (var quadtreeData in recursiveResult)
+            {
+                quadtreeData.MarkClean();
+            }
+            return recursiveResult;
+        }
+
+        private void QueryWithoutReset(ref RectangleF area, List<QuadtreeData> recursiveResult)
+        {
+            if (!NodeBounds.Intersects(area))
+                return;
+
+            if (IsLeaf)
+            {
+                foreach (QuadtreeData quadtreeData in Contents)
+                {
+                    if (quadtreeData.Dirty == false && quadtreeData.Bounds.Intersects(area))
+                    {
+                        recursiveResult.Add(quadtreeData);
+                        quadtreeData.MarkDirty();
+                    }
+                }
+            }
+            else
+            {
+                for (int i = 0, size = Children.Count; i < size; i++)
+                {
+                    Children[i].QueryWithoutReset(ref area, recursiveResult);
+                }
+            }
+        }
+    }
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTreeData.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTreeData.cs
new file mode 100644
index 0000000..db6da3e
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTreeData.cs
@@ -0,0 +1,88 @@
+using System.Collections.Generic;
+using System.Linq;
+
+namespace MonoGame.Extended.Collisions.QuadTree;
+
+/// <summary>
+/// Data structure for the quad tree.
+/// Holds the entity and collision data for it.
+/// </summary>
+public class QuadtreeData
+{
+    private readonly ICollisionActor _target;
+    private readonly HashSet<QuadTree> _parents = new();
+
+    /// <summary>
+    /// Initialize a new instance of QuadTreeData.
+    /// </summary>
+    /// <param name="target"></param>
+    public QuadtreeData(ICollisionActor target)
+    {
+        _target = target;
+        Bounds = _target.Bounds.BoundingRectangle;
+    }
+
+    /// <summary>
+    /// Remove a parent node.
+    /// </summary>
+    /// <param name="parent"></param>
+    public void RemoveParent(QuadTree parent)
+    {
+        _parents.Remove(parent);
+    }
+
+    /// <summary>
+    /// Add a parent node.
+    /// </summary>
+    /// <param name="parent"></param>
+    public void AddParent(QuadTree parent)
+    {
+        _parents.Add(parent);
+        Bounds = _target.Bounds.BoundingRectangle;
+    }
+
+    /// <summary>
+    /// Remove all parent nodes from this node.
+    /// </summary>
+    public void RemoveFromAllParents()
+    {
+        foreach (var parent in _parents.ToList())
+        {
+            parent.Remove(this);
+        }
+
+        _parents.Clear();
+    }
+
+    /// <summary>
+    /// Gets the bounding box for collision detection.
+    /// </summary>
+    public RectangleF Bounds { get; set; }
+
+    /// <summary>
+    /// Gets the collision actor target.
+    /// </summary>
+    public ICollisionActor Target => _target;
+
+    /// <summary>
+    /// Gets or sets whether Target has had its collision handled this
+    /// iteration.
+    /// </summary>
+    public bool Dirty { get; private set; }
+
+    /// <summary>
+    /// Mark node as dirty.
+    /// </summary>
+    public void MarkDirty()
+    {
+        Dirty = true;
+    }
+
+    /// <summary>
+    /// Mark node as clean, i.e. not dirty.
+    /// </summary>
+    public void MarkClean()
+    {
+        Dirty = false;
+    }
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTreeSpace.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTreeSpace.cs
new file mode 100644
index 0000000..3e9625f
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTreeSpace.cs
@@ -0,0 +1,76 @@
+using System.Collections.Generic;
+using System.Linq;
+
+namespace MonoGame.Extended.Collisions.QuadTree;
+
+public class QuadTreeSpace: ISpaceAlgorithm
+{
+    private readonly QuadTree _collisionTree;
+    private readonly List<ICollisionActor> _actors = new();
+    private readonly Dictionary<ICollisionActor, QuadtreeData> _targetDataDictionary = new();
+
+    public QuadTreeSpace(RectangleF boundary)
+    {
+        _collisionTree = new QuadTree(boundary);
+    }
+
+    /// <summary>
+    /// Inserts the target into the collision tree.
+    /// The target will have its OnCollision called when collisions occur.
+    /// </summary>
+    /// <param name="target">Target to insert.</param>
+    public void Insert(ICollisionActor target)
+    {
+        if (!_targetDataDictionary.ContainsKey(target))
+        {
+            var data = new QuadtreeData(target);
+            _targetDataDictionary.Add(target, data);
+            _collisionTree.Insert(data);
+            _actors.Add(target);
+        }
+    }
+
+    /// <summary>
+    /// Removes the target from the collision tree.
+    /// </summary>
+    /// <param name="target">Target to remove.</param>
+    public bool Remove(ICollisionActor target)
+    {
+        if (_targetDataDictionary.ContainsKey(target))
+        {
+            var data = _targetDataDictionary[target];
+            data.RemoveFromAllParents();
+            _targetDataDictionary.Remove(target);
+            _collisionTree.Shake();
+            _actors.Remove(target);
+            return true;
+        }
+
+        return false;
+    }
+
+    /// <summary>
+    /// Restructure a inner collection, if layer is dynamic, because actors can change own position
+    /// </summary>
+    public void Reset()
+    {
+        _collisionTree.ClearAll();
+        foreach (var value in _targetDataDictionary.Values)
+        {
+            _collisionTree.Insert(value);
+        }
+        _collisionTree.Shake();
+    }
+
+    /// <summary>
+    /// foreach support
+    /// </summary>
+    /// <returns></returns>
+    public List<ICollisionActor>.Enumerator GetEnumerator() => _actors.GetEnumerator();
+
+    /// <inheritdoc cref="QuadTree.Query"/>
+    public IEnumerable<ICollisionActor> Query(RectangleF boundsBoundingRectangle)
+    {
+        return _collisionTree.Query(ref boundsBoundingRectangle).Select(x => x.Target);
+    }
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/SpatialHash.cs b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/SpatialHash.cs
new file mode 100644
index 0000000..2b0920e
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/SpatialHash.cs
@@ -0,0 +1,79 @@
+using System;
+using System.Collections.Generic;
+using System.Runtime.CompilerServices;
+
+namespace MonoGame.Extended.Collisions;
+
+public class SpatialHash: ISpaceAlgorithm
+{
+    private readonly Dictionary<int, List<ICollisionActor>> _dictionary = new();
+    private readonly List<ICollisionActor> _actors = new();
+
+    private readonly Size2 _size;
+
+    public SpatialHash(Size2 size)
+    {
+        _size = size;
+    }
+
+    public void Insert(ICollisionActor actor)
+    {
+        InsertToHash(actor);
+        _actors.Add(actor);
+    }
+
+    [MethodImpl(MethodImplOptions.AggressiveInlining)]
+    private void InsertToHash(ICollisionActor actor)
+    {
+        var rect = actor.Bounds.BoundingRectangle;
+        for (var x = rect.Left; x < rect.Right; x+=_size.Width)
+        for (var y = rect.Top; y < rect.Bottom; y+=_size.Height)
+            AddToCell(x, y, actor);
+    }
+
+    [MethodImpl(MethodImplOptions.AggressiveInlining)]
+    private void AddToCell(float x, float y, ICollisionActor actor)
+    {
+        var index = GetIndex(x, y);
+        if (_dictionary.TryGetValue(index, out var actors))
+            actors.Add(actor);
+        else
+            _dictionary[index] = new() { actor };
+    }
+
+    [MethodImpl(MethodImplOptions.AggressiveInlining)]
+    private int GetIndex(float x, float y)
+    {
+        return (int)(x / _size.Width) << 16 + (int)(y / _size.Height);
+    }
+
+    public bool Remove(ICollisionActor actor)
+    {
+        foreach (var actors in _dictionary.Values)
+            actors.Remove(actor);
+        return _actors.Remove(actor);
+    }
+
+    public IEnumerable<ICollisionActor> Query(RectangleF boundsBoundingRectangle)
+    {
+        var results = new HashSet<ICollisionActor>();
+        var bounds = boundsBoundingRectangle.BoundingRectangle;
+
+        for (var x = boundsBoundingRectangle.Left; x < boundsBoundingRectangle.Right; x+=_size.Width)
+        for (var y = boundsBoundingRectangle.Top; y < boundsBoundingRectangle.Bottom; y+=_size.Height)
+            if (_dictionary.TryGetValue(GetIndex(x, y), out var actors))
+                foreach (var actor in actors)
+                    if (bounds.Intersects(actor.Bounds))
+                        results.Add(actor);
+        return results;
+    }
+
+    public List<ICollisionActor>.Enumerator GetEnumerator() => _actors.GetEnumerator();
+
+    public void Reset()
+    {
+        _dictionary.Clear();
+        foreach (var actor in _actors)
+            InsertToHash(actor);
+    }
+}
diff --git a/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/packages.config b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/packages.config
new file mode 100644
index 0000000..28c0144
--- /dev/null
+++ b/Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/packages.config
@@ -0,0 +1,4 @@
+<?xml version="1.0" encoding="utf-8"?>
+<packages>
+  <package id="MonoGame.Framework.Portable" version="3.6.0.1625" targetFramework="portable45-net45+win8+wpa81" />
+</packages>
\ No newline at end of file