Simple, lightweight, general purpose collision detection

[vrld]

Double post again to bump this topic (may the gods have mercy on my soul)

HardonCollider changes behavior:
As of the most recent update, HC will report collisions as soon as it detects them. Previously this was a two step process: In the first step, all collisions were collected and in the second, all collision were reported.

This led to complicated collision resolution when a shape x collided with two other shapes y and z at the same time and the resolution of x and y would also (partly) resolve the collision of x and z.

To give you (completely random ) example, consider a tile-based platformer. If the player managed to stand on two adjacent tiles, and the callback would simply push the player out of the tile he collided with, the player would be pushed up too far:
Some stunts had the be pulled to resolve this situation correctly.

Faulty collision resolution.

collision_resolution.png (15.45 KiB) Viewed 3649 times

With the newly change, the second resolution (with tile b) will not be invoked, since after the collision with tile a is resolved, there is no longer a collision with tile b. Additionally, situations where a callback partly resolves a collision will also be handled correctly:

Step wise resolution.

collision_resolution_step.png (22.26 KiB) Viewed 3649 times

Also, when you remove a shape in a collision callback, that shape will not be participating in any following on-collide callbacks (stop-collide will still be called, as it should be).

Get the new version here or as weirdly named zip here. Please let me know if you run into any issues using the new code.

[kikito]

Are collisions sorted out in any way? In other words, will TileB come always before TileA, or in some occasions will TileA come in first, depending on a random pairs() invokation?

That's one of the toughest problems I had in bump.lua . Right now it sorts by "surface colliding" (the tile covering most surface on the 'currently evaluated object' is collided first. This means lots of collisions are calculated and discarded. But well, AABBs are fast). It is not a silver bullet - sometimes it does the "non-intuitive" thing. I would be happy to get more brains working on the problem of "what colliding object should be dealt with first".

[Ragzouken]

Is this supposed to support polygons with negative coordinates? I thought I was having some trouble creating a centered rectangle - something to do with it ending up with NAN and INF arguments for the dot product in the support routine. I don't really have a minimal test program at the moment, and the problem was non-deterministic, so I thought I'd just ask if I was trying to do something undefined?

Code: Select all

shapes.newPolygonShape(x-w, y-h,
                       x-w, y,
                         x, y,
                         x, y-h)

[vrld]

Bartbes just asked how HC handles the situation that a collision callback moves a shape back into a shape from a previous callback, i.e. this situation (when only C is movable):

clusterfuck.png (16.62 KiB) Viewed 3635 times

The answer is: it doesn't (and didn't before), so watch out for that.

Are collisions sorted out in any way? In other words, will TileB come always before TileA, or in some occasions will TileA come in first, depending on a random pairs() invokation?

No. But there is no way of knowing in advance - for bump or HC anyways - which collision should be resolved first. However, most of the time it shouldn't matter (in the step example you will get the same end result regardless if you collide with TileA or TileB first).

I would be happy to get more brains working on the problem of "what colliding object should be dealt with first".

The only way I see to really solve this problem would be to let the user assign priorities to which collisions should be reported first.

Is this supposed to support polygons with negative coordinates?

Yes.

something to do with it ending up with NAN and INF arguments for the dot product in the support routine.

Odd. Are you sure your coordinates are neither NaN nor very (and I mean VERY) big (or small)?

[Ragzouken]

Actually, come to think of it, I'm getting really wacky results all round - and I can't replicate the same crash I used to get with that. For some reason I didn't get the problem if created the same rectangle with shape = collider:addRectangleShape(same coords) and then collider:remove(shape) - is there any reason that would be the case?

I'd investigate further, but it's code from a game jam, and complete spaghetti - probably I am just doing numerous stupid things that are interacting badly :/

[Robin]

Great update!


I still need to include the following before resolving, though, to avoid "stumbling":

Code: Select all

    if bottom1 - 3 <= top2 then
    	mtv_x = 0
    end

Otherwise, when the player walks from the one tile to the next, it stops and you have to jump over the seam, even though it is pixelperfectly right.

[kikito]

Are collisions sorted out in any way? In other words, will TileB come always before TileA, or in some occasions will TileA come in first, depending on a random pairs() invokation?

No. But there is no way of knowing in advance - for bump or HC anyways - which collision should be resolved first.

Probably you didn't mean both HC and bump on that phrase. It took me long time to get that feature working as I wanted on bump. But now TileB always comes first, if it covers more surface.

[Ragzouken]

Bartbes just asked how HC handles the situation that a collision callback moves a shape back into a shape from a previous callback, i.e. this situation (when only C is movable):

The attachment clusterfuck.png is no longer available

The answer is: it doesn't (and didn't before), so watch out for that.

What happens in this situation? Is it always / ever the case that the callbacks are called in an infinite loop due to the flip flopping?

I'm also experiencing a problem where a concave polygon colliding with a circle is giving a minimum translation vector where the y component is nil. My understanding is that the mtv should be valid for everything but points, and at the very least be non-nil for everything, so this is a bug?

[Ragzouken]

The problem seems to be in lines 172-174 in shapes.lua (CircleShape:collidesWith) - for non-polygon non-circle shapes (convex polygons being "compound" type) the code only expects and returns one separation value, which doesn't seem consistent with anything else. I'm using the fix of just "return other:collidesWith(self)", but I'm not sure if that has other implications.

Code: Select all

-- else: let the other shape decide
local collide, sep = other:collidesWith(self)
return collide, sep and -sep

Code: Select all

-- else: let the other shape decide
return other:collidesWidth(self)

I have *tried* to submit a patch/whatever on github, but I have next to no idea what I'm doing, so apologies if I have done something stupid there.

[bartbes]

What happens in this situation? Is it always / ever the case that the callbacks are called in an infinite loop due to the flip flopping?

No, the callbacks are only called once.