Jump to content

View more

Image of the Day

Adding some finishing touches...
Follow us for more
#screenshotsaturday #indiedev... by #MakeGoodGames https://t.co/Otbwywbm3a
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.


Sign up now

How to deal with getting stuck in sequential impulse?

4: Adsense
  • You cannot reply to this topic
17 replies to this topic

#1 Finalspace   Members   

1120
Like
1Likes
Like

Posted 19 April 2017 - 02:24 AM

I have a case when my fixed-rotated player body gets stuck in my level when he teleports into a static geometry or near invalid position, occupying more than half the radius of the player.

 

At first i thought this was a issue with my custom sequential physics system, but this happens in box2d-lite as well.

Its hard to explain, so i attached a modified box2d-lite source to show this case.

 

What i want to know, how do i detect such a case, so that i can handle that properly - like trying to teleport the player to a better position, or change the contact normals to random angles :unsure:

 

Would it work, to check if there is a contact with a extreme high impulse going on?

Attached Files


Edited by Finalspace, 19 April 2017 - 02:29 AM.


#2 Aressera   Members   

2897
Like
0Likes
Like

Posted 19 April 2017 - 10:25 AM

I think in that case you need to look at the direction of the geometry surface normals to determine which side of the geometry is the front, then you can just push the object out in that direction with split impulse position correction. It's an issue of choosing the correct contact point and normal.



#3 Randy Gaul   Members   

2720
Like
0Likes
Like

Posted 19 April 2017 - 11:12 AM

Post video of what is going on so we can easily take a look at the behavior. Also please draw contact points and contact normals.



#4 Finalspace   Members   

1120
Like
1Likes
Like

Posted 19 April 2017 - 12:09 PM

Post video of what is going on so we can easily take a look at the behavior. Also please draw contact points and contact normals.

 

Sure, here it is (Single stepping and resume):

 

Also i modified the source to display the arrows as well ;-)

 

*Edit:

Wait a second, this looks exactly like an internal edge issue.

This may be solved by using my tile tracing system - converting my tilemap into connected line segments.

Attached Files


Edited by Finalspace, 19 April 2017 - 12:33 PM.


#5 felipefsdev   Members   

310
Like
0Likes
Like

Posted 19 April 2017 - 01:32 PM

@FinalSpace

It happens with Box2D and Chipmunk because you are setting the position variable directly:

b->position.Set(6.0f,  -tileSize * 0.5f); /* Code that I see in your video */

which you shouldn't do (in Box2D or Chipmunk). If, instead, you just set the velocity in Box2D or Chipmunk, it's unlikely that it will happen. It might get stuck in one of the corners, but not... stuck stuck... you can still move. It's unlikely that it happens setting velociy, because when you set the velocity, the engine (Box2D and Chipmunk) will record variables regarding the motion to solve later penetration in solids. Since you are making your own physics engine, I imagine here is where it differs from Box2D and Chipmunk:

 

* Chipmunk and Box2D use **iterative solver**, which makes objects impossible (theoritically) to get stuck forever.

 

The iterative solver will move the object penetrating by a specified amount of units. That's why these two physics engine aren't nice for 2D games trying to simulate the old school platformers or top down. The iterative solver isn't perfect, because it **WILL** let objects penetrate (undesired), and then it will solve little by little the collision, making collisions with walls look like collisions with cushions (and it is a PAIN IN THE ASS to make it look good). So, I don't think you can compare your physics with Box2D/Chipmunk (and I don't recommend you to use them, because by the looks of your game, you don't want tha cushion-like effect).

 

People using Game Maker often uses the following approach, and it's very suitable for non-iterative solvers (which seems to be your case):

h_speed = /* My horizontal speed here */;

