ArcadeSolver buggy collision resolution and ContactSolveBias

[kfalicov]

Behavior

2024-07-21_19-19-19.mp4

My current parameters in-engine are:
version: ^0.30.0-alpha.964

physics: {
        arcade: {
            contactSolveBias: ContactSolveBias.VerticalFirst,
        },
        colliders: {
            compositeStrategy: "separate",
        },
        continuous: {
            checkForFastBodies: true,
        },
        solver: SolverStrategy.Arcade,
    },

Investigation

It seems to me like it's an issue with the resolution order of the solve, or the provided contactSolveBias not applying as expected. I investigated the ArcadeSolver code to try and find some evidence of the cause of the issue. I noted a few potential issues with the AABB solver:

1. ArcadeSolver's preSolve computes the distance based on worldPos of the objects, which is then used to sort the distanceMap so that the collisions can be solved by closest-first. This seems like an issue because the worldPos difference between the colliders is based on the origin point of the colliders, which in this case is not indicative of the "embed" distance between the colliding objects. I would expect instead that for each "axis" of the collision, the distance between the relevant edges is used to determine the distance, rather than a vector from center -> center
   

   Excalibur/src/engine/Collision/Solver/ArcadeSolver.ts

   Line 84 in 1a13e28

   const distance = contact.colliderA.worldPos.squareDistance(contact.colliderB.worldPos);

   
   In my attached video it does seem like this may have something to do with it, since the moving box is further away from the center of the "ground platform" than it is from the "wall platform" at the time of the buggy behavior
2. In the preSolve when computing the Side of the collision, rather than using contact.mtv it should be dependent on the colliding object's most recent position/velocity vector, because otherwise the object may be pushed out in a way which doesn't make sense for the falling object. I believe the traditional term for this is "Swept AABB", and the direction checked first during the "sweep" should be based on the contactSolveBias
   

   Excalibur/src/engine/Collision/Solver/ArcadeSolver.ts

   Line 81 in 1a13e28

   const side = Side.fromDirection(contact.mtv);

My expectation would be that for all AABB collisions, we perform a sort of raycast to the earliest intersecting edge, and reverse the box's movement back along that ray until it is flush with the intersecting edge. Then, depending on whether the edge itself is a horizontal or a vertical, we can restore the opposite component of the velocity. For example:

1. box would hit along the floor first (vertical collision)
   2. we compute this using the Side.fromDirection of the moving body's velocity
2. backtrack the object's movement by an amount which puts the box flush on the surface
3. based on the velocity remaining, cast a new ray in the complementing direction (horizontal, this time) and do another collision solve

Single Collision	Multi Collision

In the Multi Collision, the new location collides with two colliders (floor and wall). However, we don't need any sort of bias if we check the nearest collision first:

1. the bottom of our moving object (pre-collision) is closest to the top of our floor
2. then, we use the vertical distance (post-collision) between object bottom and floor top
3. project it back against the velocity vector to get our impact point
4. use that projection as a raycast to find any other obstacles

Is this a behavior that would be arriving in the "continuous" (marked as WIP) physics setting?

[kfalicov]

Apologies if this should go in discussions- I realized it became more discussion than bug report midway through

[eonarheim]

@kfalicov Thanks for the issue! This is very thorough!

I think it should be an issue :)

Apologies if this should go in discussions- I realized it became more discussion than bug report midway through

contactSolveBias really helps in the case you have a seams in colliders and sorts the contacts in specific order. Solving vertical contacts first over horizontal can help platformers not catch floor seams when running. We might need some better docs around this.

Part of the problem is the discrete nature of the simulation, every update moves the colliders a fixed amount based on velocity/acceleration. If the jumping rectangle accelerating updates most of the way through the floor rectangle, overlap resolution will push it through the bottom to minimize overlap. What you suggest might help with this, we could explore this as well but might produce other artifacts if we ignore minimum overlap and rely on current pos/vel. Side is mostly a convenience in the current setup to help folks know roughly the cardinal direction of the collision relative to the other participant.

2. In the preSolve when computing the Side of the collision, rather than using contact.mtv it should be dependent on the colliding object's most recent position/velocity vector, because otherwise the object may be pushed out in a way which doesn't make sense for the falling object. I believe the traditional term for this is "Swept AABB", and the direction checked first during the "sweep" should be based on the contactSolveBias

Totally agree on this, we should sort the contacts based on the distance to the collision features, not the centers of their geometry. This does cause some odd artifacts. We should definitely change this 100%

1. ArcadeSolver's preSolve computes the distance based on worldPos of the objects, which is then used to sort the distanceMap so that the collisions can be solved by closest-first. This seems like an issue because the worldPos difference between the colliders is based on the origin point of the colliders, which in this case is not indicative of the "embed" distance between the colliding objects. I would expect instead that for each "axis" of the collision, the distance between the relevant edges is used to determine the distance, rather than a vector from center -> center

