A messy first-attempt approach at creating swept/shapecast AABB colliders in excalibur

minkowski.ts

import {
  vec,
  Vector,
} from 'excalibur';

/**
 * sweeps a polygon p along another polygon q by using minkowski to sum the two polygons.
 * @param p the first polygon
 * @param q the second polygon
 */
function minkowski(p: Vector[], q: Vector[]): Vector[] {
  if (p.length === 0 || q.length === 0) {
    throw 'Both polygons must have at least one vertex';
  }

  // Ensure cyclic ordering by finding the vertex with the lowest y-coordinate (and lowest x if tied)
  const findStartingVertex = (polygon: Vector[]) => {
    const { index } = polygon.reduce(
      (acc, cur, index) => {
        if (!acc.vertex || cur.y < acc.vertex.y) {
          return { index, vertex: cur };
        } else if (cur.y === acc.vertex.y && cur.x < acc.vertex.x) {
          return { index, vertex: cur };
        }
        return acc;
      },
      { index: 0, vertex: polygon[0] },
    );
    return index;
  };

  const startP = findStartingVertex(p);
  const startQ = findStartingVertex(q);

  const cyclicNext = (index, length) => (index + 1) % length;

  const result: Vector[] = [];
  let i = startP;
  let j = startQ;

  /**
   * safety mechanism to guarantee no runaway while loop. It should never run
   * more than p.length + q.length times, as by then all vertices should have been covered
   */
  let cap = 0;

  do {
    result.push(p[i].clone().add(q[j]));

    const edgeP: Vector = p[cyclicNext(i, p.length)].clone().sub(p[i]);
    const edgeQ: Vector = q[cyclicNext(j, q.length)].clone().sub(q[j]);

    const cross = edgeP.cross(edgeQ);

    if (cross > 0) {
      i = cyclicNext(i, p.length);
    } else if (cross < 0) {
      j = cyclicNext(j, q.length);
    } else {
      i = cyclicNext(i, p.length);
      j = cyclicNext(j, q.length);
    }
    cap++;
  } while ((i !== startP || j !== startQ) && cap < p.length + q.length);

  return result;
}


/**
 * sample usage:
 * 1. compute the 'projected' distance traveled. in this example I achieved this by using the velocity
 * and the update timestep to compute the pixel distance traveled.
 * 2. invoke the `minkowski` function with your 'square' hitbox and a 'polygon' represented by the velocity vector and the origin
 * 3. use the resulting Vector array to set your collider's geometry
 *
 * const projection = this.vel.clone().scaleEqual((elapsed / 1000) * 2);
 * collider.set(
 *       Shape.Polygon(minkowski(this.collider.get().points, [vec(0, 0), projection])),
 *     );
 */