if (overlapping(x + h_speed, y, "wall")) {
    /* We will collide with this horizontal move */
    
    while (!overlapping(x+sign(h_speed), y, "wall")) {
        /* We move 1 by 1 px until we reach the limit without collision */
        x = x + sign(h_speed);
    }
    h_speed = 0;
}
x = x + h_speed; /* The original speed or 0 if was solved above */

There's a youtube tutorial here: www.youtube.com/ watch?v=IysShLIaosk



#6 Randy Gaul   Members   

2720
Like
0Likes
Like

Posted 19 April 2017 - 06:03 PM

I think you nailed it by mentioning internal edge issue. The internal edges are giving a lot of solutions that probably are not wanted. If we look at 38s we can see the top right corner of the box is getting a couple downward arrows. These seem to prevent the box from popping back up to the surface.

 

Internal edges have lots of solutions. Maybe your raycasting thing can work! If you like we can start talking more about handling internal edges if that is helpful to you.


@felipe There seems to be some confusion. The video results are not due to using an iterative vs non-iterative solver. The problems in the video are entirely due to discrete collision detection vs continuous collision detection. In other words, the shape starts penetrating deeper into the geometry and comes across unwanted collisions. The unwanted collisions can cause things to get stuck or fall out of the world. The faster a shape moves the more likely it is to fall into undesired collisions due to the nature of discrete timesteps.



#7 felipefsdev   Members   

310
Like
0Likes
Like

Posted 19 April 2017 - 08:48 PM

Oh, I missed the edit that he solved the problem!

 

By his post, I totally thought he was using his physics engine and then tested with Box2D later, that's why I explained about the non-iterative solver and iterative solver.



#8 Finalspace   Members   

1120
Like
0Likes
Like

Posted 19 April 2017 - 11:05 PM

Just to clarify, this happened in my custom sequential impulse physics engine (which is identical to box2d-lite in terms of functionality) when i approach the static geometry too fast as well (hard to reproduce but happened a few times while testing). Half of the radius gets inside the static geometry and then the internal edge contacts pushes it into the geometry, so that i wont come out ever. Impulses at that point just goes crazy and builds up energy until a given point (Warmstarting and multiple Iterations keeps them from exploding).

 

One solution i will try is to convert my tilemap (I love the concept of tilemaps, its simple and can be easiely changed) into connected line segments which i can produce using a contour tracing algorythm, which i already have implemented in the past successfully ;-)

This should solve may internal edges problems for the most part. Also i should just clamp the velocity of the bodies so that i can never move too fast, so that bodies wont pass through thin line segments...

 

But i would love to hear what other solutions there exists.

I heard about conservative advancement, but after looking at the paper i still dont get it - except for the fact thats a "search in time" algorythmn, so its basically a while loop until some threshold is met. Not sure how i would apply that method to the existing contact solving.

 

Anyway i will now port my javascript source to C++ and see how is it going.


Edited by Finalspace, 20 April 2017 - 12:14 AM.


#9 Randy Gaul   Members   

2720
Like
0Likes
Like

Posted 20 April 2017 - 11:05 AM

Making line segments is a good solution since you're using a tile map, along with a velocity clamp. Another solution is to find TOI between the player and the world.

The TOI can be found with conservative advancement (CA). The idea of is to call GJK to get a distance between two shapes. Then use relative velocity to form a guaranteed "safe" step, as in a step forward in time that shouldn't result in inter-penetration. Erin Catto GDC 2013 has some slides on this IIRC. Keep moving the shapes closer together and keep calling GJK to see how far apart they are. Once they are "close enough" consider that a contact, and then make some contact points (somehow). The nice thing about CA is it can handle rotating objects.

If the shape cannot rotate it gets even simpler, for example for many player controllers just using some hacky raycasts, or even doing iterative bisection to find TOI should work perfectly fine.



#10 Finalspace   Members   

1120
Like
0Likes
Like

Posted 20 April 2017 - 01:57 PM

First step is complete: Ported my javascript tile tracer to c++:



#11 Finalspace   Members   

1120
Like
0Likes
Like

