Collision code may miss some collisions because of acceleration

[kno10]

Minetest version

Minetest 5.9.1 (Linux)
Using LuaJIT 2.1.1723681758 (OpenResty)
Built by GCC 14.2
Running on Linux/6.10.7 x86_64
BUILD_TYPE=Release
RUN_IN_PLACE=0
USE_CURL=1
USE_GETTEXT=1
USE_SOUND=1
STATIC_SHAREDIR="/usr/share/minetest"
STATIC_LOCALEDIR="/usr/share/locale"

Summary

The current collision code may miss some collisions if the time step includes a movement direction change due to acceleration, e.g., when jumping. For small enough speeds and timesteps this is unlikely to happen given the padding margin used, though.

Here, min and maximum of the starting and the end position are used as query rectangle:
https://github.com/minetest/minetest/blob/3797ca52c4559da21623a39615c4e4d84d845ea9/src/collision.cpp#L389-L398

But with gravity, many movements have a parabolic shape. Taking the minimum and maximum of start and end only may clip the tip of the parabola. It would likely be sufficient to add for each axis the position where "initial velocity+time*accel=0", i.e., ctime=-velocity/accel if acceleration and velocity on the axis have opposite sign (need ctime > 0 and ctime < dtime and accel != 0 for this to be relevant).

Steps to reproduce

Use a high velocity and an even higher acceleration in the opposite direction, enough to go a number of nodes and return back to your starting position in one timestep.
Then start = end, and the current code will only test a 3x3x3 box (assuming a small object).

[Zughy]

@kno10 can you please provide actual code in the steps to reproduce? We test a lot of issues, so the easier the life for us, the better. Same for #15235

[appgurueu]

Not necessary, the issue can be understood by thinking through the logic.

I don't think it's particularly high priority for two reasons: It probably happens rarely that with the parameters used in practice a collision is missed, especially if server steps are "fast enough" and acceleration / velocity low enough due to the margins you mention, and if it does happen, it's probably unproblematic, because the net effect is still similar.
For example if you were to hit a ceiling, but the collision code decided that in those 0.1s you actually will be starting to go down again, then you will only be falling a bit too slow, but I don't think anyone would notice that.

The obvious way to fix this would be to compute the min / max of the parabola in the given timespan and use that to compute the relevant cuboid. That is probably fine for most slow entities (though for faster ones see #15227).

As for simulating collisions along the parabolas themselves, that touches upon #15029; I will comment there.

[kno10]

@kno10 can you please provide actual code in the steps to reproduce? We test a lot of issues, so the easier the life for us, the better. Same for #15235

@Zughy Can you provide example code that I can adapt?

[kno10]

But as @appgurueu noted, it will not be sufficient to just increase the min-max area, but also axisAlignedCollision needs to be modified (with the same equation) to compute the collision.
There also is a second aspect to #15227, maybe these could be solved in one go, I will comment there.

[kno10]

Also note that there are more issues with large dtime steps, so the most important part would be to reduce the dtime when possible, and maybe additionally even limiting the maximum dtime #15219.
Because transitioning into water may change acceleration (gravity vs. updrift), so the entire computation then may become pointless.
See https://www.youtube.com/watch?v=_fMPnRyTUwo&t=20s for the horrible behavior of minetest mobs with a too long dtime.

[Zughy]

@kno10 appguru has aready confirmed the bug, so I guess there's no need anymore