Checking if two shapes collide in TypeScript (double dispatch)

Question

Basically, I'm trying to create a generic way to check if two shapes are colliding.

I think this is kind of a "double-dispatch" problem, but I'm unsure if there is a better way to solve it in Typescript / Javascript. This is the best I could come up with. Just assume the static helper functions are defined.

abstract class Shape {
  abstract collidesWith(shape: Shape): boolean;
}

class Circle extends Shape {
  constructor(public x = 0, public y = 0, public r = 0) {
    super();
  }

  collidesWith(shape: Shape) {
    let circle = shape as Circle;
    if (circle instanceof Circle) { 
      return Helpers.circlesCollide(this.x, this.y, this.r, circle.x, circle.y, circle.r);
    }

    let line = shape as LineSegment;
    if (line instanceof LineSegment) {
      return Helpers.lineIntersectsCircle(line.sX, line.sY, line.eX, line.eY, this.x, this.y, this.r);
    }

    return false;
  }
}

class LineSegment extends Shape {
  constructor(public sX = 0, public sY = 0, public eX = 0, public eY = 0) {
    super();
  }

  collidesWith(shape: Shape) {
    let line = shape as LineSegment;
    if (line instanceof LineSegment) {
      return Helpers.lineSegmentsIntersect(this.sX, this.sY, this.eX, this.eY, line.sX, line.sY, line.eX, line.eY);
    }

    let circle = shape as Circle;
    if (circle instanceof Circle) {
      return Helpers.lineIntersectsCircle(this.sX, this.sY, this.eX, this.eY, circle.x, circle.y, circle.r);
    }

    return false;
  }
}

I don't really like this solution because there is a decent amount of code-duplication between all the classes. Imagine once rectangles and lines are added. Then again, I also want it to be as performant as possible. Any ideas on how to reduce the repetitiveness of this or increase the performance? Not really a fan of having to use instanceof and casting all over the place.

Answer 1

Double dispatch

You can not avoid double dispatch as the collision type is unknown. The only way to avoid the double dispatch is to duplicate the collision tests for each object.

Eg line check line circle and circle would check circle line

collidesWith(shape) { // implement for circle and line
    if (shape instanceof Circle) { 
        /* code */ 
    } else if (shape instanceof Line) { 
        /* code */ 
    } else ... and so on` 

which in effect just hides the dispatch inline.

Language selection

"Then again, I also want it to be as performant as possible. Any ideas on how to reduce the repetitiveness of this or increase the performance?"

Generally typescript can be a little slower depending on the style you use. It is most definitely a more verbose language than JS with the only advantage it has over JS is IDE integration.

For the shortest source and best performance use JS.

Please note I am very anti typescript.

Verbosity

"Not really a fan of having to use instanceof and casting all over the place."

Begs the question "Why use typescript?" if you don't like casting.

Alternative to strong typing / classing

Good JavaScript OO code is polymorphic in nature, you can have as many object types as there are objects yet still have clearly defined behaviors.

• Drop the class syntax as it only limits Object design rather than improves it.

• Use factories to define objects

• Assign inherited properties to extend existing objects rather than build a static prototype chain.

Example

Example source code implementing polymorphic Shape as Point, Line, Circle

• Types are defined as an enum TYPES
• Colliders are defined as named type pairs Colliders
• The object Shape is assign the properties of a shape Point, Line, Circle.
• The object shape has the function collidesWith which check via the two shapes to test type if there is an assigned collider. If so it will call and return the result of the correct collider else false. To avoid duplication the function assumes that circle line collision is identical to line circle collision.
• Included a toString only for illustration and testing.

Notes

• Note that Line references Point p1, and p2 but Circle becomes Point like. This was done partly to illiterate the different ways properties can be acquired and to reduce the complexity of the collision code (collision point line and point circle are very similar)

• NOTE The code may seam longer (verbose) but this is a simple example. Much of the factory's work can be automated.

• NOTE Be aware that property order can be important using this style. Ensure that the property assignments {...obj} do not overwrite type related properties

const TYPES = {
    circle: 1,
    point: 2,
    line: 3,
};

const Colliders = {
    circleCircle(circle) { return circle.distFrom(this) <= circle.radius + this.radius },
    circlePoint(p) { return p.distFrom(this) <= this.radius },
    pointPoint(p) { return this.distFrom(p) < 0.5 },
    circleLine(line) {
        const v = line.asVec();
        const p1 = line.p1;
        const u = Math.max(0, Math.min(1, ((this.x - p1.x) * v.x + (this.y - p1.y) * v.y) / (v.y * v.y + v.x * v.x)));
        return (((p1.x + v.x * u) - this.x) ** 2 + ((p1.y + v.y * u) - this.y) ** 2) ** 0.5 < (this.radius ?? 0.5);
    },
    lineLine(line) { return false }, // todo 
};

function Point(x, y) {
    const API = {
        distFrom(p) { return ((p.x - this.x) ** 2 +  (p.y - this.y) ** 2) ** 0.5; },
        x, y,
        toString() { return "Point: {x: " + this.x + ", y: " + this.y + "}" },
        type: TYPES.point,
    };
    API.colliders = {
        [TYPES.point]: Colliders.pointPoint.bind(API),
        [TYPES.line]: Colliders.circleLine.bind(API),
    };
    return API;
}
function Line(p1, p2) {
    const API = {
        asVec(v = Point()) {
            v.x = p2.x - p1.x;
            v.y = p2.y - p1.y;
            return v;
        },
        p1, p2,
        toString() { return "Line : {p1: " + this.p1 + ", p2: " + this.p2 + "}" },
        type: TYPES.line,        
    };
    API.colliders = { [TYPES.line]: Colliders.lineLine.bind(API) };
    return API;
}
function Circle(center, radius) {
    const API = {
        ...Point(center.x, center.y),   // makes circle Point like
        radius,
        toString() { return "Circle: {x: " + this.x + ", y: " + this.y + ", r: " + this.radius + "}" },
        type: TYPES.circle,
    };
    API.colliders = {
        [TYPES.circle]: Colliders.circleCircle.bind(API),
        [TYPES.point]: Colliders.circlePoint.bind(API),
        [TYPES.line]: Colliders.circleLine.bind(API),
    };
    return API;
}
function Shape(shape) {
    return {
        collidesWith(cShape) { 
            return this.colliders[cShape.type]?.(cShape) ?? cShape.colliders[this.type]?.(this) ?? false;
        },
        ...shape
    };    
}


//===========================================================================
// TEST

const line = Shape(Line(Point(0,0), Point(100,100)));
const circle1 = Shape(Circle(Point(50, 0), 50));
const circle2 = Shape(Circle(Point(150, 0), 10));
const point = Shape(Point(50,25));

log(line + "");
log(circle1 + "");
log(circle2 + "");
log(point + "");

log("Line collides circle1: " + line.collidesWith(circle1));
log("Point collides circle1: " + point.collidesWith(circle1));
log("Line collides circle2: " + line.collidesWith(circle2));
log("Point collides circle2: " + point.collidesWith(circle2));

log("Circle1 collides line: " + circle1.collidesWith(line));
log("Circle1 collides point: " + circle1.collidesWith(point));
log("Circle2 collides line: " + circle2.collidesWith(line));
log("Circle2 collides point: " + circle2.collidesWith(point));


function log(...a) { console.log(...a) }