Posted 23 April 2017 - 11:51 AM

So i am back:
 
The implementation works beatifully, i get perfect line segments without any internal edges due to connected edges, but unfortunatly the internal edge issues are still present for vertex vs vertex contacts, when trying to fall off - see the following video demonstrating the progress and the issue:
 

 
 
Should i just drop any vertex vs vertex contact entirely - detected by some distance threshold + dot product???

Edited by Finalspace, 23 April 2017 - 12:38 PM.


#12 Randy Gaul   Members   

2720
Like
0Likes
Like

Posted 23 April 2017 - 03:36 PM

Oh definitely drop vertex to vertex cases. These can be handled implicitly by face to face! I imagine if you drop vertex to vertex your solution will work pretty well.



#13 Finalspace   Members   

1120
Like
0Likes
Like

Posted 25 April 2017 - 05:30 AM

Is this a legitimate way to solve that?
 

        // @NOTE: Distance of penetration allowed in the solver
        constant r32 PHYSICS_ALLOWED_PENETRATION_DISTANCE = 0.01f;

        // @NOTE: Used for merging two contacts together when too close
        constant r32 PHYSICS_CONTACT_MERGE_THRESHOLD_DISTANCE = 0.015f;
        StaticAssert(PHYSICS_CONTACT_MERGE_THRESHOLD_DISTANCE > PHYSICS_ALLOWED_PENETRATION_DISTANCE);

        //
	// Merge two points into one when too close together
	//
	if (output.count > 1) {
		Vec2f tangent = Vec2Cross(output.normal, 1.0f);
		Vec2f distance = output.points[1] - output.points[0];
		r32 projDistance = Vec2Dot(distance, tangent);
		if (projDistance < PHYSICS_CONTACT_MERGE_THRESHOLD_DISTANCE) {
			output.points[0] = Vec2Lerp(output.points[0], 0.5f, output.points[1]);
			--output.count;
		}
	}

	//
	// Drop vertex vs vertex case to solve internal edge issues
	//
	if (output.count == 1) {
		output.count = 0;
	}

 
It works, but i am not sure if this is right - especially the part when i merge two contacts into one due to clipping!

 

Edit*: Forget it, i am just stupid... dropping any vertex contact is just silly.

I need to take the contact distance into account as well!


Edited by Finalspace, 25 April 2017 - 05:44 AM.


#14 Finalspace   Members   

1120
Like
0Likes
Like

Posted 26 April 2017 - 01:34 AM

Hmm, i still havent solved the issue... neither detected if i am face vs face or face vs edge or edge vs edge.

