Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've been trying out some rope-physics recently, and I've found that the "standard" solution - making a rope from a series of objects strung together with springs or joints - is unsatisfying. Especially when rope swinging is relevant to gameplay. I don't really care about a rope's ability to wrap up or sag (this can be faked for visuals anyway).

For gameplay, what is important is the ability for the rope to wrap around the environment and then subsequently unwrap. It doesn't even have to behave like rope - a "wire" made up of straight line segments would do. Here's an illustration:

This is very similar to the "Ninja Rope" from the game Worms.

Because I'm using a 2D physics engine - my environment is made up of 2D convex polygons. (Specifically I am using SAT in Farseer.)

So my question is this: How would you implement the "wrapping" effect?

It seems pretty obvious that the wire will be made up of a series of line segments that "split" and "join". And the final (active) segment of that line, where the moving object attaches, will be a fixed-length joint.

But what is the maths / algorithm involved for determining when and where the active line segment needs to be split? And when it needs to be joined with the previous segment?

(Previously this question also asked about doing this for a dynamic environment - I've decided to split that off into other questions.)

share|improve this question

6 Answers 6

It's a while since I played Worms, but from what I remember - when the rope wraps around things, there's only one (straight) section of rope that's moving at any one time. The rest of the rope becomes static

So there's very little actual physics involved. The active section can be modelled as a single stiff spring with a mass on the end

The interesting bit will be the logic for splitting/joining inactive sections of the rope to/from the active section.

I'd imagine there'd be 2 main operations:

'Split' - The rope has intersected something. Split it at the intersection into an inactive section and the new, shorter, active section

'Join' - The active rope has moved into a position where the nearest intersection no longer exists (this may just be a simple angle/dot product test?). Rejoin 2 sections, creating a new, longer, active section

In a scene constructed from 2D polygons, all split points should be at a vertex on the collision mesh. Collision detection may simplify down to something along the lines of 'If the rope passes over a vertex on this update, split/join the rope at that vertex?

share|improve this answer
2  
This guy was right on the spot... Actually, it is not evne a "stiff" spring, you only rotate some straight line around... –  speeder Jul 22 '10 at 23:48
    
Your answer is technically correct. But I kind of assumed that having line segments and splitting and joining them was obvious. I'm interested in the actual algorithm/maths to do that. I've made my question more specific. –  Andrew Russell Jul 23 '10 at 4:16

To determine when to split the rope, you must look at the area that the rope covers each frame. What you do is you do a collision check with the area covered and your level geometry. The area that a swing covers should be an arc. If there is a collision, you need to make a new segment to the rope. Check for corners that collide with the swinging arc. If there are multiple corners that collide with the swing arc, you should pick the one where the angle between the rope during the previous frame and the collision point is the smallest.

Helpful diagram of the ninja rope situation

The way you do the collision detection is that for the root of the current rope segment, O, the rope's end position on the previous frame, A, the rope's end position on the current frame, B, and each corner point P in a polygonal level geometry, you calculate (OA x OP), (OP x OB) and (OA x OB), where "x" represents taking the Z coordinate of the cross product between the two vectors. If all three results have the same sign, negative or positive, and the length of OP is smaller than the length of the rope segment, the point P is within the area covered by the swing, and you should split the rope. If you have multiple colliding corner points, you'll want to use the first one that hits the rope, meaning the one where the angle between OA and OP is the smallest. Use dot product to determine the angle.

As for joining segments, do a comparison between the previous segment and the arc of your current segment. If the current segment has swung from left side to the right side or vice versa, you should join the segments.

For the math for joining segments we'll use the attachment point of the previous rope segment, Q, as well as the ones we had for the splitting case. So now, you'll want to compare the vectors QO, OA and OB. If the sign of (QO x OA) is different from the sign of (QO x OB), the rope has crossed from left to right or vice versa, and you should join the segments. This of course can also happen if the rope swings 180 degrees, so if you want the rope to be able to wrap around a single point in space instead of a polygonal shape, you might want to add a special case for that.

This method of course does assume that you are doing collision detection for the object hanging from the rope, so that it doesn't end up inside the level geometry.

share|improve this answer
    
The problem with this approach is that floating-point precision errors make it possible for the rope to go "through" a point. –  Andrew Russell Aug 2 '10 at 15:18

Check out how the ninja rope in Gusanos was implemented:

  • The rope acts like a particle until it attaches to something.
  • Once attached, the rope just applies a force onto the worm.
  • Attaching to dynamic objects (like other worms) is still a TODO: in this code.
  • I can't recall if wrapping around objects/corners is supported...

Relevant excerpt from ninjarope.cpp:


void NinjaRope::think()
{
    if ( m_length > game.options.ninja_rope_maxLength )
        m_length = game.options.ninja_rope_maxLength;

    if (!active)
        return;

    if ( justCreated && m_type->creation )
    {
        m_type->creation->run(this);
        justCreated = false;
    }

    for ( int i = 0; !deleteMe && i < m_type->repeat; ++i)
    {
        pos += spd;

        BaseVec<long> ipos(pos);

        // TODO: Try to attach to worms/objects

        Vec diff(m_worm->pos, pos);
        float curLen = diff.length();
        Vec force(diff * game.options.ninja_rope_pullForce);

        if(!game.level.getMaterial( ipos.x, ipos.y ).particle_pass)
        {
            if(!attached)
            {
                m_length = 450.f / 16.f - 1.0f;
                attached = true;
                spd.zero();
                if ( m_type->groundCollision  )
                    m_type->groundCollision->run(this);
            }
        }
        else
            attached = false;

        if(attached)
        {
            if(curLen > m_length)
            {
                m_worm->addSpeed(force / curLen);
            }
        }
        else
        {
            spd.y += m_type->gravity;

            if(curLen > m_length)
            {
                spd -= force / curLen;
            }
        }
    }
}
share|improve this answer
1  
Uhmn... this doesn't seem to answer my question at all. The entire point of my question is wrapping a rope around a world made of polygons. Gusanos seems to have no wrapping and a bitmap world. –  Andrew Russell Jul 16 '10 at 13:29

I'm afraid I can't give you a concrete algorithm off the top of my head, but it occurs to me that there are only two things that matter for detecting a collision for the ninja rope: any and all potentially colliding vertices on obstacles within a radius of the last "split" equal to the remaining length of the segment; and the current direction of swing (clockwise or counter clockwise). If you created a temporary list of angles from the "split" vertex to each of the nearby vertices, your algorithm would just need to care if your segment was about to swing past that angle for any given vertex. If it is, then you need to do a split operation, which is easy as pie -- It's just a line from the last split vertex to the new split, and then a new remainder is calculated.

I think only the vertices matter. If you're in danger of hitting a segment between vertices on an obstacle, then your normal collision detection for the guy hanging at the end of the rope should kick in. In other words, your rope is only ever going to "snag" on corners anyway, so the segments between won't matter.

Sorry I don't have anything concrete, but hopefully that gets you where you need to be, conceptually, to make this happen. :)

share|improve this answer

Here's a post which has links to papers about similar types of simulations (in engineering/academic contexts rather than for games): http://gamedev.stackexchange.com/a/10350/6398

I've tried at least two different approaches to collision detection+response for this sort of "wire" simulation (as seen in the game Umihara Kawase); at least, I think this is what you're after -- there doesn't seem to be a specific term for this sort of simulation, I just tend to call it "wire" rather than "rope" because it seems like most people consider "rope" to be synonymous with "a chain of particles". And, if you want the stick-ish behaviour of ninja rope (i.e it can push AND pull), this is sort of more like a rigid wire than a rope. Anyway..

Pekuja's answer is good, you can implement continuous collision detection by solving for the time when the signed area of the three points is 0.

(I can't fully recall OTOH but you can approach it as follows: find the time t when point a is contained in line passing through b,c, (I think I did this by solving for when dot(a-b,c-b) = 0 to find values of t), and then given a valid time 0<=t<1, find the parametric position s of a on the segment bc, i.e a = (1-s)*b + s*c and if a is between b and c (i.e if 0<=s<=1) it's a valid collision.

AFAICR you can approach it the other way around too (i.e solve for s and then plug this in to find t) but it's a lot less intuitive. (I'm sorry if this doesn't make any sense, I don't have time to dig up my notes and it's been a few years!))

So, you can now calculate all the times at which events happen (i.e rope nodes should be inserted or removed); process the earliest event (insert or remove a node) and then repeat/recurse until there are no more events between t=0 and t=1.

One warning about this approach: if the objects that the rope can wrap around are dynamic (especially if you're simulating them AND their effects on the rope, and vice-versa) then there can be problems if those objects clip/pass through each other -- the wire can become tangled. And it will definitely be challenging to prevent this sort of interaction/movement (the corners of objects slipping through each other) in a box2d-style physics simulation.. small amounts of penetration between objects is normal behaviour in that context.

(At least.. this was a problem with one of my implementations of "wire".)

A different solution, which is much more stable but which misses some collisions in certain conditions is to just use static tests (i.e don't worry about ordering by time, just recursively subdivide each segment in collision as you find them), which can be a lot more robust -- the wire won't tangle at corners and small amounts of penetration will be fine.

I think Pekuja's approach works for this too, however there are alternate approaches. One approach I've used is to add auxiliary collision data: at each convex vertex v in the world (i.e the corners of shapes which the rope can wrap around), add a point u forming the directed line segment uv, where u is some point "inside the corner" (i.e inside the world, "behind" v; to calculate u you can cast a ray inward from v along its interpolated normal and stop some distance after v or before the ray intersects with an edge of the world and exits the solid region. Or, you can just manually paint the segments into the world using a visual tool/level editor).

Anyway, you now have a set of "corner linesegs" uv; for each uv, and each segment ab in the wire, check if ab and uv intersect (i.e static, boolean lineseg-lineseg intersection query); if so, recurse (split the lineseg ab into av and vb, i.e insert v), recording which direction the rope bent at v. Then for each pair of neighbouring linesegs ab,bc in the wire, test if the current bend direction at b is the same as when b was generated (all of these "bend direction" tests are just signed-area tests); if not, merge the two segments into ac (i.e remove b).

Or maybe I merged and then split, I forget -- but it definitely works in at least one of the two possible orders! :)

Given all the wire segments calculated for the current frame, you can then simulate a distance constraint between the two wire endpoints (and you can even involve the interior points, i.e the contact points between the wire and the world, but that's a bit more involved).

Anyway, hopefully this will be of some use... the papers in the post I linked too should also give you some ideas.

share|improve this answer

One approach to this is to model the rope as collidable particles, connected by springs. (fairly stiff ones, possibly even just as a bone instead). The particles collide with the environment, making sure the rope wraps around items.

Here's a demo with source: http://www.ewjordan.com/rgbDemo/

(Move over to the right on the first level, there's a red rope you can interact with)

share|improve this answer
2  
Uh - this is specifically what I don't want (see the question). –  Andrew Russell Jul 23 '10 at 2:39
    
Ah. That wasn't clear from the original question. Thanks for taking the time to clarify it so much. (Great diagram!) I'd still go with a series of very small fixed joints, as opposed to doing the dynamic splits - unless it's a huge performance issue in your environment, it's much easier to code. –  Rachel Blum Jul 24 '10 at 0:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.