Can I jump from A to B?

Question

I'm making some rudimentary AI for my side-scroller and I need to know whether an AI unit can reach point B from point A simply by taking a jump.

Flight trajectory of my characters is a bit unusal as they can apply force in mid-air (like in Jazz Jackrabbit 2 for example), so unlike the classic trajectory of a projectile which is about...

path that a thrown or launched projectile will take (...) without propulsion.

... I suppose that my problem is more about a projectile with propulsion (e.g. rocket).

To illustrate this, this is how the flight curve looks like for my character if I jump and continually press the "left button" (it looks different at the left end, this is where I was making some manuevers in mid-air):

The force applied during flight is always parallel to the X axis, so it is F = (-f, 0) if I hold "left" and it is F = (f, 0) if I hold "right".

He can move very much like a ski jumper:

So it differs a lot from the classic trajectory which is simply a parabola (source: wikipedia):

To make it more difficult, I am simulating simple air resistance so my characters can accelerate only up to some maximum speed value.

This is done by applying a small force in the opposite direction of travel:

b2Vec2 vel = body->GetLinearVelocity();
float speed = vel.Normalize(); //normalizes vector and returns length
body->ApplyForce( AIR_RESISTANCE_MULT * speed * speed * -vel, body->GetWorldCenter() );

The AIR_RESISTANCE_MULT is a constant that in my case equals 0.1.

Let's assume that my character is an infinitely small point.

And I'm NOT taking obstructions into consideration, so my question goes like this...

How to determine (at least reliably guess), given initial velocity V, an impulse J = (0, -j) that I apply to the character upon jump, gravity G = (0, g), force F = (+-f, 0) continually applied during flight and AIR_RESISTANCE_MULT if we really decide to take air resistance into account (this is optional) , whether a point lies below the curve drawn by the path my character will take?

I have literally no idea where to start with the calculations and in fact, I am not necessarily interested in an exact answer; a well working hack/approximation would be great as the AI by no means needs to act perfectly.

edit: I've decided to solve this using simulation as Jason suggests, but how to handle such a case?

Should I draw a segment from C to D and check whether the desired point lies below this segment?

Or should I binary search the timesteps between C and D to look for the point that is close enough in horizontal distance to the desired point, and only then check the vertical difference? (seems a bit overkill to me)

Answer 1

As you state, the best choice is to approximate, in this case using a numerical scheme. Divide time into large timesteps (say 100-300ms), and use the parabolic approximation for each timestep. The forces are the same throughout except air resistance. The parabolic path is basically for constant acceleration, but with air resistance the acceleration changes because the force depends on speed. A reasonable approximation is to treat air resistance as constant over each timestep. But using a quadratic (i.e. parabolic) approximation when integrating allows you to handle much larger timesteps. Then you just compute until a parabola crosses the desired point in the horizontal direction, and then compare the heights.

EDIT: A little more detail about the comparison. You know that over the timestep (which could be many in game frames), that the player crosses the target <targetx,targety>. Their path is described by the position <ax*t^2 + bx*t + cx, ay*t^2 + by*t + cy> where:

ax = 1/2 * accel.x
bx = velocity.x
cx = position.x

