Jump to content

View more

Image of the Day

Boxes as reward for our ranking mode. ヾ(☆▽☆)
#indiedev #gamedev #gameart #screenshotsaturday https://t.co/ALF1InmM7K
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
11 replies to this topic

#1 Finalspace   Members   

1056
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.

C#, Java, JavaScript are nice languages - Very Easy to code with - BUT it shakes your brain when you swap back to C or any other low level language...


#2 Aressera   Members   

2850
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   

2659
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   

1056
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.

C#, Java, JavaScript are nice languages - Very Easy to code with - BUT it shakes your brain when you swap back to C or any other low level language...


#5 felipefsdev   Members   

242
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   

2659
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   

242
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   

1056
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.

C#, Java, JavaScript are nice languages - Very Easy to code with - BUT it shakes your brain when you swap back to C or any other low level language...


#9 Randy Gaul   Members   

2659
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   

1056
Like
0Likes
Like

Posted 20 April 2017 - 01:57 PM

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


C#, Java, JavaScript are nice languages - Very Easy to code with - BUT it shakes your brain when you swap back to C or any other low level language...


#11 Finalspace   Members   

1056
Like
0Likes
Like

Posted Yesterday, 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, Yesterday, 12:38 PM.

C#, Java, JavaScript are nice languages - Very Easy to code with - BUT it shakes your brain when you swap back to C or any other low level language...


#12 Randy Gaul   Members   

2659
Like
0Likes
Like

Posted Yesterday, 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.