So I’ve been working on a js game engine, and as a part of that I’ve also been working on line vs line collision detection.
In my engine colliders are implementing an IGNCollider interface, which requires the checkCollisionWith(...colliders) method.
The following is the GNLineCollider class:
class GNLineCollider extends IGNCollider {
/**
* @param {Object} params
* @param {Vec2D} params.p1
* @param {Vec2D} params.p2
*/
constructor({ p1, p2, ...args }) {
super(args);
this.p1 = p1;
this.p2 = p2;
}
checkCollisionWith(...colliders) {
for (const collider of colliders) {
if (collider instanceof GNLineCollider) {
const collision = checkLineVsLineCollision(
this,
collider
);
if (!collision.collision) continue;
return {
collision: true,
collider: collision.colliders[1],
normal: collision.normal,
};
}
}
return { collision: false };
}
}
And this is the checkLineVsLineCollision function it calles:
checkLineVsLineCollision(line1Points, line2Points) {
/*
For line AB which goes through A(x, y), B(X, Y), the equation is:
ax + by = c
Such that:
a = Y - y
b = x - X
c = ax + by
For two lines of form ax + by = c that intersect at P(x,y), we shall find their intersection like so:
1) ax + by = c *B
2) Ax + By = C *b
1) Bax + bBy = Bc
2) bAx + bBy = bC
1-2) (Ba - bA)x = Bc - bC
Bc - bC
x = โโโโโโโ
Ba - bA
1) ax + by = c *A
2) Ax + By = C *a
1) aAx + Aby = Ac
2) aAx + aBy = aC
1-2) (Ab - aB)y = Ac - aC
Ac - aC
y = โโโโโโโ
Ab - aB
โญ Bc - bC Ac - aC โฎ
P | โโโโโโโ โโโโโโโ |
โฐ aB - Ab , Ab - aB โฏ
*/
const { a, b, c } = findLineEquation(line1Points);
const { a: A, b: B, c: C } = findLineEquation(line2Points);
if (a * B == A * b) return { collision: false };
const P = new Vec2D(
(B * c - b * C) / (a * B - A * b),
(A * c - a * C) / (A * b - B * a)
);
if (
between({
val: P.x,
min: line1Points.p1.x,
max: line1Points.p2.x,
matchMinMax: true,
equalsMinMax: true,
}) &&
between({
val: P.y,
min: line1Points.p1.y,
max: line1Points.p2.y,
matchMinMax: true,
equalsMinMax: true,
}) &&
between({
val: P.x,
min: line2Points.p1.x,
max: line2Points.p2.x,
matchMinMax: true,
equalsMinMax: true,
}) &&
between({
val: P.y,
min: line2Points.p1.y,
max: line2Points.p2.y,
matchMinMax: true,
equalsMinMax: true,
})
)
return {
collision: true,
colliders: [line1, line2],
normal: line1.p1
.sub(line1.p2)
.sub(line2.p1.sub(line2.p2))
.normalize(),
};
return { collision: false };
}
I’ve also made a GNColliderGroup class, which also implements the IGNCollider interface, and is meant to have other colliders as it’s children, and then be able to check collisions with all of them when the checkCollisionsWith function is called, like so:
export class GNColliderGroup extends IGNCollider {
/**
* @param {...IGNCollider} colliders
*/
checkCollisionWith(...colliders) {
// This function can get all of the colliders which are children of the current collider.
const subColliders = this.getChildrenOfType(IGNCollider);
for (const collider of subColliders) {
const collision = collider.checkCollisionWith(...colliders);
if (!collision.collision) continue;
return collision;
}
return { collision: false };
}
}
I’ve then made a test scene with a player and a floor. Where both of them are instences of the GNColliderGroup class, so that they can have multiple line colliders as their children. And the update function for the player looks like this:
update({ deltaTime }) {
this.velocity.y += 0.004 * deltaTime;
// Originally there was some irrelevant movement code here which I removed
for (const axis of ['x', 'y']) {
this.transform.position[axis] +=
this.velocity[axis] * deltaTime;
const collider = floor;
if (!this.checkCollisionWith(collider).collision) continue;
while (this.checkCollisionWith(collider).collision) {
this.transform.position[axis] -= normalize(
this.velocity[axis]
);
}
this.velocity[axis] = 0;
}
super.update({ deltaTime, ...args });
}
But, sometimes I have problem where on some frames the collision detection functions return false on frames where the 2 objects are very clearly intersecting, like you can see in the following video:
https://streamable.com/lpt8dm
(I added lines to the player and the floor which represent the collision lines, and made it so the lines of the player turn red whenever they detect a collision).
In addition, here are some of the utility functions I used, for those wondering:
/**
* @param {Object} params
* @param {number} params.val
* @param {number} params.min
* @param {number} params.max
* @param {boolean} params.equalsMinMax - use <=/>= instead of </>.
* @param {boolean} params.matchMinMax - check if min is smaller than max, and if it isn't - switch them.
*/
function between({
val,
min,
max,
equalsMinMax = false,
matchMinMax = false,
}) {
if (matchMinMax && min > max) [max, min] = [min, max];
if (equalsMinMax && (val == min || val == max)) return true;
return min < val && val < max;
}
/**
* @param {Object} params
* @param {Vec2D} params.p1
* @param {Vec2D} params.p2
*/
function findLineEquation({ p1, p2 }) {
const a = p2.y - p1.y;
const b = p1.x - p2.x;
const c = a * p1.x + b * p1.y;
return { a, b, c };
}
const normalize = (val) => (val ? val / Math.abs(val) : 0);