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
---
.../QuadTree/QuadTree.cs | 310 +++++++++++++++++++++
1 file changed, 310 insertions(+)
create mode 100644 Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTree.cs
(limited to 'Plugins/MonoGame.Extended/source/MonoGame.Extended.Collisions/QuadTree/QuadTree.cs')
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);
+ }
+ }
+ }
+ }
+}
--
cgit v1.1-26-g67d0