Once the Level Scene base is ready, it's time to add in the Player entity and some semblance of a level.
Player Entity
A player entity (and most entities) composes of a BBox component and a Transform component. The Transform Component describes the position, velocity, and acceleration of the entity, while the BBox component describes the bounding box of the entity. Both of these components will be used for collision detection later.
Player Movement
In the original game, the player movement is fairly simple and straightforward. These are the possible movements which have to be implemented:
- Move left and right on ground
- Can crouch on ground and move
- Can jump once (standing or crouching) if possible
- Can swim in cardinal direction
- Can jump out of water For this implementation, I've opted to use acceleration for movement. This is not true in the original. I believe the original uses instant acceleration (directly modifying the velocity). The latter allows for more precise platforming. However, I find that acceleration is slightly easier to deal with. To allow better control of the player, the acceleration is set to a high value and the velocity is capped. This allows for a near-instant maximum velocity.
Two forces are applied to the player typically:
- Gravity: Constantly downwards. Does not apply if player is on the ground (cancelled out by normal force by the ground)
- Frictional force: modeled to be velocity-dependent and is consistent across ground and air movement. This is to avoid the player being faster in the air and therefore being more predictable with jumps. If the player is swimming:
- Gravity: same as before
- Upthrust: Some factor of gravity. In the original game, the player naturally floats upwards. Thus, upthrust is set to be higher than gravity.
- Frictional Force: now consistent in all direction
Movement Update
The movement update is a simple forward Euler method.
Collision System Part I
With the introduction of a player, the collision system should be implemented as well. In the original game, the game is set up as with a grid-like system. Therefore, the implementation will follow suit. This part of collision system to mainly focus on collision with solid tiles. Entities collision handling will come later.
This isn't the first time I've deal with collision. In fact, I've always thought how collisions are handled in game for years. Past implementations of mine in the past worked but not quite satisfying.
To keep it simple, the only collision shape to deal with is Axis-Aligned Bounding Boxes (AABB). This should be sufficient as the original game does not introduce slopes or any more convex shapes.
Broad Phase
The purpose of this phase is to filter out non-colliding entities and tiles and only retain only potentially colliding tiles and entities.
There are multiple ways to go about this phase. In this implementation, a fixed-size grid is used to partition the gameplay space. This grid will also act as the tile map. When an entity moves, it will also need to update its position in the grid map so that it can be quickly referenced for a collision check in the narrow phase.
typedef struct Tile
{
bool solid;
struct sc_map_64 entities_set;
}Tile_t;
typedef struct TileGrid
{
unsigned int width;
unsigned int height;
unsigned int n_tiles;
Tile_t * tiles;
}TileGrid_t;
The entities that a tile is containing can be found in the entities_set of a Tile. The solid boolean field indicates if the tile is solid.
To assist in the update, a new component is used to keep track of the tiles an entity currently exist in. This is to avoid going over all the tiles to clear the entities before update. Now, only the tiles which the entity is previously in is involved.
typedef struct _CTileCoord_t
{
unsigned int tiles[8];
unsigned int n_tiles;
}CTileCoord_t;
The components has a hard limit of 8 tiles. A vector data struct is not used as that is not compatible with the existing initialisation method of components (which just memsets to 0). However, should the need arises, this can be changed.
Thus, with these additions, the broad phase update code would look something like this:
Entity_t *p_ent;
sc_map_foreach_value(&scene->ent_manager.entities, p_ent)
{
CTileCoord_t * p_tilecoord = get_component(&scene->ent_manager, p_ent, CTILECOORD_COMP_T);
if (p_tilecoord == NULL) continue;
CTransform_t * p_ctransform = get_component(&scene->ent_manager, p_ent, CTRANSFORM_COMP_T);
if (p_ctransform == NULL) continue;
CBBox_t * p_bbox = get_component(&scene->ent_manager, p_ent, CBBOX_COMP_T);
if (p_bbox == NULL) continue;
// Update tilemap position
for (size_t i=0;i<p_tilecoord->n_tiles;++i)
{
// Use previously store tile position
// Clear from those positions
unsigned int tile_idx = p_tilecoord->tiles[i];
sc_map_del_64(&(tilemap.tiles[tile_idx].entities_set), p_ent->m_id);
}
p_tilecoord->n_tiles = 0;
// Compute new occupied tile positions and add
// Extend the check by a little to avoid missing
unsigned int tile_x1 = (p_ctransform->position.x) / TILE_SIZE;
unsigned int tile_y1 = (p_ctransform->position.y) / TILE_SIZE;
unsigned int tile_x2 = (p_ctransform->position.x + p_bbox->size.x) / TILE_SIZE;
unsigned int tile_y2 = (p_ctransform->position.y + p_bbox->size.y) / TILE_SIZE;
for (unsigned int tile_y=tile_y1; tile_y <= tile_y2; tile_y++)
{
for (unsigned int tile_x=tile_x1; tile_x <= tile_x2; tile_x++)
{
unsigned int tile_idx = tile_y * tilemap.width + tile_x;
p_tilecoord->tiles[p_tilecoord->n_tiles++] = tile_idx;
sc_map_put_64(&(tilemap.tiles[tile_idx].entities_set), p_ent->m_id, 0);
}
}
}
This is not used in the current stage. As the implementation continues to flesh out, this is subject to changes.
With the tilemap, a solid tile is not an entity in the implementation. However, it can be treated similarily to check for collision.
Narrow Phase
Once the tiles to check for collision are identified, we enter the narrow phase collision. As stated, the focus will be on solid tiles.
A solid tile is just a tile where a player can collide with it entirely. Therefore, a solid tile can be treated as a AABB with a size of a grid size. The player is an AABB entity.
So, the goal is to implement a collision detection between AABB and AABB, and collision resolution for the player. These two phases are distinct and is worth mentioning. Most tutorials I've searched up only deal with the first part, which is straightforward to do, but neglect the second part. In the past, the way I would resolve a collision is to take the minimum overlap (computed from AABB collision detection) and move out of it. Some tutorials would use an impulse-based method, which I don't fully understand.
Thankfully, the lecture series does address both parts. What interesting is the proposed method of resolution. Rather than using the minimum overlap, it uses the overlap amount from the previous frame to determine which direction is the entity colliding towards. E.g. if the previous overlap is higher in the X direction, then the collision would be from the Y direction, and therefore the Y overlap should be used for resolution. For AABB resolution, this method works well enough.
There are a lot more to narrow phase collision when the bounding box is not limited to AABB. Outside of AABB, there are a lot more edge cases to consider. Particularly, I have thought about slopes quite a bit and how to handle that. One hard edge case that I can think of is how to resolve a collision between two consecutive tiles that forms a 'V' shape. Even just resolve normal slopes is already a challenge, really. For now, this will not be a focus.
These are links that I find useful to reference when dealing with collision: