I've got my hands on the first edition of the book Game Physics Engine Development: How to Build a Robust Commercial-Grade Physics Engine for your Game by Ian Millington. Because I didn't really know how physics engines worked (and I wanted to brush-up on some basic physics and vector math), I've decided to build a very simple 2D engine based on the book, one that I could later expand on.
My initial goal is to create an impulse-resolution engine based on the "Particle Physics" presented in the book. This basically means that there's no torque/rotation to the bodies. (I'd like to write a little puzzle-platformer with it, where you can push things, that's why I've decided to leave those out at first)
The engine - in a nutshell - works like so:
update_world(dt) {
apply_generated_forces(dt); // Gravity, drag
integrate_forces(dt);
integrate_velocities(dt);
collisions := get_all_collisions();
foreach c in collisions {
apply_impulse_to_collision(c, dt);
apply_correction_to_interpenetration(c, dt);
}
clear_forces();
}
The problems occur when I want to stack bodies on top of each other. Because gravity pulls the bodies down, the elements in the stack interpenetrate (overlap) slightly. This is why there is an apply_correction_to_interpenetration function, that basically tries to correct for this. The correction causes a problem: it can affect already resolved bodies and push separated bodies into each other. Example:
Explanation:
- The bottom box interpenetrates the ground, so it gets pushed up into the second box (the ground has infinite mass, so it doesn't move)
- The top box interpenetrates the bottom one, so the top box is pushed up and the bottom box is pushed down in proportion to their masses. This causes the bottom box to slightly penetrate the ground.
To my understanding, this is because we use so-called local solvers instead of global solvers, meaning that we focus on one constraint at a time. Global solvers are too slow for games, so instead, we run the local solver multiple times in the hope of it converging to some solution - I really liked this talk about the topic.
Interpreting "applying the local solver multiple times" literally, my fix for the problem became this:
repeat(MAX_ITERATION_COUNT) {
collisions := get_all_collisions();
foreach c in collisions {
apply_impulse_to_collision(c, dt);
apply_correction_to_interpenetration(c, dt);
}
}
This solution "works", meaning that it will yield better results. My problem with it is that it takes many iterations actually improve to the point of "seamless". For a stack of 2 bodies, I need ~12 iterations to - visually - see no errors. This number quickly grows as I increase the number of bodies, which worries me since collision checking is a relatively expensive operation. This also makes the number of iterations "non-deterministic", meaning that if I design a map with many pushable - and stackable - crates, I won't know how to set that number of iterations so that players won't notice items sliding into each other. (I'm creating a pixel-art game, so a pixel really shows)
I think the error for each step of correction - iterations after the initial - n will resemble this series:
Which usually converges fast, but reaches pixel-perfection way too slowly for some cases.
So my question is: What approach can I use to reduce the number of required corrections? Are there some heuristics I don't know about?
To present my problem a bit more interactively, I've ported - and simplified - my code to processing, which can be found here (the source is available there too). You can use the left and right arrows to decrease and increase the number of corrections (iterations) performed. You can also make the top box "jump" with the up arrow.
Note: The book presents an algorithm, which shows a more realistic ordering instead of the arbitrary resolve order (page 122). I haven't implemented it here, but I've tinkered with it in the original source. It doesn't seem to affect this problem, as this seems strictly due to interpenetration corrections and not impulse resolution.
