Movement and collision system/engine

Show Your Work
#1

I’ve decided to start work on a movement and collision system, where the user has to implement minimal code.

I want to make the first parts of making a game in Wick easier for everyone.

(It will also have good collision detection )

Plans
Have an initialization function that sets up a wall list automatically (based on clip names) (and maybe settings? such as changing hitTestOptions, momentum settings, max collision iterations, etc.)

A single function that can be added to a clip to make it a player/moving object (and custom controls for each clip)

Actual documentation / useful comments

Possibly a layer system (although it would be pretty difficult to make it good)

Also, if anyone has any ideas, suggestions, or feedback, feel free to do so.

2 Likes
#2

I realized that I forgot the most important thing in the plans:

To come up with a cool name for the engine

1 Like
#3

I’ve decided to just call it DonutEngine

I have a functional demo for the library. You move with WASD and can change the speed in the player’s default script. Walls are automatically added to a wall list.

DonutEngine_v0.0.2.wick (4.0 KB)

1 Like
#4

Ok, so I’m having a problem.

the “convexHits” function (which is the function used by the .hits() function if the project.hitTestOptions.mode is set to "CONVEX") will not work if the main clip (the one placed before the function) is rectangular. It just returns NaN.

The code for convexHits if you wanna see it 
convexHits(other, options) {
    // Efficient check first
    let bounds1 = this.absoluteBounds;
    let bounds2 = other.absoluteBounds; // TODO: write intersects so we don't rely on paper Rectangle objects

    if (!bounds1.intersects(bounds2)) {
      return null;
    }

    let c1 = bounds1.center;
    let c2 = bounds2.center; // clockwise arrays of points in format [[x1, y1], [x2, y2], ...]

    let hull1 = this.convexHull;
    let hull2 = other.convexHull;
    let finished1 = false;
    let finished2 = false;
    let i1 = hull1.length - 1;
    let i2 = hull2.length - 1;
    let intersections = [];
    let n = 0; // Algorithm from https://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring17/Lectures/cg-convexintersection.pdf

    while ((!finished1 || !finished2) && n <= 2 * (hull1.length + hull2.length)) {
      n++; // line segments A is ab, B is cd

      let a = hull1[i1],
          b = hull1[((i1 - 1) % hull1.length + hull1.length) % hull1.length],
          c = hull2[i2],
          d = hull2[((i2 - 1) % hull2.length + hull2.length) % hull2.length]; //Use parametric line intersection
      //<x,y> = a + (b - a)t1
      //<x,y> = c + (d - c)t2
      //a + (b - a)t1 = c + (d - c)t2
      //t1 = (c.x + (d.x - c.x)t2 - a.x) / (b.x - a.x)
      //a.y + (b.y - a.y) * (c.x + (d.x - c.x)t2 - a.x) / (b.x - a.x) = c.y + (d.y - c.y)t2
      //t2((b.y - a.y)(d.x - c.x)/(b.x - a.x) - (d.y - c.y)) = c.y - a.y - (b.y - a.y)*(c.x - a.x)/(b.x - a.x)
      //t2 = (c.y - a.y - (b.y - a.y)*(c.x - a.x)/(b.x - a.x))  /  ((b.y - a.y)(d.x - c.x)/(b.x - a.x) - (d.y - c.y))

      let t2 = (c[1] - a[1] - (b[1] - a[1]) * (c[0] - a[0]) / (b[0] - a[0])) / ((b[1] - a[1]) * (d[0] - c[0]) / (b[0] - a[0]) - d[1] + c[1]);
      let t1 = (c[0] + (d[0] - c[0]) * t2 - a[0]) / (b[0] - a[0]);

      if (0 <= t1 && t1 <= 1 && 0 <= t2 && t2 <= 1) {
        intersections.push({
          x: a[0] + (b[0] - a[0]) * t1,
          y: a[1] + (b[1] - a[1]) * t1
        });
      }

      let APointingToB = t1 > 1;
      let BPointingToA = t2 > 1;

      if (BPointingToA && !APointingToB) {
        // Advance B
        i2 -= 1;

        if (i2 < 0) {
          finished2 = true;
          i2 += hull2.length;
        }
      } else if (APointingToB && !BPointingToA) {
        // Advance A
        i1 -= 1;

        if (i1 < 0) {
          finished1 = true;
          i1 += hull1.length;
        }
      } else {
        // Advance outside
        if (this.cw(a[0], a[1], b[0], b[1], d[0], d[1])) {
          // Advance B
          i2 -= 1;

          if (i2 < 0) {
            finished2 = true;
            i2 += hull2.length;
          }
        } else {
          // Advance A
          i1 -= 1;

          if (i1 < 0) {
            finished1 = true;
            i1 += hull1.length;
          }
        }
      }
    } // Ok, we have all the intersections now


    let avgIntersection = {
      x: 0,
      y: 0
    };

    if (intersections.length === 0) {
      avgIntersection.x = bounds1.width < bounds2.width ? c1.x : c2.x;
      avgIntersection.y = bounds1.width < bounds2.width ? c1.y : c2.y;
    } else {
      for (let i = 0; i < intersections.length; i++) {
        avgIntersection.x += intersections[i].x;
        avgIntersection.y += intersections[i].y;
      }

      avgIntersection.x /= intersections.length;
      avgIntersection.y /= intersections.length;
    }

    let result = {};

    if (options.intersections) {
      result.intersections = intersections;
    }

    if (options.offset) {
      // Calculate offset by taking the center of mass of the intersection, call it P,
      // get the radius from P on this convex hull in the direction
      // from this center to that center,
      // Then, the offset is a vector in the direction from that center to this center
      // with magnitude of that radius
      let targetTheta = Math.atan2(c2.y - c1.y, c2.x - c1.x); //from c1 to c2

      let r = this.radiusAtPointInDirection(hull1, avgIntersection, targetTheta);
      targetTheta = (targetTheta + Math.PI) % (2 * Math.PI);
      r += this.radiusAtPointInDirection(hull2, avgIntersection, targetTheta);
      let directionX = c1.x - c2.x;
      let directionY = c1.y - c2.y;
      let mag = Math.sqrt(directionX * directionX + directionY * directionY);
      directionX *= r / mag;
      directionY *= r / mag;
      result.offsetX = directionX;
      result.offsetY = directionY;
    }

    if (options.overlap) {
      //same as offset except instead of center to center, 
      //we will move perpendicular to the best fit line
      //of the intersection points
      let directionX, directionY;

      if (intersections.length < 2) {
        directionX = c2.x - c1.x;
        directionY = c2.y - c1.y;
      } else {
        let max_d = 0;

        for (let i = 1; i < intersections.length; i++) {
          let d = (intersections[i].y - intersections[0].y) * (intersections[i].y - intersections[0].y) + (intersections[i].x - intersections[0].x) * (intersections[i].x - intersections[0].x);

          if (d > max_d) {
            max_d = d;
            directionX = -(intersections[i].y - intersections[0].y);
            directionY = intersections[i].x - intersections[0].x;

            if (directionX * (c1.x - avgIntersection.x) + directionY * (c1.y - avgIntersection.y) > 0) {
              directionX = -directionX;
              directionY = -directionY;
            }
          }
        }
      }

      let targetTheta = Math.atan2(directionY, directionX);
      let r = this.radiusAtPointInDirection(hull1, avgIntersection, targetTheta);
      targetTheta = (targetTheta + Math.PI) % (2 * Math.PI);
      r += this.radiusAtPointInDirection(hull2, avgIntersection, targetTheta);
      let r2 = this.radiusAtPointInDirection(hull1, avgIntersection, targetTheta);
      targetTheta = (targetTheta + Math.PI) % (2 * Math.PI);
      r2 += this.radiusAtPointInDirection(hull2, avgIntersection, targetTheta);

      if (r2 < r) {
        r = r2;
        directionX *= -1;
        directionY *= -1;
      }

      let mag = Math.sqrt(directionX * directionX + directionY * directionY);
      directionX *= -r / mag;
      directionY *= -r / mag;
      result.overlapX = directionX;
      result.overlapY = directionY;
    }

    return result;
  }
#5

I have narrowed down the problem further.
It’s a problem with the radiusAtPointInDirection function (which is used to calculate convex overlap magnitude)

The t1 and t2 values are the ones that are causing problems. Basically, what’s happening is that it’s trying to use the difference in x or y values between points for some calculations. (a and b are points on the convex hull). However, with (non-rotated) rectangles/squares, that makes the difference equal to zero, leading to a problem with dividing by zero.

Here's the function's code 
function radiusAtPointInDirection(ch, p, targetTheta) {
    let minThetaDiff = Infinity;
    let index;

    for (let i = 0; i < ch.length; i++) {
      let theta = Math.atan2(ch[i][1] - p.y, ch[i][0] - p.x);
      let thetaDiff = ((targetTheta - theta) % (2 * Math.PI) + 2 * Math.PI) % (2 * Math.PI); //positive mod

      if (thetaDiff < minThetaDiff) {
        minThetaDiff = thetaDiff;
        index = i;
      }
    }
    
    let a = ch[index];
    let b = ch[(index + 1) % ch.length];
    let c = [p.x, p.y];
    let d = [p.x + 100 * Math.cos(targetTheta), p.y + 100 * Math.sin(targetTheta)]; //Use parametric line intersection
    
    
    //<x,y> = a + (b - a)t1
    //<x,y> = c + (d - c)t2
    //a + (b - a)t1 = c + (d - c)t2
    //t1 = (c.x + (d.x - c.x)t2 - a.x) / (b.x - a.x)
    //a.y + (b.y - a.y) * (c.x + (d.x - c.x)t2 - a.x) / (b.x - a.x) = c.y + (d.y - c.y)t2
    //t2((b.y - a.y)(d.x - c.x)/(b.x - a.x) - (d.y - c.y)) = c.y - a.y - (b.y - a.y)*(c.x - a.x)/(b.x - a.x)
    //t2 = (c.y - a.y - (b.y - a.y)*(c.x - a.x)/(b.x - a.x))  /  ((b.y - a.y)(d.x - c.x)/(b.x - a.x) - (d.y - c.y))

    
    let t2 = (c[1] - a[1] - (b[1] - a[1]) * (c[0] - a[0]) / (b[0] - a[0])) / ((b[1] - a[1]) * (d[0] - c[0]) / (b[0] - a[0]) - d[1] + c[1]);
    let t1 = (c[0] + (d[0] - c[0]) * t2 - a[0]) / (b[0] - a[0]);

    return Math.hypot(a[0] + (b[0] - a[0]) * t1 - p.x, a[1] + (b[1] - a[1]) * t1 - p.y);
  }
#6

As it turns out, there’s actually another issue. Specifically for vertical collisions, the intersections list will not have any values in it. Since convex overlap values use the intersections, this also causes a problem for that.

Convex calculations do not like vertical / horizontal lines