Little Ninja: Physics and Collision Detection

I’ve been meaning to write something explaining some of the physics and collision detection behind Little Ninja for awhile now, but I really wanted the engine to be at a point where the movement of the ninja and his interactions with the terrain were pretty much finished. This way I can share not only the basics of writing a physics engine for a platformer, but also the many adjustments that have to be made to make it feel and look authentic. The last couple of days I’ve probably spent more time running and jumping around the terrain than actually working on the physics for the game (the fact that Yuan Hao has greatly improved the map editor making it very easy for us to create new maps has a lot to do with this). This makes me feel confident enough in the current state of the game’s engine to share it with the interwebz.

Little Ninja’s Universe

I’ll use the word sprite to talk about the characters in the game sometimes (including the Little Ninja). Sprites are pre-rendered 2d images that are integrated into a larger scene used in videogames mainly to display characters on screen.
The game is tile based, each tile consists of a square of 16×16 pixels (pixels are the smallest controllable element of a picture represented on the screen). We’re using pixels as the unit of length, as I will be for the rest of this post.
Little Ninja runs at 60 fps (frames per second), which means that the screen is refreshed 60 times every second. Frames are used as the unit of time.
A horizontal speed of 7 (pixels per frame) means that on every frame, the ninja moves 7 pixels to the right, if it were -7 he’d be moving the same distance to the left. Similarly, a vertical speed of 5 means the ninja is falling at 5 pixels per frame, and -5 means he’s moving up 5 pixels on each frame.

Lateral Motion

This is the first thing that needs to be taken care of, but also the easiest. Assuming infinite acceleration (meaning the character will transition from an idle position to full speed as soon as its detected that the button to walk or run is being pressed), this can be done by changing the position of the character in the map based on its lateral speed. This process is called integration:

This function is executed for every sprite on every frame, so all that needs to be done for a sprite to move horizontally is set its speed value.

Vertical Motion

Integrating a sprite vertically is slightly trickier, since (unless it’s a flying character) gravity should always affect its vertical motion. Given our units, gravity should be expressed in p/f² (pixels per frame squared). Now, I hate squared units, they make everything seem much more complicated than what it really is. A gravity on Earth of 9.8m/s² just means that each second, a free falling object’s speed increases by 9.8m/s; the speed increases 9.8 meters per second every second (hence 9.8m/s²). Simulating gravity just means increasing the sprite’s speed by a constant number on every frame before it’s integrated. For a character to jump all you need to do is set a value for its y speed and let the integrate function take care of the rest:

Notice that instead of having a global value for gravity (which would be more realistic), I’m using an attribute of the sprite. What this does is allow us to create characters that fall at different rates (or not at all); take Street Fighter’s Dhalsim for example, all it takes for his jumps to feel so floaty is a smaller value for his gravity.

One adjustment you might have to make is setting a terminal velocity. If the character is jumping off a platform that’s too high, the speed quickly becomes too great for the player to handle, so it’s important to set a limit to the y speed:

You can apply this to lateral movement as well if you want to have your character accelerate, these are the things that make each game or even character within a game feel unique. Mario for instance takes quite awhile before reaching max speed when walking while Mega Man changes from idle to max speed instantly.

Collisions

One thing you might notice in the code of the integrate function is that it just moves the sprite based on its x and y speed with no regard to the its surroundings. If there’s a wall in front of the sprite there’s nothing that’ll stop it from going right through it. Collision detection and response deals with this issue. This article deals only with collisions between sprites and the terrain since collisions between sprites are being handled quite differently and will be described in a later post. For the sake of simplicity, I’ll talk about the ninja as if he were a single pixel.

To maintain the illusion of a solid world, two things need to be done when a sprite is integrated:
1. Detect collisions
2. Handle collisions

Detecting collisions: The Broad Phase

Collision detection can be further divided into two stages: the broad phase and the narrow phase.
During the broad phase the map where the sprite moves must be analyzed and the tiles where it could have collided due to the movement during the frame must be determined. Take the following instance of a sprite moving from point A to point B within a map:

A safe way to determine the tiles that need to be checked during the narrow phase is to enclose the sprite’s range of motion within a box, using the position of the pixel prior to and after integration as vertices:

