Week 37: Oddly-shaped surfaces

A line drawing showing how to calculate the displacement to project a circle onto a line segment in an axially-aligned direction for various arrangements of the circle and segment.
Projecting a shape along an axially-aligned direction onto a segment.

tl;dr: Most of my work last week revolved around adding more support for oddly-shaped surfaces.

What happened last week?


  • Continued adding support for oddly-shaped surfaces.

Laundry list

  • Continued adding support for oddly-shaped surfaces:
    • Refactor calculate-surface-from-collision logic.
      • This used to assume that all surfaces lie along axially-aligned tile-map cell boundaries.
      • Now that I’m trying to reincorporate support for oddly-shaped tiles, this isn’t going to work!
      • I also used to have this split into two separate parts:
      • Calculate tile-map-coordinates from collision.
      • Calculate surface from tile-map-coordinates.
      • But in order to get more-accurate results, I actually need to check for surface-existence when calculating the tile-map-coordinate in the first place.
      • So I’ve now combined both the tile-map-coordinate and surface calculation into a single function.
    • Fix floor-max-angle epsilon.
      • This needed to be larger.
      • Godot's collision-detection system is not always super accurate.
    • Fix surface-calculation edge-cases for angled surfaces.
    • Add support for tracking surface-contact normals.
    • Test using surface-normals when applying min-velocity to maintain surface collisions.
      • When a character is attached to a surface, I need to always apply some velocity into the surface, otherwise Godot won't report that the character is still touching the surface.
      • However, now that I have non-axially-aligned surfaces, I needed to make this velocity happen in the direction of the contacted segment.
    • Add support for ignoring invalid Godot collisions during surface-state updates.
      • Godot's collision-detection system generates a lot of bogus collision normals.
      • I needed to make my system a little more robust to handling these invalid results.
    • Update get_slide_collision usage to consider adjusted collision normals if none of the collisions were valid.
    • Reconcile velocity-application-to-maintain-collisions with the move_and_slide_with_snap API.
      • The sequence of events was wrong.
      • My velocity values weren't actually getting used correctly, and surface-contacts were breaking.
    • Remove legacy logic for maintaining collisions.
    • Disable snap-to-surface and maintain-surface-collision when jumping or releasing surface.
    • Fix issues with snap-to-non-floor-surface.
    • Cancel horizontal velocity when colliding with a ceiling that slopes against the direction of motion.
    • Implement better drawing single-vertex annotations.
    • Start implementing better non-axially-aligned and segmented-surface annotations.
    • Implement better surface-segment drawing, so that adjacent segments align even as they get deeper, and for any angle of either surface.
      • My previous surface drawing logic assumed all surfaces were axially-aligned, and didn't look good with odd surface angles.
A screenshot showing surface-annotations drawn with my new logic; adjacent segments line up even as the drawings go deeper into the surface, and single-vertex surfaces are now drawn with gradients.
Notice how all the adjacent segments line up, even as the get deeper and more faded!
Also, I draw a circle for single-vertex surfaces, and these look a lot better now that I added a radial gradient for them.
  • Start adding support for calculating trajectories along oddly-shaped surfaces.
    • Previously, my intra-surface-edge and climb-to-adjacent-surface-edge trajectories were calculated assuming that adjacent surfaces form a 90-degree angle.
    • This causes some problems for oddly-shaped surfaces:
      • Expected edge durations and distances were wrong.
      • The paths drawn when preselecting a destination were inaccurate and distracting.
      • Edge-playback for climb-around-adjacent-surface-edges were pushing the character into the surface, while the collision-system pushed the character out of the surface, and the character ended up getting stuck going back and forth.
An animated GIF showing some navigation along oddly-shaped surfaces.
My previous trajectory calculations produce inaccurate trajectories.
You can see this both in the path annotations, and in how the edge-playback tries to push the character into the surfaces while the collision system tries to push the character out, leading to zig-zaggy movement.
    • I implemented a function for projecting a shape along an axially-aligned surface-normal direction until it lies against the surface.
      • project_shape_onto_surface
      • project_shape_onto_segment
A line drawing showing how to calculate the displacement to project a circle onto a line segment in an axially-aligned direction for various arrangements of the circle and segment.
Projecting a circle onto a line segment in an axially-aligned direction.
  • These are segments for a floor surface, so the surface normal is straight up.
  • Our goal is to find how far downward the circle can move before touching the segment.
  • The green dotted line shows this displacement for each case.
  • In general, there are three possibilities to consider for each case, and we use whichever case is valid and yields a smaller displacement:
    • The left-end of the segment.
    • The right-end of the segment.
    • The point along the circle where a line along the surface normal through the circle center intersects the circle circumference.
  • I support two other shapes:
    • Rectangles:
      • For these, I consider either end of the segment and either corner along the closer-side of the rectangle.
    • Capsules:
      • These are either a special case of circles or rectangles, depending on the rotation of the shape and the relative positioning of the segment and the shape.
  • Miscellaneous:
    • Add support for `move_and_slide_with_snap` instead of `move_and_slide`.
      • In the end, I actually removed this support after all.
      • Godot's surface-snapping is too limited for me; it only works on floors.
      • And I already have all the tools I need to implement my own version that works at least as well.
    • Record a space_state reference on Su.
      • This is an object that I need to reference when using some of Godot's collision detection APIs.
      • Previously, I was just re-accessing this in lots of different places.
    • Remove rounding-corner-actions, since they are no longer needed for snapping the character position to the corner.
    • Maintain a custom copy of active collisions, and concatenate into this the collisions from the separate calls to move_and_slide in `_apply_movement` and `_maintain_collisions`.
    • Refactor match-expected-edge-trajectory to be a function on SurfacerCharacter instead of an action-handler.
      • This gives the benefit of being able to now offset the character according to surface and character shape after updating the position to match the edge.
      • Because updating the expected edge position to be more accurate for oddly-shaped surfaces is much harder to do.
    • Add an extra metadata flag to FailedEdgeAttempt, to enable recreating the appropriate fall-from-floor-edge-attempt calculations.
    • Add an optional `basis_edge` parameter to `calculate_edge` in order to enable recreating the appropriate fall-from-floor-edge calculations.
    • Fix FallFromFloorEdge to save/load fall-off state in the platform-graph files.
    • Fix a bug with maintaining both floor and wall collisions at the same time.
    • Fix a bug where maintain-collision was preventing climbing from wall to concave ceiling.
    • Move logic for forcing character trajectory to match expected navigation from navigator to character.
    • Refactor collider-shape-rotation-logic to store and reference is_rotated_90_degrees rather than recalculating it.
    • Remove obsolete snap_to_surface_vector.
    • Refactor shape/rotation/half-width-height/is-rotated-90-degrees logic to use a new RotatedShape data structure.

What's next?

  • Finish adding support for oddly-shaped surfaces.
  • Add support for parsing surfaces from multiple TileMaps.
  • Add support for colinear neighbor surfaces that aren't merged together.
    • This will be important for things like marking parts of a surface that have a different friction, or that can't be navigated across.

🎉 Cheers!

This is a simple icon representing my sabbatical.