summaryrefslogtreecommitdiff
path: root/engine
diff options
context:
space:
mode:
Diffstat (limited to 'engine')
-rw-r--r--engine/components/BoundingBox.ts33
-rw-r--r--engine/entities/Floor.ts5
-rw-r--r--engine/entities/Player.ts7
-rw-r--r--engine/structures/Grid.ts97
-rw-r--r--engine/structures/QuadTree.ts41
-rw-r--r--engine/structures/RefreshingCollisionFinderBehavior.ts14
-rw-r--r--engine/structures/index.ts2
-rw-r--r--engine/systems/Collision.ts73
8 files changed, 205 insertions, 67 deletions
diff --git a/engine/components/BoundingBox.ts b/engine/components/BoundingBox.ts
index 19967f7..26b404d 100644
--- a/engine/components/BoundingBox.ts
+++ b/engine/components/BoundingBox.ts
@@ -17,6 +17,25 @@ export class BoundingBox extends Component {
// https://en.wikipedia.org/wiki/Hyperplane_separation_theorem
public isCollidingWith(box: BoundingBox): boolean {
+ if (this.rotation == 0 && box.rotation == 0) {
+ const thisTopLeft = this.getTopLeft();
+ const thisBottomRight = this.getBottomRight();
+
+ const thatTopLeft = box.getTopLeft();
+ const thatBottomRight = box.getBottomRight();
+
+ if (
+ thisBottomRight.x <= thatTopLeft.x ||
+ thisTopLeft.x >= thatBottomRight.x ||
+ thisBottomRight.y <= thatTopLeft.y ||
+ thisTopLeft.y >= thatBottomRight.y
+ ) {
+ return false;
+ }
+
+ return true;
+ }
+
const boxes = [this.getVertices(), box.getVertices()];
for (const poly of boxes) {
for (let i = 0; i < poly.length; i++) {
@@ -83,4 +102,18 @@ export class BoundingBox extends Component {
height: Math.abs(width * Math.cos(rads) + height * Math.sin(rads)),
};
}
+
+ public getTopLeft(): Coord2D {
+ return {
+ x: this.center.x - this.dimension.width / 2,
+ y: this.center.y - this.dimension.height / 2,
+ };
+ }
+
+ public getBottomRight(): Coord2D {
+ return {
+ x: this.center.x + this.dimension.width / 2,
+ y: this.center.y + this.dimension.height / 2,
+ };
+ }
}
diff --git a/engine/entities/Floor.ts b/engine/entities/Floor.ts
index 44587e6..b204ce0 100644
--- a/engine/entities/Floor.ts
+++ b/engine/entities/Floor.ts
@@ -23,7 +23,10 @@ export class Floor extends Entity {
this.addComponent(
new BoundingBox(
- { x: 300, y: 300 },
+ {
+ x: 300,
+ y: 300,
+ },
{ width, height: Floor.spriteSpec.height },
),
);
diff --git a/engine/entities/Player.ts b/engine/entities/Player.ts
index eeddd69..377e0ca 100644
--- a/engine/entities/Player.ts
+++ b/engine/entities/Player.ts
@@ -18,7 +18,7 @@ import { Direction } from "../interfaces";
export class Player extends Entity {
private static MASS: number = 10;
- private static MOI: number = 1000;
+ private static MOI: number = 100;
private static spriteSpec: SpriteSpec = SPRITE_SPECS.get(
Sprites.COFFEE,
@@ -29,7 +29,10 @@ export class Player extends Entity {
this.addComponent(
new BoundingBox(
- { x: 300, y: 100 },
+ {
+ x: 300,
+ y: 100,
+ },
{ width: Player.spriteSpec.width, height: Player.spriteSpec.height },
0,
),
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";
diff --git a/engine/systems/Collision.ts b/engine/systems/Collision.ts
index e05aba0..2dd920e 100644
--- a/engine/systems/Collision.ts
+++ b/engine/systems/Collision.ts
@@ -8,58 +8,49 @@ import {
Forces,
} from "../components";
import { Game } from "../Game";
-import { PhysicsConstants } from "../config";
+import { Miscellaneous, PhysicsConstants } from "../config";
import { Entity } from "../entities";
import type { Coord2D, Dimension2D, Velocity2D } from "../interfaces";
-import { QuadTree, BoxedEntry } from "../structures";
+import { BoxedEntry, RefreshingCollisionFinderBehavior } from "../structures";
export class Collision extends System {
private static readonly COLLIDABLE_COMPONENT_NAMES = [
ComponentNames.Collide,
ComponentNames.TopCollidable,
];
- private static readonly QUADTREE_MAX_LEVELS = 10;
- private static readonly QUADTREE_SPLIT_THRESHOLD = 10;
- private quadTree: QuadTree;
+ private collisionFinder: RefreshingCollisionFinderBehavior;
- constructor(screenDimensions: Dimension2D) {
+ constructor(refreshingCollisionFinder: RefreshingCollisionFinderBehavior) {
super(SystemNames.Collision);
- this.quadTree = new QuadTree(
- { x: 0, y: 0 },
- screenDimensions,
- Collision.QUADTREE_MAX_LEVELS,
- Collision.QUADTREE_SPLIT_THRESHOLD,
- );
+ this.collisionFinder = refreshingCollisionFinder;
}
public update(_dt: number, game: Game) {
- // rebuild the quadtree
- this.quadTree.clear();
+ this.collisionFinder.clear();
- const entitiesToAddToQuadtree: Entity[] = [];
+ const entitiesToAddToCollisionFinder: Entity[] = [];
Collision.COLLIDABLE_COMPONENT_NAMES.map((componentName) =>
game.forEachEntityWithComponent(componentName, (entity) => {
if (!entity.hasComponent(ComponentNames.BoundingBox)) {
return;
}
- entitiesToAddToQuadtree.push(entity);
+ entitiesToAddToCollisionFinder.push(entity);
}),
);
- this.insertEntitiesInQuadTreeAndUpdateBounds(entitiesToAddToQuadtree);
-
- this.findCollidingEntitiesAndCollide(entitiesToAddToQuadtree, game);
+ this.insertEntitiesAndUpdateBounds(entitiesToAddToCollisionFinder);
+ this.findCollidingEntitiesAndCollide(entitiesToAddToCollisionFinder, game);
}
- private insertEntitiesInQuadTreeAndUpdateBounds(entities: Entity[]) {
+ private insertEntitiesAndUpdateBounds(entities: Entity[]) {
+ const collisionFinderInsertions: BoxedEntry[] = [];
+
const topLeft: Coord2D = { x: Infinity, y: Infinity };
const bottomRight: Coord2D = { x: -Infinity, y: -Infinity };
- const quadTreeInsertions: BoxedEntry[] = [];
-
entities.forEach((entity) => {
const boundingBox = entity.getComponent<BoundingBox>(
ComponentNames.BoundingBox,
@@ -71,21 +62,15 @@ export class Collision extends System {
}
const { center } = boundingBox;
- const topLeftBoundingBox = {
- x: center.x - dimension.width / 2,
- y: center.y - dimension.height / 2,
- };
- const bottomRightBoundingBox = {
- x: center.x + dimension.width / 2,
- y: center.y + dimension.height / 2,
- };
+ const topLeftBoundingBox = boundingBox.getTopLeft();
+ const bottomRightBoundingBox = boundingBox.getBottomRight();
topLeft.x = Math.min(topLeftBoundingBox.x, topLeft.x);
topLeft.y = Math.min(topLeftBoundingBox.y, topLeft.y);
bottomRight.x = Math.max(bottomRightBoundingBox.x, bottomRight.x);
- bottomRight.y = Math.min(bottomRightBoundingBox.y, bottomRight.y);
+ bottomRight.y = Math.max(bottomRightBoundingBox.y, bottomRight.y);
- quadTreeInsertions.push({
+ collisionFinderInsertions.push({
id: entity.id,
dimension,
center,
@@ -94,16 +79,16 @@ export class Collision extends System {
// set bounds first
if (entities.length > 0) {
- this.quadTree.setTopLeft(topLeft);
- this.quadTree.setDimension({
+ this.collisionFinder.setTopLeft(topLeft);
+ this.collisionFinder.setDimension({
width: bottomRight.x - topLeft.x,
height: bottomRight.y - topLeft.y,
});
}
// then, begin insertions
- quadTreeInsertions.forEach((boxedEntry: BoxedEntry) =>
- this.quadTree.insert(boxedEntry),
+ collisionFinderInsertions.forEach((boxedEntry: BoxedEntry) =>
+ this.collisionFinder.insert(boxedEntry),
);
}
@@ -181,15 +166,13 @@ export class Collision extends System {
ComponentNames.BoundingBox,
);
- const neighborIds = this.quadTree
- .getNeighborIds({
- id: entity.id,
- dimension: boundingBox.dimension,
- center: boundingBox.center,
- })
- .filter((neighborId) => neighborId != entity.id);
+ const neighborIds = this.collisionFinder.getNeighborIds({
+ id: entity.id,
+ dimension: boundingBox.dimension,
+ center: boundingBox.center,
+ });
- neighborIds.forEach((neighborId) => {
+ for (const neighborId of neighborIds) {
const neighbor = game.getEntity(neighborId);
if (!neighbor) return;
@@ -200,7 +183,7 @@ export class Collision extends System {
if (boundingBox.isCollidingWith(neighborBoundingBox)) {
collidingEntityIds.push([entity.id, neighborId]);
}
- });
+ }
}
return collidingEntityIds;
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-21 20:16:22 +0000