1 files changed, 52 insertions, 45 deletions

diff --git a/engine/structures/QuadTree.ts b/engine/structures/QuadTree.ts
index d1ff3b1..93702d0 100644
--- a/engine/structures/QuadTree.ts
+++ b/engine/structures/QuadTree.ts
@@ -1,19 +1,21 @@
-import type { Coord2D, Dimension2D } from "../interfaces";
-
-interface BoxedEntry {
-  id: number;
-  dimension: Dimension2D;
-  center: Coord2D;
-}
+import type { Coord2D, Dimension2D } from '../interfaces';
+import type { BoxedEntry, RefreshingCollisionFinderBehavior } from '.';
 
 enum Quadrant {
   I,
   II,
   III,
-  IV,
+  IV
 }
 
-export class QuadTree {
+/*
+  unused due to performance problems. here anyways, in case it _really_ is necessary at some point
+  (and to justify the amount of time i spent here).
+*/
+export class QuadTree implements RefreshingCollisionFinderBehavior {
+  private static readonly QUADTREE_MAX_LEVELS = 3;
+  private static readonly QUADTREE_SPLIT_THRESHOLD = 2000;
+
   private maxLevels: number;
   private splitThreshold: number;
   private level: number;
@@ -24,34 +26,33 @@ export class QuadTree {
   private objects: BoxedEntry[];
 
   constructor(
-    topLeft: Coord2D,
+    topLeft: Coord2D = { x: 0, y: 0 },
     dimension: Dimension2D,
-    maxLevels: number,
-    splitThreshold: number,
-    level?: number,
+    maxLevels: number = QuadTree.QUADTREE_MAX_LEVELS,
+    splitThreshold: number = QuadTree.QUADTREE_SPLIT_THRESHOLD,
+    level: number = 0
   ) {
     this.children = new Map<Quadrant, QuadTree>();
     this.objects = [];
 
     this.maxLevels = maxLevels;
     this.splitThreshold = splitThreshold;
-    this.level = level ?? 0;
+    this.level = level;
 
     this.topLeft = topLeft;
     this.dimension = dimension;
   }
 
-  public insert(id: number, dimension: Dimension2D, center: Coord2D): void {
-    const box: BoxedEntry = { id, center, dimension };
+  public insert(boxedEntry: BoxedEntry): void {
     if (this.hasChildren()) {
-      this.getQuadrants(box).forEach((quadrant) => {
+      this.getQuadrants(boxedEntry).forEach((quadrant) => {
         const quadrantBox = this.children.get(quadrant);
-        quadrantBox?.insert(id, dimension, center);
+        quadrantBox!.insert(boxedEntry);
       });
       return;
     }
 
-    this.objects.push({ id, dimension, center });
+    this.objects.push(boxedEntry);
 
     if (
       this.objects.length > this.splitThreshold &&
@@ -66,22 +67,24 @@ export class QuadTree {
 
   public clear(): void {
     this.objects = [];
+
     if (this.hasChildren()) {
       this.children.forEach((child) => child.clear());
       this.children.clear();
     }
   }
 
-  public getNeighborIds(boxedEntry: BoxedEntry): number[] {
-    const neighbors: number[] = this.objects.map(({ id }) => id);
+  public getNeighborIds(boxedEntry: BoxedEntry): Set<string> {
+    const neighbors = new Set<string>(
+      this.objects.map(({ id }) => id).filter((id) => id != boxedEntry.id)
+    );
 
     if (this.hasChildren()) {
       this.getQuadrants(boxedEntry).forEach((quadrant) => {
         const quadrantBox = this.children.get(quadrant);
-
         quadrantBox
           ?.getNeighborIds(boxedEntry)
-          .forEach((id) => neighbors.push(id));
+          .forEach((id) => neighbors.add(id));
       });
     }
 
@@ -99,9 +102,9 @@ export class QuadTree {
         [Quadrant.III, { x: this.topLeft.x, y: this.topLeft.y + halfHeight }],
         [
           Quadrant.IV,
-          { x: this.topLeft.x + halfWidth, y: this.topLeft.y + halfHeight },
-        ],
-      ] as [[Quadrant, Coord2D]]
+          { x: this.topLeft.x + halfWidth, y: this.topLeft.y + halfHeight }
+        ]
+      ] as [Quadrant, Coord2D][]
     ).forEach(([quadrant, pos]) => {
       this.children.set(
         quadrant,
@@ -110,8 +113,8 @@ export class QuadTree {
           { width: halfWidth, height: halfHeight },
           this.maxLevels,
           this.splitThreshold,
-          this.level + 1,
-        ),
+          this.level + 1
+        )
       );
     });
   }
@@ -119,52 +122,48 @@ export class QuadTree {
   private getQuadrants(boxedEntry: BoxedEntry): Quadrant[] {
     const treeCenter: Coord2D = {
       x: this.topLeft.x + this.dimension.width / 2,
-      y: this.topLeft.y + this.dimension.height / 2,
+      y: this.topLeft.y + this.dimension.height / 2
     };
 
     return (
       [
         [
           Quadrant.I,
-          (x: number, y: number) => x >= treeCenter.x && y < treeCenter.y,
+          (x: number, y: number) => x >= treeCenter.x && y < treeCenter.y
         ],
         [
           Quadrant.II,
-          (x: number, y: number) => x < treeCenter.x && y < treeCenter.y,
+          (x: number, y: number) => x < treeCenter.x && y < treeCenter.y
         ],
         [
           Quadrant.III,
-          (x: number, y: number) => x < treeCenter.x && y >= treeCenter.y,
+          (x: number, y: number) => x < treeCenter.x && y >= treeCenter.y
         ],
         [
           Quadrant.IV,
-          (x: number, y: number) => x >= treeCenter.x && y >= treeCenter.y,
-        ],
-      ] as [[Quadrant, (x: number, y: number) => boolean]]
+          (x: number, y: number) => x >= treeCenter.x && y >= treeCenter.y
+        ]
+      ] as [Quadrant, (x: number, y: number) => boolean][]
     )
       .filter(
         ([_quadrant, condition]) =>
           condition(
             boxedEntry.center.x + boxedEntry.dimension.width / 2,
-            boxedEntry.center.y + boxedEntry.dimension.height / 2,
+            boxedEntry.center.y + boxedEntry.dimension.height / 2
           ) ||
           condition(
             boxedEntry.center.x - boxedEntry.dimension.width / 2,
-            boxedEntry.center.y - boxedEntry.dimension.height / 2,
-          ),
+            boxedEntry.center.y - boxedEntry.dimension.height / 2
+          )
       )
       .map(([quadrant]) => quadrant);
   }
 
   private realignObjects(): void {
     this.objects.forEach((boxedEntry) => {
-      this.getQuadrants(boxedEntry).forEach((direction) => {
-        const quadrant = this.children.get(direction);
-        quadrant?.insert(
-          boxedEntry.id,
-          boxedEntry.dimension,
-          boxedEntry.center,
-        );
+      this.getQuadrants(boxedEntry).forEach((quadrant) => {
+        const quadrantBox = this.children.get(quadrant);
+        quadrantBox!.insert(boxedEntry);
       });
     });
 
@@ -174,4 +173,12 @@ export class QuadTree {
   private hasChildren() {
     return this.children && this.children.size > 0;
   }
+
+  public setTopLeft(topLeft: Coord2D) {
+    this.topLeft = topLeft;
+  }
+
+  public setDimension(dimension: Dimension2D) {
+    this.dimension = dimension;
+  }
 }