mario math – part 2

To calculate Mario’s position with KEY_RIGHT pressed down continuously for n frames:

let

at frame 1:

at frame 2:

at frame 3:

at frame 4:

If you multiply everything through, a pattern starts to emerge:

So we can say that in general, Mario’s position after n frames will be:

But we’d like a formula we can evaluate in O(1), so massaging the equation a bit we get:

Both of sums in the above equation, we have identities for:
      and      

Of which the second one is kind of convoluted, but allows us to come up with:

Which can then write in Java as:

public float positionAfter(float accel, int nFrames) {
    float term1 = n * (1 - Math.pow(.89, nFrames + 1)) / .11;
    float term2 = (Math.pow(.89, nFrames + 1) * (-.11 - 1) + .89) / .2079;
    return a * (term1 - term2);
}

The (.89) term is friction (I think?) and on the ground the code uses that value. In the air, the dynamics and equations are the same, but use a different coefficient of friction: (.85). The initial acceleration of a jump is vastly different, though, so I’ll tackle that in the next Mario Math installment.

mario math

To calculate Mario’s velocity, with KEY_RIGHT pressed down continuously for n frames:

let (1.2 if KEY_SPEED is held down as well)

at frame one, then, your velocity

frame 2:
frame 3:
frame 4:

which, if you multiply through, looks like this:

Which makes it a bit easier to generalize Mario’s velocity at any frame n:

we know from paying attention in high school wikipedia that:

however, our sequence only goes to n-1 frames. It’s missing the last term:

subtracting xⁿ from both sides

which we could have maybe figured out faster if we had remembered this identity:

replacing the lower m with 0 and upper n with n-1 we get:

which multiplied by is what we found earlier.

and so mario’s velocity after n frames of acceleration is:

which can be calculated in constant time by this Java function:

public float velocityAfter(float accel, int nFrames) {
    return accel * ((1 - Math.pow(0.89, nFrames)) / 0.11);
}

Whew.

Thanks to Heath Borders and my co-blogger Ben for working this out on a whiteboard with me.

tour de mario – jumping

My co-blogger Ben and I are working on an entry for the Mario AI Competition 2009. The idea is to develop a Java program that simulates button presses to guide Mario through randomly generated levels of increasing difficulty. The competition is aimed at exploring Artificial Intelligence methods in gaming, but before Ben and I can even get to that, I think a short tour of the code we will be working with is in order.

Jumping is key in Mario. Maybe more precisely, landing is key. Controlling where you land will stomp an enemy or clear a gap. Jumping is easy, landing is hard.

Since this is so integral, let’s take a look at the code that makes Mario tick.

The class ch.idsia.mario.engine.sprites.Mario controls Mario’s behavior.

The tick() method of Mario’s superclass, Sprite is called once for every frame of the game, 24/sec. tick() is pretty simple, it just calls move(), which Mario happens to implement.

The move() method has a lot of code in it — 224 lines — but at it’s core, it just sets the xa and ya variables — x-acceleration and y-acceleration — and then uses them to increment Mario’s current x and y position variables.

move() starts on line 156, but doesn’t start doing anything we’re interested in until line 211:

        float sideWaysSpeed = keys[KEY_SPEED] ? 1.2f : 0.6f;

Mario moves horizontally at a rate 0.6 per frame at normal speed and 1.2 when the SPEED key is pressed.

The jumping code starts on line 234. I’ve left out the conditions we don’t care about:

if(keys[KEY_JUMP] || ...) {
    ...
    if(onGround && mayJump) {
        xJumpSpeed = 0;
        yJumpSpeed = -1.9f;
        jumpTime = 7;
        ya = jumpTime * yJumpSpeed;
        onGround = false;
        sliding = false;
    }
    ...
    else if(jumpTime > 0) {
        xa += xJumpSpeed;
        ya = jumpTime * yJumpSpeed;
        jumpTime--;
    }
}

This is the heart of the jump. jumpTime is a frame counter variable, and a jump lasts 7 frames. I’m not positive, but I think that the y-origin is in the upper right of the screen, hence the negative yJumpSpeed. After 7 frames, jumpTime is reset to 0.

There are extra bits of code that limit Mario’s maximum acceleration to 8, cut Mario’s xa and ya to 85% of their value and every frame that Mario isn’t on the ground his y-acceleration is is decreased by 3.

        ya *= 0.85f;        
        if (!onGround) {
            ya += 3;
        }

But it’s enough to figure out where you’re going to land.

Update
I made a couple of mistakes, which are crossed out above, and besides the mention of sideWaysSpeed I didn’t mention anything about horizontal speeds. As you can see above, when you are in the air xJumpSpeed starts out as 0 and you don’t gain any acceleration from it for the duration of your jump. The code that sets your horizontal acceleration regardless of whether you are on the ground or not is at line 288:

        if (keys[KEY_RIGHT] && !ducking) {
            if (facing == -1) sliding = false;
            xa += sideWaysSpeed;
            if (jumpTime >= 0) facing = 1;
        }

which merely sets your acceleration depending on what direction you are pressing.