10
\$\begingroup\$

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): enter image description here

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:

enter image description here

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

enter image description here

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? enter image description here

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)

\$\endgroup\$
1

3 Answers 3

4
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ +1, Great answer! How could I not consider the actual simulation. Could you please elaborate on "parabolic approximation" (I don't quite understand)? Do you just mean the method of integrating velocities, like for example RK4 and Euler? If so, could you explain it or at least link to some information on how to perform it? \$\endgroup\$ Feb 6, 2014 at 2:39
  • 1
    \$\begingroup\$ Normally you do x'= x + v*dt. Instead use x' = x + v*dt + 1/2*a*dt*dt. When dt is small, dt^2 is tiny, so generally it is left out in traditional Euler integration in games. Here dt is not small, so you need the acceleration term. Since dt is raised to the second power, this is a quadratic integration, and the path is a parabola, hence parabolic approximation. RK4 essentially calculates higher derivatives, and so could give cubic, quartic, quintic, etc. approximations. RK4 is overkill for this, most likely, as stability is not important. \$\endgroup\$
    – user41442
    Feb 6, 2014 at 2:52
  • \$\begingroup\$ and I suppose velocity itself should be integrated like in traditional Euler? v' = v + a*dt \$\endgroup\$ Feb 6, 2014 at 3:03
  • 1
    \$\begingroup\$ Yep. You don't have jerk, you are assuming it is zero. \$\endgroup\$
    – user41442
    Feb 6, 2014 at 3:40
  • \$\begingroup\$ Please take a look at the edit. \$\endgroup\$ Feb 6, 2014 at 14:09
4
\$\begingroup\$

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.

enter image description here

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ That is only practical for certain worlds. In particular Mario limits the size of the search graph by being roughly linear, having a limited number of velocities, and having an excellent heuristic. Depending on the game, this might not be true. Also computationally efficient is relative, as this AI would likely have to work for more than one character/enemy, whereas in Mario there is just one to control. \$\endgroup\$
    – user41442
    Feb 6, 2014 at 2:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .