increase collision performance _heavily_

4 files changed, 135 insertions, 19 deletions

diff --git a/engine/structures/Grid.ts b/engine/structures/Grid.ts
new file mode 100644
index 0000000..d359909
--- /dev/null
+++ b/engine/structures/Grid.ts
@@ -0,0 +1,97 @@
+import type { Coord2D, Dimension2D } from "../interfaces";
+import type { RefreshingCollisionFinderBehavior } from ".";
+
+export class Grid implements RefreshingCollisionFinderBehavior {
+  private cellEntities: Map<number, string[]>;
+
+  private gridDimension: Dimension2D;
+  private cellDimension: Dimension2D;
+  private topLeft: Coord2D;
+
+  constructor(
+    gridDimension: Dimension2D,
+    cellDimension: Dimension2D,
+    topLeft = { x: 0, y: 0 },
+  ) {
+    this.gridDimension = gridDimension;
+    this.cellDimension = cellDimension;
+    this.topLeft = topLeft;
+
+    this.cellEntities = new Map();
+  }
+
+  public insert(boxedEntry: BoxedEntry) {
+    this.getOverlappingCells(boxedEntry).forEach((gridIdx) => {
+      if (!this.cellEntities.has(gridIdx)) {
+        this.cellEntities.set(gridIdx, []);
+      }
+      this.cellEntities.get(gridIdx).push(boxedEntry.id);
+    });
+  }
+
+  public getNeighborIds(boxedEntry: BoxedEntry): Set<string> {
+    const neighborIds: Set<string> = new Set();
+    this.getOverlappingCells(boxedEntry).forEach((gridIdx) => {
+      if (this.cellEntities.has(gridIdx)) {
+        this.cellEntities.get(gridIdx).forEach((id) => neighborIds.add(id));
+      }
+    });
+    return neighborIds;
+  }
+
+  public clear() {
+    this.cellEntities.clear();
+  }
+
+  public setTopLeft(topLeft: Coord2D) {
+    this.topLeft = topLeft;
+  }
+
+  public setDimension(dimension: Dimension2D) {
+    this.gridDimension = dimension;
+  }
+
+  public setCellDimension(cellDimension: Dimension2D) {
+    this.cellDimension = cellDimension;
+  }
+
+  private getOverlappingCells(boxedEntry: BoxedEntry): number[] {
+    const { center, dimension } = boxedEntry;
+    const yBoxes = Math.ceil(
+      this.gridDimension.height / this.cellDimension.height,
+    );
+    const xBoxes = Math.ceil(
+      this.gridDimension.width / this.cellDimension.width,
+    );
+
+    const translated: Coord2D = {
+      y: center.y - this.topLeft.y,
+      x: center.x - this.topLeft.x,
+    };
+
+    const topLeftBox = {
+      x: Math.floor(
+        (translated.x - dimension.width / 2) / this.cellDimension.width,
+      ),
+      y: Math.floor(
+        (translated.y - dimension.height / 2) / this.cellDimension.height,
+      ),
+    };
+    const bottomRightBox = {
+      x: Math.floor(
+        (translated.x + dimension.width / 2) / this.cellDimension.width,
+      ),
+      y: Math.floor(
+        (translated.y + dimension.height / 2) / this.cellDimension.height,
+      ),
+    };
+
+    const cells: number[] = [];
+
+    for (let y = topLeftBox.y; y <= bottomRightBox.y; ++y)
+      for (let x = topLeftBox.x; x <= bottomRightBox.x; ++x)
+        cells.push(yBoxes * y + x);
+
+    return cells;
+  }
+}
diff --git a/engine/structures/QuadTree.ts b/engine/structures/QuadTree.ts
index e6e29fa..90227a0 100644
--- a/engine/structures/QuadTree.ts
+++ b/engine/structures/QuadTree.ts
@@ -1,10 +1,5 @@
 import type { Coord2D, Dimension2D } from "../interfaces";
-
-export interface BoxedEntry {
-  id: string;
-  dimension: Dimension2D;
-  center: Coord2D;
-}
+import type { BoxedEntry, RefreshingCollisionFinderBehavior } from ".";
 
 enum Quadrant {
   I,
@@ -13,7 +8,14 @@ enum Quadrant {
   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,18 +26,18 @@ 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;
@@ -45,7 +47,7 @@ export class QuadTree {
     if (this.hasChildren()) {
       this.getQuadrants(boxedEntry).forEach((quadrant) => {
         const quadrantBox = this.children.get(quadrant);
-        quadrantBox?.insert(boxedEntry);
+        quadrantBox!.insert(boxedEntry);
       });
       return;
     }
@@ -73,15 +75,16 @@ export class QuadTree {
   }
 
   public getNeighborIds(boxedEntry: BoxedEntry): string[] {
-    const neighbors: string[] = this.objects.map(({ id }) => id);
+    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));
       });
     }
 
@@ -158,9 +161,9 @@ export class QuadTree {
 
   private realignObjects(): void {
     this.objects.forEach((boxedEntry) => {
-      this.getQuadrants(boxedEntry).forEach((direction) => {
-        const quadrant = this.children.get(direction);
-        quadrant?.insert(boxedEntry);
+      this.getQuadrants(boxedEntry).forEach((quadrant) => {
+        const quadrantBox = this.children.get(quadrant);
+        quadrantBox!.insert(boxedEntry);
       });
     });
 
diff --git a/engine/structures/RefreshingCollisionFinderBehavior.ts b/engine/structures/RefreshingCollisionFinderBehavior.ts
new file mode 100644
index 0000000..21d690d
--- /dev/null
+++ b/engine/structures/RefreshingCollisionFinderBehavior.ts
@@ -0,0 +1,14 @@
+import type { Coord2D, Dimension2D } from "../interfaces";
+
+export interface BoxedEntry {
+  id: string;
+  dimension: Dimension2D;
+  center: Coord2D;
+}
+
+export interface RefreshingCollisionFinderBehavior {
+  public clear(): void;
+  public insert(boxedEntry: BoxedEntry): void;
+  public getNeighborIds(boxedEntry: BoxedEntry): Set<string>;
+  public setTopLeft(topLeft: Coord2d): void;
+}
diff --git a/engine/structures/index.ts b/engine/structures/index.ts
index 605a82a..49a84af 100644
--- a/engine/structures/index.ts
+++ b/engine/structures/index.ts
@@ -1 +1,3 @@
+export * from "./RefreshingCollisionFinderBehavior";
 export * from "./QuadTree";
+export * from "./Grid";