## Simple, lightweight, general purpose collision detection

vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

### Re: Simple, lightweight, general purpose collision detection

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 2396 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 2396 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.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Contact:

### Re: Simple, lightweight, general purpose collision detection

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".
When I write def I mean function.
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

### Re: Simple, lightweight, general purpose collision detection

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)
Last edited by Ragzouken on Mon Oct 08, 2012 5:23 pm, edited 1 time in total.
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

### Re: Simple, lightweight, general purpose collision detection

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 2382 times
The answer is: it doesn't (and didn't before), so watch out for that.
kikito wrote: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).
kikito wrote: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.
Ragzouken wrote:Is this supposed to support polygons with negative coordinates?
Yes.
Ragzouken wrote: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)?
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

### Re: Simple, lightweight, general purpose collision detection

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
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

### Re: Simple, lightweight, general purpose collision detection

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
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Contact:

### Re: Simple, lightweight, general purpose collision detection

kikito wrote: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.
When I write def I mean function.
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

### Re: Simple, lightweight, general purpose collision detection

vrld wrote: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?
Attachments
hardonbug.love
This demonstrates where my shape causes the failure.
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

### Re: Simple, lightweight, general purpose collision detection

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
Sex machine
Posts: 4946
Joined: Fri Aug 29, 2008 10:35 am
Location: The Netherlands
Contact:

### Re: Simple, lightweight, general purpose collision detection

Ragzouken wrote: 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.

### Who is online

Users browsing this forum: No registered users and 5 guests