My contacts are the results of clipping the incident face segment against the reference side planes which produces two contact points in my internal edge case for 99%, because both contacts are behind the incident face plane -> So its a face vs face case :-(

 

I really need one quiet evening, without any kids jumping around... so i can focus on that.



#15 Randy Gaul   Members   

2720
Like
0Likes
Like

Posted 27 April 2017 - 11:12 AM

Yeah you definitely can't drop cases with one contact. I just realized you must be treating the individual line segments as separate colliders. So what happens in the video is you do get a face to face contact, but clipping gives you one or two points. If the two point case, you have some merging code so it will probably be merged to a single point that looks like a vertex to vertex collision.

The problem becomes: how to treat the corner where to line segments meet end to end as a new and unique voronoi region. In your video each corner voronoi region would look like 1/4th of a circle, and normals can point outward away from the corner (pointing to the obtuse angle where each line segment meets).

This is what Box2D does for its chain shape. A chain is a set of end to end connected line segments, and the narrow phase actually treats the connected endpoints as voronoi regions. You can check out the chain shape collision detection for an example implementation.

---

But since you're using only AABBs maybe a more hacky solution can work.

Another more hacky solution might be to fiddle around and add in a logic layer. Take the resulting manifold after merging close contact points. Then have some logic to see if the player is hitting a wall on the side (which would look like 2 contact points sharing the same normal). Then remove all other *singular* contact points that do not share the same normal, but keep other cases of hitting another wall (2 contact points with same normal).

Something very hacky like this may work, and it might be easier than doing a chain shape. The chain shape is pretty much collision detection on a mesh with adjacency information, but in 2D.


Edited by Randy Gaul, 27 April 2017 - 11:13 AM.


#16 Finalspace   Members   

1120
Like
0Likes
Like

Posted 27 April 2017 - 10:56 PM

Yeah you definitely can't drop cases with one contact. I just realized you must be treating the individual line segments as separate colliders. So what happens in the video is you do get a face to face contact, but clipping gives you one or two points. If the two point case, you have some merging code so it will probably be merged to a single point that looks like a vertex to vertex collision.

The problem becomes: how to treat the corner where to line segments meet end to end as a new and unique voronoi region. In your video each corner voronoi region would look like 1/4th of a circle, and normals can point outward away from the corner (pointing to the obtuse angle where each line segment meets).

This is what Box2D does for its chain shape. A chain is a set of end to end connected line segments, and the narrow phase actually treats the connected endpoints as voronoi regions. You can check out the chain shape collision detection for an example implementation.

---

But since you're using only AABBs maybe a more hacky solution can work.

Another more hacky solution might be to fiddle around and add in a logic layer. Take the resulting manifold after merging close contact points. Then have some logic to see if the player is hitting a wall on the side (which would look like 2 contact points sharing the same normal). Then remove all other *singular* contact points that do not share the same normal, but keep other cases of hitting another wall (2 contact points with same normal).

Something very hacky like this may work, and it might be easier than doing a chain shape. The chain shape is pretty much collision detection on a mesh with adjacency information, but in 2D.

 

This is the next thing i wanted to talk about:

 

But first i must clarify: I have a general physics solution including multiple shapes (planes, line segments, circles, polygons, boxs) and rotation dynamics support - i am not bound to aabb only. The video looks like it, because the player have a inverse inertia of zero - so it never rotates, but the internal is full rigid body - basically a extended version of box2d-lite full custom implemented - except for solving this is almost identical..

 

To get to the topic, you are totally right!

 

Currently i treat line segments the same case i do polygon vs polygon - but reduced the line segment to a single edge using SAT.

This is totally wrong and the reason why i made a separate line segment vs polygon case in my original javascript physics system in the first place - which i dont ported over to C for my current system.

Thinking smart like this: "Why do i made a separate case for line segment? No need its just a simple SAT call + the same code for vertex-based vs vertex-based shape" was not a good choice for this case.

 

So i will create a separate contact generator for line segment vs vertex-based by looking at the voronoi region only, so the normal is based on that region and not based on SAT - then everything should work just fine?

 

Also i will have a look at box2d source and see how that chain shape works, because its basically the thing i want... i dont want one line segment for each tile edge, but rather connected line segments -> The tile tracing returns just a array with a array of connected vertices anyway. So this would be much better i think.


Edited by Finalspace, 27 April 2017 - 11:06 PM.


#17 Finalspace   Members   

1120
Like
0Likes
Like

Posted 28 April 2017 - 04:52 AM

Which normal is correct for a chained line segment?

https://jsfiddle.net/6ekLfe9n/

 

- Locked surface normal? <- I assume this??

- Locked positive region?

- No lock at all?

 

Btw. i found the code for edge vs polygon in box2d: b2EPCollider::Collide()... Looks really complicated...


Edited by Finalspace, 28 April 2017 - 05:34 AM.


#18 Randy Gaul   Members   

2720
Like
0Likes
Like

Posted 29 April 2017 - 11:20 AM

Depends on what you want. With connected line segments the normal would be between the angle the two segments form, so something closer to the locked one is probably what you are after.


Edited by Randy Gaul, 29 April 2017 - 11:20 AM.