Guide to the implementation of 2D platformers (start)

Since earlier I was disappointed with the amount of information on this issue, I decided to fill this gap by collecting different types of implementation of 2D platformers, describing their strengths and weaknesses and reflecting on the implementation details.

My goal was to create a comprehensive and understandable guide to the implementation of 2D platformers.



Disclaimer : Some of the information in this article was obtained by reverse engineering the behavior of the game, and not from the source code or from programmers. It is possible that in fact the game is not implemented as described in the article, but simply behaves in a similar way. It is also worth noting that the dimensions of the tile grid for game logic may differ from the sizes of the graphic tiles.

Four decisions

Four main options for decisions come to mind when creating a platformer. Within the framework of this article, all four will be considered, but due to the large volume of the article, it is divided into 2 parts (approx. Per.).

From simple to most complex, these are:

Type 1: Tiled (clean)

In it, the character’s positioning is limited by a grid of tiles, so he can never get between two tiles. Various animations can be used to create the illusion of smooth movement, however, according to the game logic, the character is always located directly on a specific tile. This is the easiest way to make a platformer, but it imposes great restrictions on character control, making it unacceptable for traditional action platformers. Nevertheless, it is very popular for puzzles and "cinematic" platformers.

Flashback, tile grid
Examples: Prince of Persia, Toki Tori, Lode Runner, Flashback

How it works
A map is a grid of tiles, each of which contains information about the properties of the tile: whether it is an obstacle or not, which image to use, which steps to play, and so on. And the player and other characters are represented by a set of one or more tiles moving together. For example, in Lode Runner, a player is a single tile. In Toki Tori, the player is 2x2 tiles. And in the game Flashback, which is rather unusual due to the small size of the grid of tiles, the player has dimensions of two tiles wide and five high (see image above) when standing, but only three tiles in height when bending down.
In games of this type, the character usually does not move diagonally, and if it moves, then the movement can be decomposed into two separate steps. A move over several tiles can be made by multiple shifts of single tiles, if necessary (in Flashback, a player always moves two tiles at a time). The following algorithm is added:

1. Create a copy of the character where it should be (i.e. if you need to move 1 tile to the right, you need to make a copy where each character tile is shifted by one tile to the right)
2. Check this copy for intersection with background and other characters
3. If an intersection is found, then the character's movement is blocked. Need to respond accordingly.
4. Otherwise, the path is clear. Move the character here, playing the animation, if necessary, so that the movement looks smooth.

