Calculating jump speed

In my game, I'm at the point where I have to implement a good jumping algorithm So, I thought that I base my algorithm on real physics. And that's why I need to know:

If a person jumps a specific height, what is the mathematical formula to calculate how long the jump will take until the person lands on the ground again? (Assuming Earth's gravity.)

Then, when we know how long the jump of a specific height takes, how do I calculate in what height the person will be at any given time of the jump?

I'm pretty sure there is a formula for this. From this formula, I will calculate at which frame of the jump the player will have which y position and save these values into a lookup table. But first of all I need to know the general mathematical formula itself.

Does anybody know where I can find this?

Your questions are more suitable for a school exam than for a game...

Since a game's state is modified progressively, one step/frame at a time, you don't need to know "in what height the person will be at any given time", you just update their position for the next frame. Similarly, you don't need to know how long the jump will take, because you don't need to manually hardcode that amount of time into NES frames.

What games typically do, is give the object a large negative Y velocity. Say, -6 pixels per frame. Then you need gravity to prevent the object from moving up indefinitely. Gravity should have a much smaller value, maybe around 0.3 pixels per frame. Then every frame you add the object's Y velocity to its Y coordinate, and also add the gravity to the Y velocity, so it will slowly move towards 0, at which point the object will at the peak of its jump. Continue to add gravity to the speed and it will become positive, effectively pushing the object down.

You can tweak the initial velocity of the jump and the amount of gravity until the jump matches your desired height and duration. I remember someone saying they didn't even add gravity during the first steps of the jump, which was necessary to match the effect they wanted.

This might not be the most physically accurate way to describe jumps, but nearly every game with decent physics you ever played does it like this, and you certainly won't get anything much more accurate than this out of an 8-bit CPU running at 1.79MHz.

Real physics will look wrong in a game. In real life, you can only jump about half your height, and be in the air about a second. That's a vertical movement of about 1/2 of a pixel per frame to a max of 16 pixels of vertical movement. That would be very dull gameplay.

d = v₀t + 1/2 a t²?

d being height, v₀ being at what speed you initially jump, and a being gravity, or -9.8m/s²

I could be wrong, but I believe solving for t would give you the time.

Of course, I have no idea how you'd translate this to the NES

Triple ninja'd. But whatever:


I'll get the integral calculus* out of the way first:

Acceleration: d^2y/dt^2 = g

Velocity: dy/dt = g*t

Displacement: y = g*t^2/2

where y is height, g is the acceleration due to gravity, and t is time since the peak of the jump. Assuming SI units and Earth conditions, y is in meters, t is in seconds, and g = 9.80665 m/s^2.

Given y, you want to find 2*t, as half the time is spent rising and the other half falling. From here on, everything is algebra.

y = g*t^2/2
2*y = g*t^2
2*y/g = t^2
sqrt(2*y/g) = t
2*sqrt(2*y/g) = 2*t

Now that you have t, the time from jumping from peak or the time from peak to landing, the magnitude of the vertical component of velocity at the start and end of the jump is g*t.


Usually it's done with Euler integration, which is how mathematicians describe the process that tokumaru described above. Set the initial velocity at the start of the jump, then add gravity (converted to subpixels per frame squared) to the object's velocity every frame, and add the object's velocity to its displacement every frame.

If you can provide a particular height or hang time, a particular scale (in units such as pixels per meter), and a particular frame rate (in frames per second), I can demonstrate how to translate this into 6502 code.


* Integral calculus is the area between the gum line and the tartar line. Differential calculus is the rate of growth of tartar over time.

Also note that Euler integration is an approximation, meaning it accumulates errors over the course of the jump, so the continuous calculus formula is really only a (good) estimate of what your game is going to do.

What I suggest is to write a small program, in python or otherwise, that just runs the jump/gravity simulation for as many frames as it takes to land, and collects statistics: frames in the air, highest point reached, maximum horizontal span, etc.

Pick some starting constants using calculus, and then put them into your little simulator, and tweak them until you get the jump you want coming out of it.

Looks like the mathematical stuff is more complicated than I thought. So, I guess I'll go with tokumaru's suggestion.

However, since this method uses floating point calculations, I guess I will pre-calculate the heights of each frame of the jump and put these values into a lookup array, so that the jumping routine just needs to read from that array to see how many pixels the character needs to move up or down in each frame.

How do real games do this calculation? Do they use a lookup array as well, with the array being long enough so that a jump starting from the highest possible position and going down to the lowest bottom can still be looked up?
Or do they actually calculate the current value immediately? If yes, wouldn't this be slow since it uses floating point calculations?

To check if I got the idea right, is this general code to calculate these values correct?


And another question: In how far does the gravity value relate to the actual real gravity? Let's say I want to try out the real Earth's gravity of 9.80665 m/s². How do I convert this value into the gravity constant of the program?

In games, floating-point math is normally replaced by fixed-point math, which is fast enough for fractional movement even in slow 8-bit CPUs. The basic idea is that you use an additional byte to represent the fractional part of positions, velocities, etc. and when the fractional part overflows or underflows, this is propagated to the integer part of the numbers.

I don't know if this is helpful, but...

http://hamaluik.com/posts/super-mario-world-physics/

Alright, I wrote another little test program to check these values. (I didn't optimize for the NES, like using global variables instead of function parameters etc.)

Can you please tell me whether everything is correct according to what you described me?

The below is an example of what you need for jumping, with details such as collision and ejection left out. If anyone notices anything that can be improved in the below, I'd be eager to learn it. *edit* I'll try to read your C code and comment, but I posted this asm example partially for my own practice in explaining things to others, so I apologize in advance if this is not immediately helpful to you for your C implementation. Conceptually though you could translate this to C pretty easily.



*edit* I forgot to mention, the two highest bytes of the 3 byte y coordinate would be your 16 bit world coordinate. The lowest byte is sub-pixel precision.

If this was directed specifically towards me and not a general code snipped:
Thanks, but I already know how to implement movement functions, i.e. how to react to user input and level environment. In fact, I already have a fully working jumping function in my game. It's just that the Y value is calculated in a pretty basic way.

I just wanted to know whether the calculation in my above sample code is correct in the way that tokumaru described.
The actual NES implementation won't be a problem. I just need to know if the general algorithm for calculating the Y value is correct so far.

What I posted is a 6502 implementation of what tokumaru described...unless I'm completely missing something above.

O.k., but all I wanted to know is: The general C++ code that I wrote above, is this one correct? This is not about 6502 yet. I just need to know whether the code that I already wrote to demonstrate the jumping algorithm is correct the way it is implemented or if you find an error.

Here's how I'd do it in pseudo C. Note as above I picked arbitrary constants. If I were building a real game, I'd tweak these until I got the arc I wanted.

Again: I don't need any code because I've written one myself. See above.
All I want to know is: Does my code contain any errors? Did I understand anything wrong or is the above sample code, written by me, a correct implementation of tokumaru's description?
That's all I need to know. I'm not in a situation where I don't know how to go on or where my program has a bug. I just want to know: Is my above code correct or did I miss something?

Your code makes sense and seems to implement the same idea---but to be honest I was thrown off by your having a velocityPoint and velocityBase...what are these for?

That's the fixed point stuff. VelocityBase is the value before the dot and VelocityPoint is the value after the dot. As soon as VelocityPoint gets over 100, VelocityBase is incremented. Just like when you add 0.30 to the value 6.90, you get 7.20. VelocityBase would be the 7 and VelocityPoint would be the 20.

Ah, that makes sense. I suppose you could do it that way, seems more compact to do what I recommended above: long for your y coordinate, so the lowest byte is 8 bit sub pixel precision, next two higher bytes are 16 bit world coordinates, highest byte is don't care unless you have a huge world. 16 bit (int) for your y velocity. Then C can take care of the sign extension for you just with a +=. Then you just shift right by 8 or figure out how to use pointer math to just get at the two bytes above the lowest byte in your long y coordinate, to get your Y world coordinate. Again---I'm not too experienced with C on the NES, so I'm unsure how to weigh the advantages or disadvantages of these approaches. *edit* My problem is I think in 6502 first, so I'm probably doing a bad job of helping you with your C implementation. I'll let rainwarrior or another C user take over from here...thanks for the practice, though

O.k., so your comma values are based on the value 256 instead of 100. I.e. in my case, the gravity wouldn't have the value 30, but the value 77. Yeah, this is also a way. In Assembly it makes it easier to check for the overflow. Also, in this case, one doesn't need to reset the value to VelocityPoint -= 100.

Although I wouldn't put this into the Y variable. The general Y variable in my game is an int variable. (If you couldn't fall out of the screen, byte/unsigned char would even be enough.) The whole comma values only have a meaning when jumping and falling, but not during the rest of the gameplay. So, the comma value is of course put into a separate byte variable. Otherwise, I would have to shift that value whenever I want to check for the actual absolute Y value.

You don't have to shift it...You could convert the (2 bytes above the lowest byte) of long y into an int like this: (I put in a comment about figuring this out because I wasn't sure I could just rattle it off without testing it...pointer math can get confusing)
int actual_y_coordinate = *((int*) (&y_coordinate + 1)); //I think this is right?