t is the time through the timestep (0 <= t <= dt) and similarly for y. So when t=0 the character is at the previous position, and when t=dt, they are at the next position. Note that this is basically the Euler update with dt replaced by t so that we can calculate anywhere along the trajectory. Now we know the x-position is a quadratic function, so we can solve ax*t^2 + bx*t + cx = targetx and get (up to) two times during the step in which the character is directly above or below the target. Then we throw out any solutions that aren't in the range [0, dt], as these aren't in the current timestep. (For robustness, add a small constant to the ends of the range so you don't have round off problems). Now we could have no solutions (after filtering), in which case we don't hit the target this timestep. Otherwise, we evaluate ay*t^2 + by*t + cy at the solutions, and compare this y with targety. Note that you could be above the target at one point in your trajectory, and below it later (or vice-versa). You'll need to interpret such situations according to what you want to do.

Considering a bunch of timesteps is much easier than finding an analytic solution to the original problem, and far more flexible as you can change the motion model and this will still roughly work.

Bonus points for using variable steps, for example, 100ms for the first second (ten points), 200ms for the next two (ten more points), 400ms over 4 seconds, etc. In fact, as your character approaches terminal velocity the variation in the resistance goes down, and you don't need larger timesteps anyway. This way you can handle really long jumps without too much processing, as the complexity for T seconds is O(log T) rather than O(T).

You can also simulate what happens when the character stops boosting partway through their jump, or starts boosting the other way. With the above trick the complexity is O((log T)^2), which isn't too bad.

Answer 2

Yay! I did it!

I'm using simple simulation that takes the first position to land behind the vertical axis of the target point - from there, I take the previous simulated position and make a segment. Now I check whether the target point is below this segment. If it is - we can jump there.

It's a player-controlled character on the gif. Pink is the predicted path, yellow segments are predicted subsequent stepping positions, and the final segment turns white if the target point lies below it, red otherwise. Red curve is the actual flight path. There are some slight inaccuracies due to physics state interpolation turned on.

The calculations turned out to be surprisingly easy, however making my environment work the same way as these pure calculations do... was a massive pain in the butt. At least I solved some serious bugs out there, so it was a useful exercise after all.

Here is the complete code in Lua used to solve the original problem (the code assumes you have your own "debug_draw" routine and your own vector class with basic methods like "length_sq" (length squared), "normalize" or operators +,*:

function simple_integration(p, dt)
    local new_p = {}

    new_p.acc = p.acc
    new_p.vel = p.vel + p.acc * dt 
    new_p.pos = p.pos + new_p.vel * dt
    -- uncomment this if you want to use quadratic integration
    -- but with small timesteps even this is an overkill since Box2D itself uses traditional Euler
    -- and I found that for calculations to be accurate I either way must keep the timesteps very low at the beginning of the jump
     --+ p.acc * dt * dt * 0.5

    return new_p
end

function point_below_segment(a, b, p)
    -- make sure a is to the left
    if a.x > b.x then a,b = b,a end

    return ((b.x - a.x)*(p.y - a.y) - (b.y - a.y)*(p.x - a.x)) < 0
end

-- returns true or false
function can_point_be_reached_by_jump
(
gravity, -- vector (meters per seconds^2)
movement_force, -- vector (meters per seconds^2)
air_resistance_mult, -- scalar
queried_point, -- vector (meters)
starting_position, -- vector (meters)
starting_velocity, -- vector (meters per seconds)
jump_impulse, -- vector (meters per seconds)
mass -- scalar (kilogrammes)
)

    local my_point = {
        pos = starting_position,
        vel = starting_velocity + jump_impulse/mass
    }

    local direction_left = movement_force.x < 0
    local step = 1/60

    while true do           
        -- calculate resultant force
        my_point.acc = 
        -- air resistance (multiplier * squared length of the velocity * opposite normalized velocity)
        (vec2(my_point.vel):normalize() * -1 * air_resistance_mult * my_point.vel:length_sq()) / mass
        -- remaining forces
        + gravity + movement_force/mass

        -- I discard any timestep optimizations at the moment as they are very context specific
        local new_p = simple_integration(my_point, step)

        debug_draw(my_point.pos, new_p.pos, 255, 0, 255, 255)
        debug_draw(new_p.pos, new_p.pos+vec2(0, -1), 255, 255, 0, 255)

        if (direction_left and new_p.pos.x < queried_point.x) or (not direction_left and new_p.pos.x > queried_point.x) then
            if point_below_segment(new_p.pos, my_point.pos, queried_point) then
                debug_draw(new_p.pos, my_point.pos, 255, 0, 0, 255)
                return true
            else
                debug_draw(new_p.pos, my_point.pos, 255, 255, 255, 255)
                return false
            end
        else 
            my_point = new_p
        end
    end

    return false
end

Accept goes to Jason for setting me into the right direction! Thanks!

Answer 3

You might want to "just calculate" the answer but I'm sure that you'll find it insufficient once you've got it because of the highly interactive nature of your "free fall" physics.

Consider using a different approach: Searching. Here is how it's done for Super Mario AI: http://aigamedev.com/open/interview/mario-ai/

Searching possible pathes to get from A to B allows for unlimited interactivity in mid-air while still being computationally efficient.