• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Finalspace

How to deal with getting stuck in sequential impulse?

18 posts in this topic

Posted (edited)

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?

Edited by Finalspace
1

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

Posted (edited)

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):

https://youtu.be/2NGwbZKCBJ0

 

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.

Edited by Finalspace
1

Share this post


Link to post
Share on other sites

@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

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

Posted (edited)

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
0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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

https://www.youtube.com/watch?v=TXvQjjVrETI&feature=youtu.be

0

Share this post


Link to post
Share on other sites

Posted (edited)

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:
 
https://www.youtube.com/watch?v=K-N6WJGOmVQ&feature=youtu.be
 
 
Should i just drop any vertex vs vertex contact entirely - detected by some distance threshold + dot product??? Edited by Finalspace
0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

Posted (edited)

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
0

Share this post


Link to post
Share on other sites

Posted (edited)

I solved it by just porting over the contact generation from box2d directly. At start i dont wanted to do that, but after looking into the box2d collision source very briefly i decided to port just the collision stuff over, because its really well implemented in a efficient way. I would have ended up remembering the adjacent edge informations anyway - which solves the getting stuck problem in a simple way.

 

Also i think storing and computing all manifolds in local space is really smart. I always stored and computed in world space which is harder and bad for contact caching coherence.

 

Right now this is all i need, so i am happy and can finally continue on my actual game code.

But when i need more than this, i will just use box2d directly and use a custom memory allocator.

Edited by Finalspace
1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0