*edit* I'll add yet another disclaimer that, I know how troublesome C is on the NES, and for all I know the above generates about eighty billion instructions just to do that little thing.

Doing this will just copy the current value to actual_y_coordinate once. I.e. you have to do this every time if you always want to have the current value.

Yes, I know, in Assembly, you can just declare:

and then just take care that the YWithComma label always works with three bytes and the YWitoutComma label works with two bytes.

This doesn't work in C.

Sure, I could declare an array of three bytes and then work with some pointers.

But firstly, there is no three bytes data type, so I would have to use long, i.e. four bytes, when I want to calculate the whole value. This wastes one byte in RAM and also in terms of speed.

And secondly, working with pointers means that the Assembly code works with indirect addressing and not like if you actually use a regular variable.

I don't know whether there's some hack that allows me to share memory between two variables and still access them with the absolute addresses. But I think it would be very non-intuitive for C and would look more like an ugly hack.
So, the combination of one Y variable and one comma variable is probably the best.

Seems like a good approach then. Off topic: Yeah...speaking for myself I got utterly scared off of C a couple of weeks ago (after making a sincere attempt to adopt it). For one, I'm already comfortable with 6502. Another, I've completed two games and I ran into more than enough trouble fitting everything in to a cartridge just with my 6502 code and very sparing use of macros. I shudder to think of building a complete game in C. Not saying it can't be done! And more power to you. But *shudder*. Hahahah. Also there are so many options of what to do, and because the C compiler is so, so, SO terrible at generating code it almost seems like you have to spend MORE time tinkering with your code to get it to not be utterly terrible when actually compiled. I...really don't want to struggle with that. That's just me though---good luck to you