The tiles the box intersects with (highlighted in yellow) are selected for analysis during the narrow phase:

The Narrow phase

This takes place within a tile, where it is determined if and how a collision between the character and a particular line within the tile took place. I’m gonna use a tile with a 45° slope to exemplify how this is done in Little Ninja, since collisions against slopes are usually the hardest to deal with in platformers. The tile consists of 3 lines, all of which will be defined internally by a normalized vector n (an arrow of length 1 that starts at the origin and points perpendicularly at the line) and a distance d, which is the distance from the origin to the line following the direction of n. The normal of the sloped line in the tile would look like this:

Now take these two cases: in the first one (A) the sprite lies above the line, in the second one it has phased through it (B). The positional vectors of the sprites are drawn pointing towards them (the components of which are just the sprite’s coordinates).

Now, I’ll add the normals back, and project the positional vectors of each sprite on the normal of the tile, in both cases d’ will represent the magnitude of the projected vector:


Notice that in A, d’ will be larger than the previously defined d (distance from the origin to the line), while in B, d’ will be smaller. Since n is a unit vector, d’ corresponds to the dot product of the positional vector of the sprite with the normal of the line. Now for some more pseudocode:

Collision Response

When it’s been determined that a sprite has penetrated a solid surface, it must be repositioned outside of the line’s bounds. The shortest distance between the sprite and the tile’s line where the collision took place will be in the direction of the line’s normal. The distance the sprite must travel in that direction to reach the outside of the line is the difference between d and d’, I’ll call that distance r:

Since n is a unit vector, the components of a vector in the same direction with a size of r can be obtained simply by multiplying the compoenents of n by r:

Walking Uphill

The great thing about using this method to resolve collisions is that it solves the problem of a character walking up a slope very elegantly, take for instance the following 2 sprites walking into a ramp and how the collisions are resolved.

As you can see, after the collision is resolved in both cases, the lateral distance traveled by each sprite is reduced depending on the slope of the hill and the lateral speed of the sprite. This means that characters in the game will not be able to run up ramps as fast as they can run on flat ground, but the rate at which they run will still be related to their speed. This creates a very nice effect that feels very natural when playing, here’s how it looks like in Little Ninja:

Drawbacks of the method

There’s a lot of things that we’re used to in video games that aren’t based on real physics but do make the games more enjoyable. A lot are obvious (like being able to change a character’s trajectory mid-jump), but some are a bit harder to notice and fix. Take the following collision and response:

The response makes perfect sense, if a sprite just completed a running jump and lands on the ground it’s important to maintain the lateral movement to keep the flow of the game steady. Let’s now take a look at exactly the same diagram rotated 45 degrees:


If a character standing on a slope jumps straight up, when he falls back down the response will push the sprite down the slope a few pixels. This makes as much sense as the previous case from a physics point of view, however we’re not used to this behavior in video games. Any gamer who barely makes a jump into a sloped surface only to be pushed back by the physics engine to his death will probably smash his controller against the screen. It is clear that this case must be handled differently: the x position must be maintained and all adjustments must be made solely in the y axis.

To do this it’s necessary to figure out the y component of the vector I’ve highlighted in blue in the following image:

Notice that if the vector a is projected on the normal of the line, the magnitude of the resulting vector will be r (a value we have already calculated). So the vector a satisfies the following equation:

We also know that the x component of the vector a is 0 (since it points straight upwards), if we solve for the y component of a we get:


Which is quite simple and fast to compute!

Is that all there is to it?

Nope. I didn’t want this post to grow too long so I didn’t mention a bunch of things that you’ll probably need to take care of if you’re working on a game (collision boxes, internal edge collisions, elastic collisions, etc). The best sources I’ve found so far are Paul Birth’s blog and Christer Ericson’s book Real-Time Collision Detection if you’re really interested in the subject.

We’ll keep the blog updated whenever we run into anything interesting during the development process. If you have any questions, comments, or ideas you want to share please post them in our comments section! Don’t forget to follow us on Twitter and Facebook!

Thanks!

2 Comments

Leave a Reply

%d bloggers like this: