Support physic on non-convex shape

[jjhesk]

I have read about the content on wiki which talking about:

Polygon: A custom shape through vertices. The polygon must be convex, and if this condition fails, the shape falls back to a default box. The number of vertices must be greater than or equal to 3 (otherwise, it can't be convex) and less than or equal to 8 (the maximum number of vertices supported per polygon): 3 ≤ Number of vertices ≤ 8.

I think it is possible to calculate custom shape like the moon shape which can save tons of time in work-arounds done by hand.

Found some resources about this solution:
filling technique: https://tronche.com/gui/x/xlib/graphics/filling-areas/XFillPolygon.html

research

from godot documentation
from more discussions

Concave Polygons
Collisions uses the Separating Axis Theorem (SAT) for its narrow-phase collision tests. One caveat to SAT is that it only works properly on convex bodies. However, concave polygons can be "faked" by using a series of Lines. Keep in mind that a polygon drawn using Lines is "hollow".

Handling true concave polygons requires breaking them down into their component convex polygons (Convex Decomposition) and testing them for collisions individually. There are plans to integrate this functionality into the library in the future, but for now, check out poly-decomp.js.

[jjhesk]

@4ian can we make a road map to improve collision polygon with this solution? decompose-polygon ts version

[jjhesk]

Check out the idea and we can start working from this line: https://github.com/4ian/GDevelop/blob/master/Extensions/Physics2Behavior/physics2runtimebehavior.ts#L473-L547

Just need to see how to change it:
https://github.com/4ian/GDevelop/blob/master/Extensions/Physics2Behavior/physics2runtimebehavior.ts#L476-L494

[4ian]

@jjhesk Please rather discuss your ideas on the forum first - I know that you're doing a lot of research but you need to consolidate these and get ideas/feedbacks from other users before posting on GitHub (unfortunately posting multiple links is not super useful by itself - the research needs to be much more precise, or even prototyped if you can :)).
At least, try to consolidate your multiple messages into a single one because I have not a lot of time and having information spread over 3 different replies is not helping. Thanks! :)

[jjhesk]

To create a plugin for GDevelop that calculates a collision polygon for curve shapes to enable collision detection with a circle shape, we need a clear, practical approach that integrates with GDevelop’s framework. The plugin will allow users to define curve shapes (e.g., Bézier curves or other parametric curves) and generate a collision polygon to detect intersections with a circular object. Below, I outline the concept, technical approach, and implementation steps for developing this plugin, leveraging insights from the provided GitHub discussion and relevant collision detection techniques.

Concept Overview

The plugin will:

• Allow users to define a curve shape (e.g., quadratic or cubic Bézier curve) in GDevelop.
• Approximate the curve as a polygon (a series of line segments) for collision detection.
• Detect collisions between this polygon and a circle (representing a game object like a player or projectile).
• Be lightweight to maintain performance, avoiding complex computations like exact curve-circle intersection tests.
• Integrate seamlessly with GDevelop’s event system and object properties.

The GitHub discussion (#3753) highlights issues with GDevelop’s physics engine and resource handling, suggesting that plugins must be robust to avoid errors like missing resources or undefined properties. Thus, the plugin will include error handling and clear documentation.

Technical Approach

1. Curve Representation:

   • Use Bézier curves (quadratic or cubic) as the primary curve type due to their flexibility and familiarity in game development.
   • Allow users to define control points for the curve via GDevelop’s object properties or events.

2. Polygon Approximation:

   • Subdivide the Bézier curve into a series of straight line segments to form a polygon. This simplifies collision detection, as line segment-circle intersections are computationally cheaper than direct curve-circle tests.
   • Use an adaptive subdivision algorithm (e.g., de Casteljau’s algorithm) to ensure the polygon closely approximates the curve while controlling the number of segments for performance.

3. Collision Detection:

   • Implement a circle-polygon collision algorithm where the circle is defined by its center and radius, and the polygon is the approximated curve.
   • For each line segment of the polygon, calculate the closest point to the circle’s center and check if it lies within the circle’s radius.
   • Optimize by using a bounding box or spatial grid to skip segments far from the circle.

4. GDevelop Integration:

   • Create a custom object extension in GDevelop that represents the curve shape.
   • Provide actions to set curve control points and conditions to check for collisions with circle-shaped objects.
   • Ensure compatibility with GDevelop’s rendering pipeline to visualize the curve and its collision polygon during development.

Implementation Steps

Below are the steps to develop the plugin, assuming familiarity with JavaScript (used for GDevelop extensions) and basic collision detection math.

Step 1: Set Up the Plugin

• Create an Extension:
  • Use GDevelop’s extension creation tools to start a new extension (e.g., CurveCollisionExtension).
  • Define a custom object type, CurveShape, to represent the curve.
• Dependencies:
  • No external libraries are required, as GDevelop’s runtime provides basic math utilities, and we’ll implement collision logic manually.
• Error Handling:
  • Based on the GitHub discussion, ensure the plugin checks for valid resources (e.g., curve points) to avoid errors like Cannot read property 'substring' of undefined.

Step 2: Define the Curve Shape

• Properties:
  • Add object properties for the curve, such as:
    • ControlPoints: An array of (x, y) coordinates (e.g., for a cubic Bézier: P0, P1, P2, P3).
    • SegmentCount: Number of line segments for polygon approximation (default: 20).
    • RenderCurve: Boolean to toggle curve visualization in the editor.
• Actions:
  • Create an action `SetControlPoints(x1, y1, x2, y2, ...) to allow users to define the curve via events.
  • Example: SetControlPoints(0, 0, 100, 50, 200, 50, 300, 0) for a cubic Bézier.

Step 3: Approximate the Curve as a Polygon

• Bézier Curve Subdivision:
  • Implement a function to evaluate points on a Bézier curve using de Casteljau’s algorithm or direct parametric equations:
    • For a cubic Bézier with points P0, P1, P2, P3, the position at parameter t (0 ≤ t ≤ 1) is:

      B(t) = (1-t)^3 * P0 + 3(1-t)^2 * t * P1 + 3(1-t) * t^2 * P2 + t^3 * P3
      

    • Generate SegmentCount points by evaluating B(t) at t = 0, 1/SegmentCount, 2/SegmentCount, ..., 1.
  • Connect consecutive points to form line segments, creating a polygon.
• Optimization:
  • Use adaptive subdivision to add more segments in high-curvature areas and fewer in flat areas, balancing accuracy and performance.

Step 4: Implement Circle-Polygon Collision Detection

• Algorithm:
  • For a circle with center C (x_c, y_c) and radius r, and a polygon with line segments [S1, S2, ..., Sn]:
    1. For each segment Si (from point A to B):
       • Find the closest point P on segment Si to C using vector projection:

         t = clamp(((C - A) · (B - A)) / ||B - A||^2, 0, 1)
         P = A + t * (B - A)
         

       • Compute the distance d = ||C - P||.
       • If d ≤ r, the circle intersects the segment (collision detected).
    2. Optionally, check if C is inside the polygon (for closed curves) using a point-in-polygon test (e.g., ray-casting).
• Optimization:
  • Use a bounding box around the polygon to quickly skip collision checks if the circle is far away.
  • Implement a spatial grid to reduce the number of segments checked, especially for long curves.

Step 5: Integrate Collision Detection in GDevelop

• Conditions:
  • Add a condition IsCollidingWithCircle(object, radius) to check if the curve collides with a specified object (assumed to be a circle with the given radius).
  • Example usage in GDevelop events:

    Conditions: CurveShape IsCollidingWithCircle(Player, 10)
    Actions: Do something (e.g., stop player, trigger effect)
    

• Runtime Logic:
  • In the extension’s runtime code, compute the polygon approximation once per frame (or when control points change) and cache it.
  • Evaluate the collision condition by iterating through the polygon segments and applying the circle-polygon algorithm.

Step 6: Visualization and Debugging

• Render the Curve:
  • Use GDevelop’s rendering API to draw the Bézier curve in the editor and game (e.g., using gdjs.RuntimeObject’s draw methods).
  • Optionally draw the collision polygon (line segments) for debugging.
• Debug Tools:
  • Add a property to toggle polygon visualization.
  • Log warnings if control points are invalid or if SegmentCount is too high, impacting performance.

Step 7: Test and Optimize

• Testing:
  • Create a test project in GDevelop with a CurveShape object and a circular player object.
  • Define various curves (e.g., S-shaped, looped, sharp turns) and verify collision detection accuracy.
  • Test edge cases, such as very small or large circles, fast-moving circles, or curves with few segments.
• Optimization:
  • Profile the plugin to ensure it runs efficiently, especially with many curves or high SegmentCount.
  • Reduce segment checks using spatial partitioning (e.g., a grid or quadtree) if performance is an issue.

[jjhesk]

Example Code Snippet (Pseudo-JavaScript)

Below is a simplified example of the collision detection logic, which would be part of the extension’s runtime code:

gdjs.registerObject("CurveCollisionExtension::CurveShape", function(runtimeScene) {
    var CurveShape = function() {
        this.controlPoints = [{x: 0, y: 0}, {x: 100, y: 50}, {x: 200, y: 50}, {x: 300, y: 0}];
        this.segmentCount = 20;
        this.polygon = [];
        this.updatePolygon();
    };

    CurveShape.prototype.updatePolygon = function() {
        this.polygon = [];
        for (var t = 0; t <= 1; t += 1 / this.segmentCount) {
            var point = this.evaluateBezier(t); // Implement Bézier evaluation
            this.polygon.push(point);
        }
    };
CurveShape.prototype.isCollidingWithCircle = function(circleObject, radius) {
    let circleCenter = { x: circleObject.getX(), y: circleObject.getY() };
    
    // Check edge intersections
    for (let i = 0; i < this.polygon.length - (this.isClosed ? 0 : 1); i++) {
        let A = this.polygon[i];
        let B = this.polygon[(i + 1) % this.polygon.length]; // Loop back for closed
        let AB = { x: B.x - A.x, y: B.y - A.y };
        let AC = { x: circleCenter.x - A.x, y: circleCenter.y - A.y };
        let lengthSquared = AB.x * AB.x + AB.y * AB.y;
        let t = Math.max(0, Math.min(1, (AC.x * AB.x + AC.y * AB.y) / lengthSquared));
        let closest = { x: A.x + t * AB.x, y: A.y + t * AB.y };
        let distance = Math.sqrt(
            (circleCenter.x - closest.x) ** 2 + (circleCenter.y - closest.y) ** 2
        );
        if (distance <= radius) return true;
    }
    
    // Check if circle center is inside (for closed polygons)
    if (this.isClosed && isPointInPolygon(circleCenter, this.polygon)) {
        return true;
    }
    
    return false;
};


}

The plugin concept I outlined for GDevelop, which approximates a curve as a polygon for collision detection with a circle, does not inherently support concave polygons in its basic implementation. However, it can be extended to handle concave polygons with additional logic. Below, I explain why concave polygons require special consideration, whether the proposed approach supports them, and how to modify the plugin to include concave polygon support.

Why Concave Polygons Are a Challenge

• Definition: A concave polygon has at least one interior angle greater than 180° or a "dent" where the polygon caves inward. In contrast, a convex polygon has all interior angles less than 180°, making it simpler for collision detection.
• Collision Detection:
  • The basic plugin approximates a curve (e.g., a Bézier curve) as a series of line segments forming a polygon and checks if a circle intersects any segment. This works for both convex and concave polygons, as the segment-circle test is agnostic to the polygon’s concavity.
  • However, if the curve forms a closed polygon (e.g., a loop) and you want to detect if the circle’s center is inside the polygon (not just touching its edges), concavity complicates the point-in-polygon test. Standard algorithms like ray-casting work but require careful handling for concave shapes to avoid incorrect results.
• Curve Approximation: Bézier curves can produce concave shapes, especially with complex control point configurations. The plugin’s polygon approximation (a chain of line segments) may be concave, depending on the curve.

Current Plugin Support for Concave Polygons

The plugin, as described, supports concave polygons in the following sense:

• Edge Collisions: The collision detection algorithm checks for intersections between the circle and each line segment of the polygon. This works for both convex and concave polygons because it only considers individual segments, not the polygon’s overall shape.
• Open Curves: If the curve is not closed (e.g., a simple arc or S-shape), the plugin treats it as a polyline (a sequence of connected segments), which can be concave without issue, as no point-in-polygon test is needed.
• Limitations: The basic implementation does not handle closed concave polygons where the circle’s center might be inside the polygon without touching an edge. For example, in a concave star-shaped polygon, a circle could be fully inside the shape but not intersect any edges, and the plugin would not detect this without a point-in-polygon test.

Extending the Plugin to Support Concave Polygons

To fully support concave polygons, including closed curves where the circle might be inside the shape, you can enhance the plugin with the following modifications:

1. Add Support for Closed Curves

• User Option: Add a property to the CurveShape object, e.g., IsClosed (boolean), to indicate whether the curve forms a closed polygon (e.g., a loop where the first and last points connect).
• Polygon Generation: If IsClosed is true, ensure the polygon approximation connects the last point back to the first when generating segments from the Bézier curve.

2. Implement Point-in-Polygon Testing

• Algorithm: Use the ray-casting algorithm (also known as the point-in-polygon test) to determine if the circle’s center is inside the closed polygon:
  • From the circle’s center, cast a ray (e.g., along the positive x-axis).
  • Count the number of intersections with the polygon’s edges.
  • If the number of intersections is odd, the point is inside; if even, it’s outside.
• Handling Concavity: Ray-casting works for both convex and concave polygons but requires careful edge case handling (e.g., points exactly on edges or vertices). Use robust implementations, such as those in computational geometry libraries, adapted to GDevelop’s JavaScript runtime.
• Pseudo-Code:

  function isPointInPolygon(point, polygon) {
      let intersections = 0;
      for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
          let xi = polygon[i].x, yi = polygon[i].y;
          let xj = polygon[j].x, yj = polygon[j].y;
          if (((yi > point.y) != (yj > point.y)) &&
              (point.x < (xj - xi) * (point.y - yi) / (yj - yi) + xi)) {
              intersections++;
          }
      }
      return (intersections % 2) === 1; // True if inside
  }

3. Enhance Collision Detection

• Combined Logic: Update the isCollidingWithCircle method to check both edge intersections and point-in-polygon for closed curves:
  • First, check if the circle intersects any polygon edge (as in the original implementation).
  • If IsClosed is true and no edge intersection is found, check if the circle’s center is inside the polygon using the ray-casting algorithm.
  • If either condition is true, report a collision.
• Pseudo-Code:

  CurveShape.prototype.isCollidingWithCircle = function(circleObject, radius) {
      let circleCenter = { x: circleObject.getX(), y: circleObject.getY() };
      
      // Check edge intersections
      for (let i = 0; i < this.polygon.length - (this.isClosed ? 0 : 1); i++) {
          let A = this.polygon[i];
          let B = this.polygon[(i + 1) % this.polygon.length]; // Loop back for closed
          let AB = { x: B.x - A.x, y: B.y - A.y };
          let AC = { x: circleCenter.x - A.x, y: circleCenter.y - A.y };
          let lengthSquared = AB.x * AB.x + AB.y * AB.y;
          let t = Math.max(0, Math.min(1, (AC.x * AB.x + AC.y * AB.y) / lengthSquared));
          let closest = { x: A.x + t * AB.x, y: A.y + t * AB.y };
          let distance = Math.sqrt(
              (circleCenter.x - closest.x) ** 2 + (circleCenter.y - closest.y) ** 2
          );
          if (distance <= radius) return true;
      }
      
      // Check if circle center is inside (for closed polygons)
      if (this.isClosed && isPointInPolygon(circleCenter, this.polygon)) {
          return true;
      }
      
      return false;
  };

1. Optimize for Performance

• Bounding Box: Before running the point-in-polygon test, check if the circle’s center is within the polygon’s bounding box to avoid unnecessary ray-casting.
• Segment Reduction: For concave polygons, ensure the curve approximation doesn’t generate excessive segments in low-curvature areas, using adaptive subdivision (e.g., based on curvature or flatness criteria).
• Spatial Partitioning: If the polygon has many segments, use a spatial grid or quadtree to reduce the number of edges checked in both edge-intersection and ray-casting tests.

2. Handle Self-Intersecting Curves

• Issue: Some Bézier curves with extreme control points may produce self-intersecting polygons, which can confuse ray-casting algorithms.
• Solution:
  • Detect self-intersections during polygon generation by checking for segment intersections.
  • Warn the user (via console or editor feedback) if the curve self-intersects, as this may lead to unpredictable collision results.
  • Optionally, split the curve into non-self-intersecting segments or simplify the polygon.

3. Test Concave Cases

• Test Scenarios:
  • Create a closed concave curve (e.g., a star or crescent shape) and verify that a circle is detected when inside the shape or touching its edges.
  • Test open concave curves (e.g., a U-shaped arc) to ensure edge collisions work correctly.
  • Test edge cases, such as a circle exactly on a vertex or edge, or a very small circle inside a large concave polygon.
• GDevelop Integration: Use GDevelop’s event system to set up test scenes, ensuring the plugin handles concave shapes robustly without errors (e.g., avoiding issues like those in the GitHub discussion, such as undefined properties).

Practical Considerations

• GDevelop Compatibility: The ray-casting algorithm is lightweight and compatible with GDevelop’s JavaScript runtime. Ensure all inputs (e.g., control points, polygon vertices) are validated to prevent errors, as seen in the GitHub discussion (Support physic on non-convex shape #3753).
• User Experience: Provide clear documentation on how to use closed concave curves, including warnings about performance with high segment counts or complex shapes.
• Visualization: Enhance the plugin’s debugging tools to render the polygon’s concavity (e.g., highlight concave vertices) in the GDevelop editor, helping users understand the collision shape.

Example Use Case

Imagine a GDevelop game with a concave, star-shaped barrier (defined as a closed Bézier curve) and a circular player object:

• The plugin approximates the star as a closed polygon with, say, 50 segments.
• When the player moves near the star, the plugin checks if the player’s circle intersects any polygon edge or if the player’s center is inside the star (using ray-casting).
• If either condition is true, an event triggers (e.g., stopping the player or reducing health).