*edit* actually yeah, I wonder if you could use a union to pull off the same trick of embedding an int inside a long, as long as you put a dummy byte (for the sub pixel byte) in the right location to account for little endian on the NES? Then you wouldn't need pointer math or copying or shifting. *edit* Maybe you'd need a struct that consists of a char, and an int, and then create a union between that struct and a long. Then you use the long as the y coordinate, and then pull out the int from the struct to get the world y coordinate. No idea how that'd turn out in compiled code, but it sounds like something fun to try anyway.

I didn't have many issues with using C. If I had to program completely in Assembly, I would have never made it. (In fact, I would have never started in the first place.)

I program the low level stuff in Assembly:
- Everything where the NES registers are accessed.
- Everything that is done during VBlank.
- Some general purpose functions, like copying or filling an array.

But the whole game logic is done in C. And I didn't really have any issues with it.

My game has approximately the complexity of "Kung Fu" (maybe some fewer opponents). And I still have about 40% of ROM space (standard 32 + 8 KB NROM cartridge) with more or less only the enemy movements remaining as major features. (In the moment, only two of seven enemy types do anything.)

I guess I might run into a lag again when I add two more enemies to the screen and finish their movements.
In the moment, there can be two enemy characters on screen at once. The aim is two human-sized enemies of 16 x 40 or 16 x 48 pixels, one small object 16 x 16 and one tiny projectile 16 x 8. Plus the player character of course (also 16 x 40. Plus 16 x 8 for the weapon).
For some reason, the collision check between the player's weapon and the enemies takes the most time. I'll have to do some major optimizations here, maybe indeed writing it in Assembly. It's probably the loop.

But other than that, I have a fully working framework and the whole development process went pretty smoothly. Until now, I wasn't forced to do any actual game logic in Assembly, if I remember correctly.
In the moment, Assembly is just the low level and general purpose stuff, i.e. the things that you can reuse in every game.
But for example the physics of the game or the MovePlayer, MoveEnemyA, MoveEnemyB are still 100 % C.

Please don't get me wrong, I think its awesome folks are successfully building games in C. It's just not for me. What do you think of trying the union idea I added as an edit to the previous post? Sounds kinda fun to try, but as I've abandoned C, I won't be trying it myself. Unions seem pretty idiomatic to C, not really a hack.

No problem.


Right. I totally forgot about them. I never used a union ever. But maybe it's worth a look.

Hmm. So, when I declare this:


Doesn't this mean that the y variable occupies the two highest bytes?

Your idea was that:
Unused, HighByteY, LowByteY, Comma

But the union would probably save it like this:
HighByteY, LowByteY, Comma, Unused

And this doesn't work without shifting.

Or is there a way to tell the union that variable y shall occupy the second and third byte instead of the first and second?

Yeah...I was thinking something like (and this is pseudo C, so I might have something backwards somewhere)

I assume the order where the bytes for the variables are stored in a union is undefined. So, you cannot be sure that a specific byte of one variable overlaps with another.

