All things collisions

Recently I have been getting in to physics and collision detection in Codea and programming in general. I’ve read a few books, but none of them have really been satisfying to me because they’re too technical and too focused on real-world equations for my taste(not that those don’t have their place, but basic physics engines are not their place). 2D collision detection is easy. I even wrote my own engine, based on I like how it works in terms of collisions as it is extremely efficient as well as accurate, but collision response is a bit harder. How have any of you implemented collision response? In my current program trying to emulate N++(the game the creator of the tutorial made) I can get the collisions to work fine, but the collision response(something they didn’t go into great detail in the article about) doesn’t work very well - very jittery. Of course this is my fault, but I can’t find a good fix. Here is the code anyway: I love this algorithm, it’s extremely versatile and accurate(not for circles but I didn’t need those anyway). Aside from all this, I’ve also been wondering how 3D collisions are done. I’ve already done a height map project but how does one move beyond the height map? I’m talking caves, overhangs, cliffs, all built into the terrain and detection engine. Is there a simple way to do this without many special cases? I’m not even really interested in how to implement it into Codea, but I’m wondering how big games such as No Man’s Sky or even FPS games handle collisions with complex objects in the terrain. I love voxels, but they’re limiting at times and I’d rather find another method. However other methods do have their own intricacies, mainly generation and generating the mesh. Therefore if anyone could link me to an improved voxels tutorial, perhaps generating smoother terrain, I would be grateful.

TLDR : How does one do 2D collision response?
How does one do 3D collision detection with complex terrain features?

Well, 2 parts to this problem. You just mention detecting collisions, but to what extent do you want to resolve collisions? eg, with a flight game you might just need detection, if your plane touches the ground then “boom”. But if you need, say, a crate to land on a bumpy terrain, bounce, slide, and then come to rest, (eg the collision is resolved, a full 3D physics system) that would be brain-meltingly hard I think (from the articles I’ve read on it at least). If I needed that for a project, I’d probably go with a system that has 3D physics out of the box, like Unity, or Apple’s SceneKit (tho you can’t code either of those on an iPad of course!)

Having said that, if you limit your 3D physics so that all dynamic bodies are spheres and all static bodies are planes aligned with at least one of the axes, then that’s quite easy, as sphere meets plane is really just circle meets line. That’s what I did for Banjax.

If you want to find whether a given point is below the surface of your height map, you can use bilinear interpolation. It interpolates between the four points making up the quad to find the height at the point you specify. The function below is for a Z-up environment, where height is on the Z axis. If you wanted Y-up, just switch all the Z and Y components. So collision detection between a spherical body and this terrain is as simple as (myBody.pos.z - myBody.radius) < getHeight(myBody.pos). Resolving that collision though is quite a bit more complex.

function getHeight(pos)
   --convert world coordinates (pos) to heightmap coordinates (px, py) plus the remainder (x, y)
    local px,x = math.modf(pos.x/arena.step) 
    local py,y = math.modf(pos.y/arena.step)
    --the other coordinates of the quad we will check
    local pyy=py+1 
    local pxx=px+1 

    local xi, yi = 1-x, 1-y --inverse
    -- the 4 points of the quad of the heightmap grid we are checking
    local a,b,c,d = grid[px][py].p.z, grid[px][pyy].p.z, grid[pxx][pyy].p.z, grid[pxx][py].p.z --4 known points of square
   --unit square bilinear interpolation
    return a * xi * yi + d * x * yi + b * xi * y + c * x * y 

For 2D, why not just use Box2D?

The key to managing collisions in Box2D or any other physics system is to make good use of bitmasks, so that you only trigger events for the collisions you’re interested in.

BTW, on the issue of terrain generation (but also lots of other stuff, path-finding, line-of-sight, hex grids etc), this page is incredible: make sure you check out the interactive demos that are on most of the pages

I read that most games cheat by using simple shapes to approximate the objects.

Wrt the jitter, it seems as though your object has become embedded. If there is a collision, you need to calculate (by interpolation) the time at which the collision took place, which will be between the last draw and the current one, and backtrack the object along the path it came, to prevent it embedding.