summaryrefslogtreecommitdiff
path: root/engine/structures
diff options
context:
space:
mode:
Diffstat (limited to 'engine/structures')
-rw-r--r--engine/structures/Grid.ts104
-rw-r--r--engine/structures/QuadTree.ts97
-rw-r--r--engine/structures/RefreshingCollisionFinderBehavior.ts14
-rw-r--r--engine/structures/index.ts4
4 files changed, 173 insertions, 46 deletions
diff --git a/engine/structures/Grid.ts b/engine/structures/Grid.ts
new file mode 100644
index 0000000..5f0e053
--- /dev/null
+++ b/engine/structures/Grid.ts
@@ -0,0 +1,104 @@
+import type { Coord2D, Dimension2D } from '../interfaces';
+import type { BoxedEntry, RefreshingCollisionFinderBehavior } from '.';
+import { Miscellaneous } from '../config/constants';
+
+export class Grid implements RefreshingCollisionFinderBehavior {
+ private cellEntities: Map<number, string[]>;
+
+ private gridDimension: Dimension2D;
+ private cellDimension: Dimension2D;
+ private topLeft: Coord2D;
+
+ constructor(
+ gridDimension: Dimension2D = {
+ width: Miscellaneous.WIDTH,
+ height: Miscellaneous.HEIGHT
+ },
+ cellDimension: Dimension2D = {
+ width: Miscellaneous.DEFAULT_GRID_WIDTH,
+ height: Miscellaneous.DEFAULT_GRID_HEIGHT
+ },
+ 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 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;
+ }
}
diff --git a/engine/structures/RefreshingCollisionFinderBehavior.ts b/engine/structures/RefreshingCollisionFinderBehavior.ts
new file mode 100644
index 0000000..573ddd8
--- /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 {
+ clear(): void;
+ insert(boxedEntry: BoxedEntry): void;
+ getNeighborIds(boxedEntry: BoxedEntry): Set<string>;
+ setTopLeft(topLeft: Coord2D): void;
+}
diff --git a/engine/structures/index.ts b/engine/structures/index.ts
index 605a82a..679dbd4 100644
--- a/engine/structures/index.ts
+++ b/engine/structures/index.ts
@@ -1 +1,3 @@
-export * from "./QuadTree";
+export * from './RefreshingCollisionFinderBehavior';
+export * from './QuadTree';
+export * from './Grid';
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-21 18:21:57 +0000