From acea7b2e728787a0d83bbf83c8c1f042d2c32e7e Mon Sep 17 00:00:00 2001 From: chai <215380520@qq.com> Date: Mon, 3 Jun 2024 10:15:45 +0800 Subject: + plugins project --- .../CollisionComponent.cs | 341 +++++++++++++++++++++ .../CollisionEventArgs.cs | 26 ++ .../ICollisionActor.cs | 27 ++ .../ISpaceAlgorithm.cs | 40 +++ .../MonoGame.Extended.Collisions/Layers/Layer.cs | 39 +++ .../Layers/UndefinedLayerException.cs | 18 ++ .../MonoGame.Extended.Collisions.csproj | 12 + .../QuadTree/QuadTree.cs | 310 +++++++++++++++++++ .../QuadTree/QuadTreeData.cs | 88 ++++++ .../QuadTree/QuadTreeSpace.cs | 76 +++++ .../MonoGame.Extended.Collisions/SpatialHash.cs | 79 +++++ .../MonoGame.Extended.Collisions/packages.config | 4 + 12 files changed, 1060 insertions(+) create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/CollisionComponent.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/CollisionEventArgs.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/ICollisionActor.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/ISpaceAlgorithm.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/Layers/Layer.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/Layers/UndefinedLayerException.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/MonoGame.Extended.Collisions.csproj create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTree.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTreeData.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTreeSpace.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/SpatialHash.cs create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/packages.config (limited to 'Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions') 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 +{ + /// + /// Handles basic collision between actors. + /// When two actors collide, their OnCollision method is called. + /// + public class CollisionComponent : SimpleGameComponent + { + public const string DEFAULT_LAYER_NAME = "default"; + + private Dictionary _layers = new(); + + /// + /// List of collision's layers + /// + public IReadOnlyDictionary Layers => _layers; + + private HashSet<(Layer, Layer)> _layerCollision = new(); + + /// + /// Creates component with default layer, which is a collision tree covering the specified area (using . + /// + /// Boundary of the collision tree. + public CollisionComponent(RectangleF boundary) + { + SetDefaultLayer(new Layer(new QuadTreeSpace(boundary))); + } + + /// + /// Creates component with specifies default layer. + /// If layer is null, method creates component without default layer. + /// + /// Default layer + public CollisionComponent(Layer layer = null) + { + if (layer is not null) + SetDefaultLayer(layer); + } + + /// + /// The main layer has the name from . + /// The main layer collision with itself and all other layers. + /// + /// Layer to set default + 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); + } + + /// + /// Update the collision tree and process collisions. + /// + /// + /// Boundary shapes are updated if they were changed since the last + /// update. + /// + /// + 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 + }); + } + + } + } + + /// + /// Inserts the target into the collision tree. + /// The target will have its OnCollision called when collisions occur. + /// + /// Target to insert. + 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); + } + + /// + /// Removes the target from the collision tree. + /// + /// Target to remove. + 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 + + /// + /// Add the new layer. The name of layer must be unique. + /// + /// Name of layer + /// The new layer + /// is null + 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); + } + + /// + /// Remove the layer and all layer's collisions. + /// + /// The name of the layer to delete + /// The layer to delete + 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 + + /// + /// Calculate a's penetration into b + /// + /// The penetrating shape. + /// The shape being penetrated. + /// The distance vector from the edge of b to a's Position + 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 +{ + /// + /// This class holds data on a collision. It is passed as a parameter to + /// OnCollision methods. + /// + public class CollisionEventArgs : EventArgs + { + /// + /// Gets the object being collided with. + /// + public ICollisionActor Other { get; internal set; } + + /// + /// Gets a vector representing the overlap between the two objects. + /// + /// + /// This vector starts at the edge of and ends at + /// the Actor's location. + /// + 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 +{ + /// + /// An actor that can be collided with. + /// + public interface ICollisionActor + { + /// + /// A name of layer, which will contains this actor. + /// If it equals null, an actor will insert into a default layer + /// + string LayerName { get => null; } + + /// + /// A bounds of an actor. It is using for collision calculating + /// + IShapeF Bounds { get; } + + /// + /// It will called, when collision with an another actor fires + /// + /// Data about collision + 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; + +/// +/// Interface, which split space for optimization of collisions. +/// +public interface ISpaceAlgorithm +{ + /// + /// Inserts the actor into the space. + /// The actor will have its OnCollision called when collisions occur. + /// + /// Actor to insert. + void Insert(ICollisionActor actor); + + /// + /// Removes the actor into the space. + /// + /// Actor to remove. + bool Remove(ICollisionActor actor); + + /// + /// Removes the actor into the space. + /// The actor will have its OnCollision called when collisions occur. + /// + /// Actor to remove. + IEnumerable Query(RectangleF boundsBoundingRectangle); + + /// + /// for foreach + /// + /// + List.Enumerator GetEnumerator(); + + /// + /// Restructure the space with new positions. + /// + 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; + +/// +/// Layer is a group of collision's actors. +/// +public class Layer +{ + /// + /// If this property equals true, layer always will reset collision space. + /// + public bool IsDynamic { get; set; } = true; + + + /// + /// The space, which contain actors. + /// + public readonly ISpaceAlgorithm Space; + + /// + /// Constructor for layer + /// + /// A space algorithm for actors + /// is null + public Layer(ISpaceAlgorithm spaceAlgorithm) + { + Space = spaceAlgorithm ?? throw new ArgumentNullException(nameof(spaceAlgorithm)); + } + + /// + /// Restructure a inner collection, if layer is dynamic, because actors can change own position + /// + 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; + +/// +/// Thrown when the collision system has no layer defined with the specified name +/// +public class UndefinedLayerException : Exception +{ + /// + /// Thrown when the collision system has no layer defined with the specified name + /// + /// The undefined layer name + 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 @@ + + + + Collisions to make MonoGame more awesome. + monogame collisions + + + + + + + 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 +{ + /// + /// Class for doing collision handling with a quad tree. + /// + public class QuadTree + { + /// + /// The default maximum depth. + /// + public const int DefaultMaxDepth = 7; + + /// + /// The default maximum objects per node. + /// + public const int DefaultMaxObjectsPerNode = 25; + + /// + /// Contains the children of this node. + /// + protected List Children = new List(); + + /// + /// Contains the data for this node in the quadtree. + /// + protected HashSet Contents = new HashSet(); + + /// + /// Creates a quad tree with the given bounds. + /// + /// The bounds of the new quad tree. + public QuadTree(RectangleF bounds) + { + CurrentDepth = 0; + NodeBounds = bounds; + } + + /// + /// Gets or sets the current depth for this node in the quadtree. + /// + protected int CurrentDepth { get; set; } + /// + /// Gets or sets the maximum depth of the quadtree. + /// + protected int MaxDepth { get; set; } = DefaultMaxDepth; + /// + /// Gets or sets the maximum objects per node in this quadtree. + /// + protected int MaxObjectsPerNode { get; set; } = DefaultMaxObjectsPerNode; + + /// + /// Gets the bounds of the area contained in this quad tree. + /// + public RectangleF NodeBounds { get; protected set; } + + /// + /// Gets whether the current node is a leaf node. + /// + public bool IsLeaf => Children.Count == 0; + + /// + /// Counts the number of unique targets in the current Quadtree. + /// + /// Returns the targets of objects found. + public int NumTargets() + { + List dirtyItems = new List(); + var objectCount = 0; + + // Do BFS on nodes to count children. + var process = new Queue(); + 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; + } + + /// + /// Inserts the data into the tree. + /// + /// Data being inserted. + 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); + } + } + } + + /// + /// Removes data from the Quadtree + /// + /// The data to be removed. + 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)}"); + } + } + + /// + /// Removes unnecessary leaf nodes and simplifies the quad tree. + /// + public void Shake() + { + if (IsLeaf) + { + return; + } + + List dirtyItems = new List(); + + var numObjects = NumTargets(); + if (numObjects == 0) + { + Children.Clear(); + } + else if (numObjects < MaxObjectsPerNode) + { + var process = new Queue(); + 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); + } + + /// + /// Splits a quadtree into quadrants. + /// + 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(); + } + + /// + /// Clear current node and all children + /// + public void ClearAll() + { + foreach (QuadTree childQuadtree in Children) + childQuadtree.ClearAll(); + Clear(); + } + + private void Clear() + { + foreach (QuadtreeData quadtreeData in Contents) + { + quadtreeData.RemoveParent(this); + } + Contents.Clear(); + } + + /// + /// Queries the quadtree for targets that intersect with the given area. + /// + /// The area to query for overlapping targets + /// A unique list of targets intersected by area. + public List Query(ref RectangleF area) + { + var recursiveResult = new List(); + QueryWithoutReset(ref area, recursiveResult); + foreach (var quadtreeData in recursiveResult) + { + quadtreeData.MarkClean(); + } + return recursiveResult; + } + + private void QueryWithoutReset(ref RectangleF area, List 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; + +/// +/// Data structure for the quad tree. +/// Holds the entity and collision data for it. +/// +public class QuadtreeData +{ + private readonly ICollisionActor _target; + private readonly HashSet _parents = new(); + + /// + /// Initialize a new instance of QuadTreeData. + /// + /// + public QuadtreeData(ICollisionActor target) + { + _target = target; + Bounds = _target.Bounds.BoundingRectangle; + } + + /// + /// Remove a parent node. + /// + /// + public void RemoveParent(QuadTree parent) + { + _parents.Remove(parent); + } + + /// + /// Add a parent node. + /// + /// + public void AddParent(QuadTree parent) + { + _parents.Add(parent); + Bounds = _target.Bounds.BoundingRectangle; + } + + /// + /// Remove all parent nodes from this node. + /// + public void RemoveFromAllParents() + { + foreach (var parent in _parents.ToList()) + { + parent.Remove(this); + } + + _parents.Clear(); + } + + /// + /// Gets the bounding box for collision detection. + /// + public RectangleF Bounds { get; set; } + + /// + /// Gets the collision actor target. + /// + public ICollisionActor Target => _target; + + /// + /// Gets or sets whether Target has had its collision handled this + /// iteration. + /// + public bool Dirty { get; private set; } + + /// + /// Mark node as dirty. + /// + public void MarkDirty() + { + Dirty = true; + } + + /// + /// Mark node as clean, i.e. not dirty. + /// + 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 _actors = new(); + private readonly Dictionary _targetDataDictionary = new(); + + public QuadTreeSpace(RectangleF boundary) + { + _collisionTree = new QuadTree(boundary); + } + + /// + /// Inserts the target into the collision tree. + /// The target will have its OnCollision called when collisions occur. + /// + /// Target to insert. + public void Insert(ICollisionActor target) + { + if (!_targetDataDictionary.ContainsKey(target)) + { + var data = new QuadtreeData(target); + _targetDataDictionary.Add(target, data); + _collisionTree.Insert(data); + _actors.Add(target); + } + } + + /// + /// Removes the target from the collision tree. + /// + /// Target to remove. + 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; + } + + /// + /// Restructure a inner collection, if layer is dynamic, because actors can change own position + /// + public void Reset() + { + _collisionTree.ClearAll(); + foreach (var value in _targetDataDictionary.Values) + { + _collisionTree.Insert(value); + } + _collisionTree.Shake(); + } + + /// + /// foreach support + /// + /// + public List.Enumerator GetEnumerator() => _actors.GetEnumerator(); + + /// + public IEnumerable 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> _dictionary = new(); + private readonly List _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 Query(RectangleF boundsBoundingRectangle) + { + var results = new HashSet(); + 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.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 @@ + + + + \ No newline at end of file -- cgit v1.1-26-g67d0