This type of movement is completely unsuitable for ordinary jumps "in an arc", therefore games of this genre are completely devoid of jumps (Toki Tori, Lode Runner) or allow only horizontal or only vertical jumps of a fixed length (Prince of Persia, Flashback), which are nothing else like ordinary linear motion. The advantages of this system are simplicity and accuracy. Such games are more deterministic, which leads to a lower likelihood of glitches and more controlled gameplay, which does not require adjusting the values ​​too often depending on the circumstances. Fixed distances for interaction make it possible to make beautiful seamless animation. Implementation of some game mechanics (such as grabbing a ledge and one-sided platforms) is greatly simplified - all you need to do is check
Of course, this system does not allow you to take steps on less than one tile, but the steps can be reduced in different ways. For example, the tiles may be slightly smaller than the player (say, a 2x6 tile player), or you can allow “only visual” movement to move inside the selected tile without changing the logic (I believe this solution is applied in “Lode Runner - The Legend Returns ")

Type No. 2: Tile (Smooth)

Collisions are still determined by the grid of tiles, but characters can move around the world freely (usually with a resolution of 1 pixel. See the remark at the end of the article on smooth movement). This is the most common form of platformer implementation on 8-bit and 16-bit consoles, which remains popular today, as it is extremely easy to implement and allows you to edit the level much easier than using more complex techniques. It also allows you to make slopes and smooth jumps in an arc.
If you are not sure what kind of platformer you want to do, but definitely action, then I suggest stopping on this type. It is not surprising that the vast majority of the best action platformers of all time are based on this method.

Mega Man X, with a grid and character rectangle.

Examples: Super Mario World, Sonic the Hedgehog, Mega Man, Super Metroid, Contra, Metal Slug, and just about any 16-bit era platformer.

How it works
Information about the map is stored in the same way as in the purely tile method. The only difference is how the character interacts with the background. Now the character has a rectangle describing it for calculating collisions (AABB, which cannot rotate), and, usually, in size is a multiple of the size of the tile. Standard sizes are like one tile wide and one (small Mario, bent Samus), two (large Mario, Mega Man, bent Samus) or three (standing Samus) tiles in height. In many cases, the character’s sprite is visually larger than the logical rectangle, as this makes the game look more enjoyable and the gameplay more honest (agree that it is better for the player to avoid getting hit when he needs to get it than get it when he shouldn't).
In the image above, you can see that the sprite with the character “X” is square (two tiles wide), but the rectangle describing it is only one tile wide.
Provided that there are no slopes and one-sided platforms, the algorithm is simple:

1. Expand the movement on the X and Y axes, do one movement at a time. If you plan to add biases later, then first along X, then along Y. Otherwise, the order is absolutely not important. Then for each axis:
   Get the coordinate of the face in the direction of motion. For example: if you move to the left, X is the coordinate of the left side of the describing rectangle. If right, X is the coordinate of the right side. If top, Y is the top coordinate and so on.
2. Determine which tile lines intersect with the description rectangle - this will give the minimum and maximum value of the tile on the OTHER axis. For example, if we move to the left, suppose the player intersects with horizontal lines 32, 33 and 34 (here it is, tiles with Y = 32 * TS, Y = 33 * TS and Y = 34 * TS, where TS = tile size).
3. Examine these lines with tiles in the direction of travel until you find the nearest obstacle. Then, in a cycle, look at each moving obstacle and determine which of all is closest in your path.
4. The resulting movement of the player along this direction is the minimum between the distance to the nearest obstacle and the range of the player.
5. Move the player to a new position. From this position, handle a different coordinate, if not already processed.

Biases

Mega Man X, with comments on slopes

Slopes (tiles that are indicated by green arrows) are a bit tricky thing, since they are obstacles and at the same time allow the character to go to their tile. They also cause a change in the Y coordinate with a simple movement along the X axis. A simple way to make them is to allow the tile to store information about the "floor height" on each side. Suppose a coordinate system with a zero in the upper left corner, then the tile to the left of X (hero), the first slope tile, will contain heights {0, 3}. The one on which it stands will contain {4, 7}, then {8, 11}, then {12, 15}. After which everything will be repeated again with {0, 3} and so on. After we see a slope with a large angle, assembled from two tiles {0, 7} and {8, 15}.

Detailed view of the tile {4, 7}

The method that I am going to describe allows you to make arbitrary biases, despite obvious reasons, these two biases are the most common and are obtained from 12 tiles (6 are described earlier and their mirror copies). The collision algorithm changes for horizontal movement:

• Make sure that the movement along the X axis occurs earlier than along the Y.
• During the collision check (point 4 above), the slope is considered a collision only if its nearest face is the highest (less than the Y coordinate). This will prevent the situation with twitching the character when moving on the other side.
• You might want to prevent the character from stopping halfway down the slope (for example, on the {4, 7} tile). These restrictions are accepted in Mega Man X and many other games. If you do not want to, then you will have to deal with an even more difficult case when a player tries to climb from the bottom of the tile with a slope. One way to overcome this is to process the level and mark all such tiles. Then, when encountering collisions, you should also consider this as a collision from the bottom of the player if the player’s smallest Y coordinate is below the protruding part of the tile (tile coordinate * tile size + floor level y).
• An entire tile with an obstacle adjacent to a slope, if a player is standing on it, should not be considered as if it is attached to a slope. That is, if the character (its lower central pixel) is on the slope {0, *}, the left tile must be ignored, and if on the stole {*, 0} - the right one should be ignored. You can do this for a larger number of tiles, if the character is wider than two tiles - just throw off the check of the entire row if the player moves towards the top of the slope. The reason for doing this is to prevent the character from getting stuck in these tiles (highlighted in yellow in the screenshot above) while he is climbing and his feet will be below the “surface level” until then. until it rises to the level of direct tiles.

And for vertical movement:

• If gravity is allowed to do its job of descending a slope, make sure that the minimum displacement by gravity is compatible with slope and horizontal speed. For example, on a 4: 1 slope (in the screenshot {4, 7} above), the gravitational shift should be at least 1/4 of the horizontal speed rounded up. On a slope of 2: 1 (such as {0, 7}), a minimum of 1 \ 2. If this is not taken into account, the player will move horizontally to the end of the ramp over time, until gravity catches and throws him down, forcing him to jump on an inclined plane instead of smoothly descending it.
• An alternative to using gravity is to calculate the difference in the number of pixels between the height of the player before and after the movement (I use the formula below) and change its position so that everything matches.
• When moving down, take for calculation not the highest face of the slope for calculating collisions, but the current point on the vertical with the position of the player. To do this, find the [0, 1] value that determines the player’s location on the tile (0 = left, 1 = right) and use linear interpolation of floorY values. The code will look something like this:
  

  float t = float(centerX - tileX) / tileSize;
  float floorY = (1-t) * leftFloorY + t * rightFloorY;

• When moving down, if several tiles with obstacles are on the same Y coordinate and one on the X coordinate of the player’s center is the slope tile, then use it, ignore the others, even if they are technically closer. This will ensure more correct behavior on the edges of the slopes and will not allow the character to "move out" on a completely even tile just because there is a slope nearby.

Single sided platforms

Super Mario World, where Mario stumbles through (to the left) and stands on (to the right) of the same one-sided platform.

One-sided platforms are ordinary platforms that you can stand on, but you can jump through them from below. In other words, they are considered an obstacle if you are standing on them, and not considered if you are jumping from below. This fully describes their behavior. The algorithm changes a bit:

• in X coordinate this tile is never an obstacle
• In the Y coordinate, this tile is an obstacle only when moving from top to bottom and only when the player’s coordinate is greater (at least 1 pixel when it is standing) than the top face of the tile.

It is quite tempting to tie the behavior to the positive value of the vertical speed of the player (if the player falls), but this will not be true: the player can, when jumping, cross the platform, but then begin to fall down again, without having time to put his feet on the platform. In this case, it should still fall through it.
Some games allow the player to jump down from such platforms. There are several solutions, but they are all relatively simple. For example, you can disable one-sided platforms by one frame and make sure that the vertical speed is at least one pixel (so that the character is lower than the platform in the next frame), or you can check whether it is on a one-sided platform, and if it is, then move the character one pixel down.

Stairs

Mega Man 7, with a grid of tiles, illuminated staircase tiles, and a player rectangle.

Stairs may seem like a complicated thing, but they are implemented quite simply - when the character is on the stairs, he simply ignores most collisions and redefines them with a new set of rules. Stairs are usually one tile wide.
The stairs can be reached in two ways:

• The rectangle describing the character intersects with the stairs, it does not matter in the air or on the ground and by pressing the up button (some games allow you to press down)
• The character stands at the top of the staircase tile (which is often the one-sided platform tile, so you can walk on it) and presses down.

This immediately causes the effect of tying the X coordinate of the player to the tiles of the stairs, and if you move down the stairs, you just need to change the Y coordinate, since the player is already inside the real stairs. From this point on, some games start using a different descriptive rectangle to determine if the player is still on the stairs. Mega Man, for example, apparently uses a single tile (the equivalent of the top tile of a regular character, circled in red in the picture above).
To leave the stairs there are several options:

• Reach the top of the stairs. This usually ends the animation and moves the player a few pixels up the Y so that he now just stands on the top of the stairs.
• Reach the bottom of the hanging stairs. This will lead to the player simply falling, although some games simply will not allow them to leave the ladder this way.
• Move left or right. If there are no obstacles to the side, the player may be allowed to escape this way.
• To jump off. Some games allow you to free the ladder even so.

While the player is on the stairs, the character's behavior changes so that usually he can move up and down and sometimes attack.

Stairs

Castlevania: Dracula X, with a grid of tiles

Steps is a kind of stairs, as seen in some games, but especially in the Castlevania series. The implementation is very similar to stairs with some caveats:

• The player moves tile by tile or half of the tile (as in Dracula X)
• Each "step" shifts the player at the same time in both X and Y coordinates by a fixed amount.
• The definition of starting contact with the stairs at the start of the climb should look at the tile forward instead of the one that is crossing now.

Other games may implement ladders as slopes. In this case, the stairs are more decorative in nature.

Moving platforms

Super Mario World

Moving platforms may seem tricky, but really extremely simple. Unlike normal platforms, they cannot be represented by fixed tiles (for obvious reasons), but you need to describe them with an AABB rectangle. This is a common obstacle for all types of collisions. If you stay on this, then these will be very slippery platforms (they will work, but as planned, except that the character will not move with them).
There are several solutions. Let's analyze one algorithm:

• Before something moves in the scene, it is necessary to determine whether the character is on a moving platform. This can be achieved by checking, for example, whether the player’s central pixel is one pixel above the platform surface. If so, keep the pointer to the platform somewhere inside the character.
• We shift all moving platforms. We will make sure that we did this before we started moving the characters.
• For each character who stands on the platform, we calculate the delta of the platform displacement (how much has moved along each axis). Now move the character to the same value.
• Now we move the characters, as usual.

Other features

Sonic the Hedgehog 2

There are games that have sophisticated and exclusive features. For example, the Sonic the Hedgehog series. These features are beyond the scope of this article (and my knowledge, which is very important!), But may be the subject of a future article.

Continuation (ending)