As far as I understand it, unions are when you only need one of various different variables at the same time, so they can share their space.
Once you set one variable of a union, consider the others destroyed.
Relying on the fact that you write a = 3 and can still use b, this is probably undefined behavior and therefore a hack.

The order should be defined by your struct though, and I would think a union would guarantee the two members at least start at the same location in memory---in which case I'd expect something like this would work. I honestly haven't tried this though so...not certain how it would turn out in practice. We're talking about C...it's almost assembly, hacks aren't necessarily bad always. Unions are built into the language...the language is MEANT for low level stuff like this. But yeah..if I missed something here and my assumptions are wrong...can't do it this way I suppose.

There's also the problem whether the program is highest byte first or lowest byte first. So, you can't rely on the order in the struct because in an architeture with highest byte first, you would have to put the char variable behind the int variable.

Nah, I'll just use two variables. As I already suspected: Everything else are hacks. Unions are probably intended to have only one valid variable at a time. But what we're trying to do here is having two variables that share the same space, but that are both always valid at the same time. And that's probably not what a union is created for.

Yes of course I considered endianness (and made assumptions since I can't test this right now), but felt it was a reasonable assumption you were talking about making non portable code for the NES. I can't imagine writing a game that is portable to NES and PC, there would have to be so much crap and #ifdefs all over the place, it'd be pretty gross!

*edit* I think your approach is fine, but I enjoyed this discussion about trying a union.

*edit* TBH, your approach could be described as a hack, too, since you're having to use something other than the cpu's normal operation to imitate fixed point math--and have to do several comparisons where with the addition approach in 6502 (or hacked in C), you don't have to do these additional comparisons. So I mean...try everything out before you decide which is the best approach. Since this is a pretty short calculation and likely not the biggest time sink in a full frame update for your game it probably isn't bad, still, though. Again, thinking in 6502...

*edit* What is a hack? Seems like---fixed point math is not natively supported in C, so you have to do something to imitate it. So anything you implement will be a hack.

Just use a 16-bit int, let the compiler's support for 16-bit ints do the work, and right shift the coordinate by 8 before displaying the sprite.

This was my first suggestion, with the addition of a 16 bit world coordinate for Y in case one is doing a game that's larger than one screen high. Probably is the simplest approach with plain C. Interesting discussion ensued though!

Sure, the code is not portable. But I still prefer to use C constructs in the way they are intended.


There is a difference between a programming trick or compensation for missing features and a hack. My approach is not a hack because it is still valid C. I don't violate the language features to create a code that does something the language was never intended to do. I just use an alternate version to implement a program feature. This method will still work with any C compiler since it's totally well-defined and valid C.

A hack is something like the stuff we tried to do with the union:
From the language's point of view, you are only supposed to use one of the properties at a time. The others are in an undefined status.
Now, if you use the union in a way that both properties are valid at the same time, then you do something the language isn't designed to do. This is dangerous behavior because you rely on the fact that the compiler's internal operations work in a specific way. Even if big and little endian is fixed, this doesn't give you the guarantee that a two bytes variable in a four bytes memory is located at the beginning. If the creator of the compiler decides to shift the data internally in the next version, then the program will break as soon as you update the compiler.

There might be some things that, in any other context, would be considered bad writing style. Like using global variables and no function parameters. Or using two separate variables for fixed point math. But these are still valid language constructs that act in a pre-defined way and someone who reads the code can understand it.

Hacks are the things where you rely on the fact that the internal implementation of the compiler does a certain thing in a certain way. You abuse a feature that isn't supported by the language and whose behavior is actually undefined and it just works because you tried it out and adjusted your code, so that it matches the way the compiler implemented it. Someone who reads the code might have a hard time understanding what you're trying to do and it might break in a future version of the compiler.



This might work if I didn't use a 16 bit integer for the X and Y coordinate to begin with. I need an int to decide whether a certain character is even within the visual area of the screen. So, for jumping and comma values, I need that integer and a byte variable.

Also, using an int or a long for these operations (letting the lowest byte being the comma value and the second to lowest byte being the actual lowest byte of the integer number) has its own performance problems because it wouldn't be just shifting the value during the output. You also have to shift the value whenever you do a collision check with the environment. For every single character. Even if this character cannot even jump.

I guess there would be too many potential side effects that you have to remember and adjust to in your code if you have a Y coordinate whose value doesn't equal the actual Y position, but where the position is (value >> 8).
Having a separate value for the comma stuff on the other hand makes no fuss: You work with your Y value as always. And that comma value is just used for jumping. You have one place in the entire code where you do a manual if comma >= 100 then ++Y, comma -= 100 and that's it.