A lot of what you describe is part of a continuous collision solution. These are exactly the type of things we are thinking about, I've been doing a lot of research around approaches. This is definitely something we want.

My expectation would be that for all AABB collisions, we perform a sort of raycast to the earliest intersecting edge, and reverse the box's movement back along that ray until it is flush with the intersecting edge. Then, depending on whether the edge itself is a horizontal or a vertical, we can restore the opposite component of the velocity

Definitely, currently the (not very robust) continuous collision mechanism is raycasting when an object is moving faster than half it's size in a frame it starts a raycast from the center of (currently only in the DynamicTree spatial partition strategy). My plan is to do a separate phase in the solver for time of impact contacts. I'm currently leaning towards a technique known as speculative contacts as a v1 and perhaps something more robust in the future that can better handle fast rotation and multiple fast objects.

Is this a behavior that would be arriving in the "continuous" (marked as WIP) physics setting?

To summarize:

1. 100% we should sort contacts by feature distance, not center collider distance
2. I'm not positive using the current velocity and contactSolveBias this will solve the issue, but I'm willing to explore this more. But a swept AABB or shapecast with time of impact code would definitely solve this. contactSolveBias is currently used just for contact sorting currently in the ArcadeSolver.

Workarounds:

• Thicker floors (I know it sounds silly but might be a cheap option)
• Run excalibur in a fixed fps mode, it'll give a consistent simulation as variable framerates could drastically influence update distances. Forcing 60fps or ramping to 120fps might bring enough discrete steps to avoid the teleport. We've done for some of our platformers

  const game = new ex.Engine({
    fixedUpdateFps: 60,
    ...
  })

[kfalicov]

Workarounds:

• Thicker floors (I know it sounds silly but might be a cheap option)
• Run excalibur in a fixed fps mode

Unfortunately, neither of these solve the issue as recorded in the video- After the initial collision with the wall, as the player falls down, it still always manages to squeeze through:

2024-07-21_22-13-45.mp4

I did some debug logging and found that:

• The collision has a Side of Left, which pushes it to the right (into the wall)
• on the very next frame, it has a Side of Right, which pushes it back
• this repeats twice per side, and then the object has fallen completely through.

It never tries to displace back out to the top no matter how I set the fixed update, and no matter how thick I make the platforms, as long as the gap is sufficient for the object to be less overlapping in the X direction than the Y direction, it will always do this:

[kfalicov]

I'm trying to avoid using the Realistic physics solver as I don't need the rest of its features, and it will get expensive with what I have planned for my project. But my requirements mean that I may end up having to write my own collision resolver, if only just for the player actor

[eonarheim]

@kfalicov I'll dig in deeper this week, this is definitely something that should work

[eonarheim]

@kfalicov Out of curiosity, what happens if you remove contactSolveBias

[eonarheim]

@kfalicov Sorry for the rapid fire responses!

Could you send me your test code from the videos?

[kfalicov]

Sure!
https://github.com/kfalicov/excalibur-prototypes/tree/platformer

The engine setup is in apps/movement and the init is main.ts. the issue seems to persist regardless of the contactSolveBias value

[eonarheim]

I got things to avoid teleporting by turning on a fairly high fixed update at 120fps (8ms steps guaranteed), it seems I can also go as low as 95.

120fps-platformer.mp4

Another thing that was pointed out to me is we could implement substepping in excalibur to improve the fidelity of the simulation with low cost, I might also explore that in addition to continuous collision.

[kfalicov]

The problem with any solution based on the fixed update is that it means this problem is concealed, not solved. All it takes is for the same object to be moving at about 1.5x speed in the new fixed update FPS in order to still experience the same incorrect collision behavior- the only condition to replicate this is that the vertical overlap is greater than the horizontal during any collision, which is likely to happen again on accident if I'm not extremely precise with the values I choose for acceleration and maximum velocity.

If players walk all the way until just 1 pixel remains on the platform, and then they jump straight up, their falling speed is usually enough to make sure that they fall past the platform rather than landing back on it

[eonarheim]

@kfalicov Fair point, I'll keep poking around for workaround. I do agree that a more robust solution is warranted probably continuous/substepping.

I'm going to step through the arcade solver in this setup as well to see if there are any other oddities that we can fix easily (in addition to collision feature distance)

[eonarheim]

I've got a promising experiment locally with substepping that seems to work without a fixed update, I'll post more when I have firmer results.

The gist is it does multiple small integration steps, re-uses collision features, and solves incrementally every frame

[github-actions]

This issue hasn't had any recent activity lately and is being marked as stale automatically.